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_ioccurs 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.

Input

The first line contains single integer n (1 ≤ n ≤ 10⁵) — 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_idoesn't exceed 10⁶, 1 ≤ x_i, j ≤ 10⁶, 1 ≤ k_i ≤ 10⁶, and the sum of all k_i doesn't exceed 10⁶. 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 寻找一个字符串。给你一些线索（某些子串的位置），输出一个满足条件的最小字典序字符串。 暴力求解超时。可以采用并查集，若当前位置已经有子串放置，那就从已知子串的末尾继续放。并查集记录下末尾的下一位。很好的避免了重叠部分的重复枚举。有点像cys学长教过的那道next跳的题。 并查集套路题。

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #define MAX 2000005#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;int f[MAX];char a[MAX];int find(int x){ return f[x]==x?x:f[x]=find(f[x]);}int main(){ int n,m,x,len,i,j,k,ii; char s[MAX]; scanf("%d",&n); for(i=0;i<=2000000;i++){ a[i]='a'; f[i]=i; } int maxx=0; while(n--){ scanf(" %s %d",s,&k); len=strlen(s); for(j=1;j<=k;j++){ scanf("%d",&x); int xx=find(x); int ff=find(len+x); for(i=xx,ii=xx-x;i<=len+x-1;i++,ii++){ a[i]=s[ii]; f[find(i)]=ff; } if(len+x-1>maxx) maxx=len+x-1; } } for(i=1;i<=maxx;i++){ printf("%c",a[i]); } printf("\n"); return 0;}