{"raw_statement":[{"iden":"statement","content":"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.\n\nIvan 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_.\n\nYou 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."},{"iden":"input","content":"The first line contains single integer _n_ (1 ≤ _n_ ≤ 105) — the number of strings Ivan remembers.\n\nThe 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 106, 1 ≤ _x__i_, _j_ ≤ 106, 1 ≤ _k__i_ ≤ 106, and the sum of all _k__i_ doesn't exceed 106. The strings _t__i_ can coincide.\n\nIt is guaranteed that the input data is not self-contradictory, and thus at least one answer **always** exists."},{"iden":"output","content":"Print lexicographically minimal string that fits all the information Ivan remembers."},{"iden":"examples","content":"Input\n\n3\na 4 1 3 5 7\nab 2 1 5\nca 1 4\n\nOutput\n\nabacaba\n\nInput\n\n1\na 1 3\n\nOutput\n\naaa\n\nInput\n\n3\nab 1 1\naba 1 3\nab 2 3 5\n\nOutput\n\nababab"}],"translated_statement":[{"iden":"statement","content":"Ivan 有一个由小写英文字母组成的字符串 #cf_span[s]。然而，他的朋友 Julia 故意捉弄他，把字符串 #cf_span[s] 隐藏了起来。Ivan 更愿意构造一个新的字符串，而不是去找原来的那个。\n\nIvan 记得关于字符串 #cf_span[s] 的一些信息：他记得字符串 #cf_span[ti] 在字符串 #cf_span[s] 中至少出现了 #cf_span[ki] 次或更多，并且他准确记得 #cf_span[ki] 个字符串 #cf_span[ti] 在 #cf_span[s] 中出现的位置：这些位置是 #cf_span[xi, 1, xi, 2, ..., xi, ki]。他一共记得 #cf_span[n] 个这样的字符串 #cf_span[ti]。\n\n你需要重构一个字典序最小的字符串 #cf_span[s]，使其满足 Ivan 记住的所有信息。字符串 #cf_span[ti] 和字符串 #cf_span[s] 仅由小写英文字母组成。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）—— Ivan 记住的字符串数量。\n\n接下来的 #cf_span[n] 行包含关于这些字符串的信息。第 #cf_span[i] 行包含一个非空字符串 #cf_span[ti]，一个正整数 #cf_span[ki]（表示字符串 #cf_span[ti] 在字符串 #cf_span[s] 中出现的次数），以及 #cf_span[ki] 个互不相同的正整数 #cf_span[xi, 1, xi, 2, ..., xi, ki]（按递增顺序排列），表示字符串 #cf_span[ti] 在 #cf_span[s] 中出现的起始位置。保证所有字符串 #cf_span[ti] 的长度之和不超过 #cf_span[106]，#cf_span[1 ≤ xi, j ≤ 106]，#cf_span[1 ≤ ki ≤ 106]，且所有 #cf_span[ki] 的总和不超过 #cf_span[106]。字符串 #cf_span[ti] 可能相同。\n\n保证输入数据无自相矛盾之处，因此至少存在一个合法答案。\n\n请输出一个字典序最小的字符串，满足 Ivan 记住的所有信息。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）—— Ivan 记住的字符串数量。接下来的 #cf_span[n] 行包含关于这些字符串的信息。第 #cf_span[i] 行包含一个非空字符串 #cf_span[ti]，一个正整数 #cf_span[ki]（表示字符串 #cf_span[ti] 在字符串 #cf_span[s] 中出现的次数），以及 #cf_span[ki] 个互不相同的正整数 #cf_span[xi, 1, xi, 2, ..., xi, ki]（按递增顺序排列），表示字符串 #cf_span[ti] 在 #cf_span[s] 中出现的起始位置。保证所有字符串 #cf_span[ti] 的长度之和不超过 #cf_span[106]，#cf_span[1 ≤ xi, j ≤ 106]，#cf_span[1 ≤ ki ≤ 106]，且所有 #cf_span[ki] 的总和不超过 #cf_span[106]。字符串 #cf_span[ti] 可能相同。保证输入数据无自相矛盾之处，因此至少存在一个合法答案。"},{"iden":"output","content":"请输出一个字典序最小的字符串，满足 Ivan 记住的所有信息。 "},{"iden":"examples","content":"输入\n3\na 4 1 3 5 7\nab 2 1 5\nca 1 4\n输出\nabacaba\n\n输入\n1\na 1 3\n输出\naaa\n\n输入\n3\nab 1 1\naba 1 3\nab 2 3 5\n输出\nababab"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of remembered substrings.  \nFor each $ i \\in \\{1, \\dots, n\\} $:  \n- Let $ t_i \\in \\Sigma^* $ be a non-empty string over $ \\Sigma = \\{a, b, \\dots, z\\} $.  \n- Let $ k_i \\in \\mathbb{Z}^+ $ be the number of occurrences of $ t_i $ in $ s $.  \n- Let $ X_i = (x_{i,1}, x_{i,2}, \\dots, x_{i,k_i}) $ be a strictly increasing sequence of starting positions where $ t_i $ occurs in $ s $, with $ x_{i,j} \\geq 1 $.  \n\nLet $ s \\in \\Sigma^* $ be the unknown target string.  \n\n**Constraints**  \n1. For each $ i \\in \\{1, \\dots, n\\} $, and for each $ j \\in \\{1, \\dots, k_i\\} $:  \n   $$\n   s[x_{i,j} : x_{i,j} + |t_i| - 1] = t_i\n   $$  \n   (i.e., the substring of $ s $ starting at position $ x_{i,j} $ of length $ |t_i| $ equals $ t_i $).  \n\n2. The total number of position constraints is $ \\sum_{i=1}^n k_i \\leq 10^6 $.  \n3. The total length of all $ t_i $ is $ \\sum_{i=1}^n |t_i| \\leq 10^6 $.  \n4. All $ x_{i,j} \\leq 10^6 $, and positions are consistent (no conflicting assignments).  \n\n**Objective**  \nFind the lexicographically minimal string $ s $ satisfying all constraints above.","simple_statement":null,"has_page_source":false}