CodeForces - 828C String Reconstruction 并查集（next跳）

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, 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⁵) — 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_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<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<string>

#include<math.h>

#include<queue>

#include<set>

#include<stack>

#include<algorithm>

#include<vector>

#include<iterator>

#define MAX 2000005

#define INF 0x3f3f3f3f

#define MOD 1000000007

using 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=;i<=;i++){

        a[i]='a';

        f[i]=i;

    }

    int maxx=;

    while(n--){

        scanf(" %s %d",s,&k);

        len=strlen(s);

        for(j=;j<=k;j++){

            scanf("%d",&x);

            int xx=find(x);

            int ff=find(len+x);

            for(i=xx,ii=xx-x;i<=len+x-;i++,ii++){

                a[i]=s[ii];

                f[find(i)]=ff;

            }

            if(len+x->maxx) maxx=len+x-;

        }

    }

    for(i=;i<=maxx;i++){

        printf("%c",a[i]);

    }

    printf("\n");

    return ;

}

巴特西

CodeForces - 828C String Reconstruction 并查集（next跳）

String Reconstruction

最新文章

热门文章