У Ивана была строка s, состоящая из строчных букв латинского алфавита. Но его подруга Юля решила пошутить над ним и спрятала строку s. Иван решил, что не будет искать строку, а просто сделает новую.
Иван помнит о строке s следующую информацию. Он помнит, что строка ti встречается в строке s количество раз ki или больше, а также помнит ровно ki позиций, с которых начинается вхождение строки ti в строку s — это позиции xi, 1, xi, 2, ..., xi, ki. При этом количество строк ti, про которые помнит Иван, равно n.
Перед вами стоит задача восстановить лексикографически минимальную строку s такую, что она удовлетворяет всей информации, которую помнит Иван. Как строки ti, так и строка s могут содержать только строчные буквы латинского алфавита.
Выходные данные
Выведите лексикографически минимальную строку, которая удовлетворяет всей информации, которую помнит Иван.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
a 4 1 3 5 7
ab 2 1 5
ca 1 4
|
abacaba
|
|
2
|
1
a 1 3
|
aaa
|
|
3
|
3
ab 1 1
aba 1 3
ab 2 3 5
|
ababab
|