English · Original
Chinese · Translation
Formal · Original
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_ ≤ 105) — 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 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.
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.
[samples]
Ivan 有一个由小写英文字母组成的字符串 #cf_span[s]。然而，他的朋友 Julia 想捉弄他，把字符串 #cf_span[s] 藏了起来。Ivan 选择重新构造一个字符串，而不是去找原来的那个。
Ivan 记得一些关于字符串 #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]。
你需要重构一个字典序最小的字符串 #cf_span[s]，使其满足 Ivan 记住的所有信息。字符串 #cf_span[ti] 和字符串 #cf_span[s] 仅由小写英文字母组成。
第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]）—— 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[10^6]，#cf_span[1 ≤ xi, j ≤ 10^6]，#cf_span[1 ≤ ki ≤ 10^6]，且所有 #cf_span[ki] 的总和不超过 #cf_span[10^6]。字符串 #cf_span[ti] 可能相同。
保证输入数据没有自相矛盾，因此至少存在一个合法答案。
请输出一个字典序最小的字符串，满足 Ivan 记住的所有信息。
## Input
第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]）—— 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[10^6]，#cf_span[1 ≤ xi, j ≤ 10^6]，#cf_span[1 ≤ ki ≤ 10^6]，且所有 #cf_span[ki] 的总和不超过 #cf_span[10^6]。字符串 #cf_span[ti] 可能相同。保证输入数据没有自相矛盾，因此至少存在一个合法答案。
## Output
请输出一个字典序最小的字符串，满足 Ivan 记住的所有信息。
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of remembered substrings.
For each $ i \in \{1, \dots, n\} $:
- Let $ t_i \in \Sigma^* $ be a non-empty string over $ \Sigma = \{a, b, \dots, z\} $.
- Let $ k_i \in \mathbb{Z}^+ $ be the number of occurrences of $ t_i $ in $ s $.
- Let $ X_i = (x_{i,1}, x_{i,2}, \dots, x_{i,k_i}) $ be a strictly increasing sequence of starting positions (1-indexed) where $ t_i $ occurs in $ s $.
Let $ s \in \Sigma^* $ be the target string to reconstruct.
**Constraints**
1. For each $ i \in \{1, \dots, n\} $ and each $ j \in \{1, \dots, k_i\} $:
$$
s[x_{i,j} : x_{i,j} + |t_i| - 1] = t_i
$$
2. The total length of all $ t_i $ satisfies $ \sum_{i=1}^n |t_i| \leq 10^6 $.
3. The total number of occurrences satisfies $ \sum_{i=1}^n k_i \leq 10^6 $.
4. All positions $ x_{i,j} \geq 1 $ and $ x_{i,j} + |t_i| - 1 \leq |s| $.
5. The string $ s $ must be **lexicographically minimal** among all strings satisfying the above.
**Objective**
Find the lexicographically minimal string $ s \in \Sigma^* $ such that for every $ i, j $, the substring of $ s $ starting at position $ x_{i,j} $ of length $ |t_i| $ equals $ t_i $.
API Response (JSON)
{
"problem": {
"name": "A. String Reconstruction",
"description": {
"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. Ivan k",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF827A"
},
"statements": [
{
"statement_type": "Markdown",
"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 k...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Ivan 有一个由小写英文字母组成的字符串 #cf_span[s]。然而，他的朋友 Julia 想捉弄他，把字符串 #cf_span[s] 藏了起来。Ivan 选择重新构造一个字符串，而不是去找原来的那个。\n\nIvan 记得一些关于字符串 #cf_span[s] 的信息。具体来说，他记得字符串 #cf_span[ti] 在字符串 #cf_span[s] 中至少出现了 #cf_span[ki] 次或...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**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, \\d...",
"is_translate": false,
"language": "Formal"
}
]
}