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}, k_{i}. 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.


-----Input-----

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}, k_{i} 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.


-----Output-----

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


-----Examples-----
Input
3
a 4 1 3 5 7
ab 2 1 5
ca 1 4

Output
abacaba

Input
1
a 1 3

Output
aaa

Input
3
ab 1 1
aba 1 3
ab 2 3 5

Output
ababab

Difficulty: interview

Starter code:

Solutions:
import math as mt 
import sys,string
input=sys.stdin.readline
print=sys.stdout.write
import random
from collections import deque,defaultdict
L=lambda : list(map(int,input().split()))
Ls=lambda : list(input().split())
M=lambda : map(int,input().split())
I=lambda :int(input())
t=I()
d=defaultdict(str)
ml=0
p=0
for _ in range(t):
    s=input().split()
    w=s[0]
    x=list(map(int,s[1::]))
    for i in range(1,len(x)):
        r=d[x[i]-1]
        if(len(r)<len(w)):
            d[x[i]-1]=w
    ml=max(ml,len(w)+x[-1]-1)
ans="a"*ml
ans=list(ans)
#print(d)
p=-1
z=sorted(list(d.keys()))
for i in z:
    if(i+len(d[i])>p):
        if(i>=p):
            for j in range(i,i+len(d[i])):
                ans[j]=d[i][j-i]
        else:
            leave=p-i
            f=max(i,p)
            #print(ans,"@",d[i],p,d[i][leave::])
            for j in range(leave,len(d[i])):
                ans[f]=d[i][j]
                f+=1
            #print(ans,"*")
        p=i+len(d[i])
    
for i in ans:
    print(i)