Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. String Reconstruction

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIvan 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* ≤ 10^{5}) — 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 10^{6}, 1 ≤ *x* _{ i, j} ≤ 10^{6}, 1 ≤ *k* _{ i} ≤ 10^{6}, and the sum of all *k* _{ i} doesn't exceed 10^{6}. 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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/14/2020 03:34:24 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|