#215680. [ICPC 2022 Jakarta R] Nightmare Brother

Your brother has a string of length with indices from to . You want to know exactly what string is. To help you, he gives you hints that might help you to figure out . Hint is represented by an integer and a string , indicating that the string appears as a substring of starting from index of . All the hints are unique, that is, there are no hints and such that while and .

However, your brother is known to be mischievous and tells you that there might be at most one false hint among all hints he has given, but he didn't tell you which.

A string is a possible solution if and only if there exists a set of at least hints (that are assumed to be true) where string is the only string consistent with all of the hints in the set.

You would like to find a possible solution. If there is no possible solution, you should output . If there is more than one possible solution, you should output .

Input begins with two integers (; ) representing the number of hints and the length of the scary string, respectively. Each of the next lines contains an integer and a string (; ) representing hint . The string consists of only uppercase characters. It is guaranteed that there are no hints and such that while and .

If there is exactly one possible solution as explained in the problem description above, then output the string in a single line. If there is no possible solution, then output in a single line. If there is more than one possible solution, then output in a single line.

样例输入 1

3 11
5 JAKARTA
1 ICPC
3 BINUS

样例输出 1

ICPCJAKARTA

样例输入 2

3 9
6 EX
8 AM
1 FINAL

样例输出 2

FINALEXAM

样例输入 3

3 8
1 GRAD
5 UAL
6 ATE

样例输出 3

-1

样例输入 4

3 5
1 BIN
4 US
4 OM

样例输出 4

-2

Explanation for the sample input/output #1

The only possible is ICPCJAKARTA assuming hint is false. If the false hint is assumed to be one of the others, then there is no string consistent with the other two hints. Similarly when no hint is assumed false.

Explanation for the sample input/output #2

The only possible is FINALEXAM assuming no hint is false. If any of the hints are assumed to be false, then there is more than one string consistent with the rest of the hints.

Explanation for the sample input/output #3

There is no possible solution.

• Assuming no hint is false: There is no string consistent with all the hints.
• Assuming hint is false: There is no string consistent with the other two hints.
• Assuming hint is false or hint is false: There is more than one string consistent with the other two hints.

Explanation for the sample input/output #4

There are possible solutions: BINOM (assuming hint is false) and BINUS (assuming hint is false).