DMOPC '19 Contest 1 P5 - Broken String

View as PDF

Submit solution

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

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 lowercase 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.


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

Subtask 1 [5%]


Subtask 2 [15%]

K \le 2
N \le 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 1

5 3

Sample Output 1


Sample Input 2

2 5

Sample Output 2



There are no comments at the moment.