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 ≤ 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

Difficulty: MEDIUM_HARD
Tags: String algorithms

Sorting

Data structures
Skill types: Sorting

Data structures

Starter code:

Solutions:
from sys import stdin, stdout
sze = 10 ** 6 + 1
n = int(stdin.readline())
challengers = []
strings = []
sze = 10 ** 6 + 1
cnt = [0 for i in range(sze)]
for i in range(n):
	s = stdin.readline().strip().split()
	num = int(s[1])
	values = list(map(int, s[2:]))
	strings.append(s[0])
	for j in range(num):
		if not cnt[values[j]]:
			cnt[values[j]] = (i, len(s[0]))
		elif cnt[values[j]][1] < len(s[0]):
			cnt[values[j]] = (i, len(s[0]))
previous = 1
for i in range(sze):
	if not cnt[i]:
		continue
	(ind, s) = (i, cnt[i][0])
	s = strings[s]
	if previous < ind:
		stdout.write(str('a') * (ind - previous))
		previous = ind
	if previous > ind + len(s) - 1:
		continue
	else:
		stdout.write(s[previous - ind:len(s)])
		previous = ind + len(s)


import math as mt
import sys, string
input = sys.stdin.readline
print = sys.stdout.write
import random
from collections import deque, defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
t = I()
d = defaultdict(str)
ml = 0
p = 0
for _ in range(t):
	s = input().split()
	w = s[0]
	x = list(map(int, s[1:]))
	for i in range(1, len(x)):
		r = d[x[i] - 1]
		if len(r) < len(w):
			d[x[i] - 1] = w
	ml = max(ml, len(w) + x[-1] - 1)
ans = 'a' * ml
ans = list(ans)
p = -1
z = sorted(list(d.keys()))
for i in z:
	if i + len(d[i]) > p:
		if i >= p:
			for j in range(i, i + len(d[i])):
				ans[j] = d[i][j - i]
		else:
			leave = p - i
			f = max(i, p)
			for j in range(leave, len(d[i])):
				ans[f] = d[i][j]
				f += 1
		p = i + len(d[i])
for i in ans:
	print(i)