← 返回题目列表

Codeforces · 827/A

A. 字符串重建

中文机器翻译题面 查看原题

Ivan 有由小英文字母组成的字符串 s。然而,他的朋友朱莉娅决定取笑他并隐藏了字符串 s。伊万更喜欢制作一根新弦,而不是寻找旧弦。

Ivan 知道有关字符串 s 的一些信息。也就是说,他记得字符串 ti 在字符串 s 中至少出现 ki 次或更多,他还准确记得字符串 ti 在字符串 s 中出现的 ki 个位置:这些位置是 xi, 1, xi, 2, ..., xi, ki。他记得n这样的字符串ti。

你要重建字典顺序最小的字符串 s ,使其适合 Ivan 记住的所有信息。字符串 ti 和字符串 s 仅由小英文字母组成。

输入

第一行包含单个整数 n (1 ≤ n ≤ 105) — Ivan 记住的字符串数量。

接下来的 n 行包含有关字符串的信息。这些行中的第 i 行包含非空字符串 ti,然后是正整数 ki,它等于字符串 ti 在字符串 s 中出现的次数,然后是 ki 个不同的正整数 xi, 1, xi, 2, ..., xi, ki 按升序排列 — 字符串 ti 在字符串 s 中出现的起始位置。保证字符串ti的长度之和不超过106、1≤xi、j≤106、1≤ki≤106,且所有ki的总和不超过106。字符串ti可以重合。

保证输入数据不自相矛盾,因此至少有一个答案总是存在。

输出

按字典顺序打印符合 Ivan 记住的所有信息的最小字符串。

示例

输入 #1

3
a 4 1 3 5 7
ab 2 1 5
ca 1 4

输出 #1

abacaba

输入 #2

1
a 1 3

输出 #2

aaa

输入 #3

3
ab 1 1
aba 1 3
ab 2 3 5

输出 #3

ababab