DMOPC '19 Contest 1 P5 - Broken String

View as PDF

Submit solution


Points: 17
Time limit: 3.0s
Memory limit: 128M

Author:
Problem type

During class, Bob's teacher wanted to try an interesting activity. He began by writing down a string of length N+K-1 containing only lower-case English letters, where N is the number of students. Afterwards, he writes down each of the N substrings of length K, and gives one to each student. Bob and the rest of the class now need to find out what the original string could have been, or if the teacher has made a mistake.

Constraints

In all subtasks,
1 \le N \le 200\space 000
1 \le K \le 5

Subtask 1 [5%]

K=1

Subtask 2 [15%]

K\leq 2
N\leq 20

Subtask 3 [20%]

You only need to determine whether or not the teacher has made a mistake.
If there is a candidate for the original string, print out any string of length N+K-1

Subtask 4 [60%]

No additional constraints

Input Specification

The first line contains two space-separated integers, N and K.
N lines follow, each containing a string of length K, one of the strings that the students received.

Output Specification

On one line, output any string that the teacher could have written down. If there are multiple such strings, then output any of them.
If there are no candidates for the original string, output -1 .

Sample Input

5 3
obl
rob
lem
pro
ble

Sample Output

problem

Sample Input 2

2 5
abcde
cdefa

Sample Output 2

-1

Comments

There are no comments at the moment.