Изначально была дана строка s длины n, состоящая из строчных латинских букв. Её скопировали ровно k раз, получив при этом k одинаковых строк s1, s2, ..., sk. После этого в каждой из них поменяли местами ровно одну пару символов (возможно, одинаковых, но находящихся на разных позициях).
Вам необходимо по заданным k строкам s1, s2, ..., sk восстановить любую подходящую строку s. Обратите внимание, что суммарная длина всех строк не превосходит 5000 (то есть k·n ≤ 5000).
Выходные данные
В единственной строке выведите любую подходящую строку s, либо же «-1» (без кавычек), если такой строки не существует.
Примечание
В первом тестовом примере строка s1 получается из строки acab перестановкой местами 2 и 4 символов, строка s2 получается перестановкой 1 и 2 символов, а строка s3 — 3 и 4 символов.
Во втором тестовом примере s1 получается из строки kbub перестановкой 3 и 4 символов, s2 — перестановкой 2 и 4 символов, а s3 — перестановкой 1 и 3 символов.
В третьем тестовом примере невозможно получить никакую строку, удовлетворяющую условиям.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
abac
caab
acba
|
acab
|
|
2
|
3 4
kbbu
kbub
ubkb
|
kbub
|
|
3
|
5 4
abcd
dcba
acbd
dbca
zzzz
|
-1
|