A10983 | String Reconstruction

Ivan had string $s$ consisting of small English letters. However, his friend Julia decided to make fun of him and hid the string $s$ . Ivan preferred making a new string to finding the old one.

Ivan knows some information about the string $s$ . Namely, he remembers, that string $t_{i}$ occurs in string $s$ at least $k_{i}$ times or more, he also remembers exactly $k_{i}$ positions where the string $t_{i}$ occurs in string $s$ : these positions are $x_{i,1},x_{i,2},...,x_{i,ki}$ . He remembers $n$ such strings $t_{i}$ .

You are to reconstruct lexicographically minimal string $s$ such that it fits all the information Ivan remembers. Strings $t_{i}$ and string $s$ consist of small English letters only.

The first line contains single integer $n$ ( $1<=n<=10^{5}$ ) — the number of strings Ivan remembers.

The next $n$ lines contain information about the strings. The $i$ -th of these lines contains non-empty string $t_{i}$ , then positive integer $k_{i}$ , which equal to the number of times the string $t_{i}$ occurs in string $s$ , and then $k_{i}$ distinct positive integers $x_{i,1},x_{i,2},...,x_{i,ki}$ in increasing order — positions, in which occurrences of the string $t_{i}$ in the string $s$ start. It is guaranteed that the sum of lengths of strings $t_{i}$ doesn't exceed $10^{6}$ , $1<=x_{i,j}<=10^{6}$ , $1<=k_{i}<=10^{6}$ , and the sum of all $k_{i}$ doesn't exceed $10^{6}$ . The strings $t_{i}$ can coincide.

It is guaranteed that the input data is not self-contradictory, and thus at least one answer always exists.

Print lexicographically minimal string that fits all the information Ivan remembers.