题目描述

Your brother has a string $S$ of length $M$ with indices from $1$ to $M$. You want to know exactly what string $S$ is. To help you, he gives you $N$ hints that might help you to figure out $S$. Hint $i$ is represented by an integer $X_i$ and a string $T_i$, indicating that the string $T_i$ appears as a substring of $S$ starting from index $X_i$ of $S$. All the hints are unique, that is, there are no hints $i$ and $j$ such that $i \neq j$ while $X_i = X_j$ and $T_i = T_j$.

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

A string $S$ is a possible solution if and only if there exists a set of at least $N - 1$ hints (that are assumed to be true) where string $S$ 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 $-1$. If there is more than one possible solution, you should output $-2$.

输入格式

Input begins with two integers $N$ $M$ ($1 \leq N \leq 100$; $1 \leq M \leq 100$) representing the number of hints and the length of the scary string, respectively. Each of the next $N$ lines contains an integer and a string $X_i$ $T_i$ ($1 \leq X_i, |T_i|$; $X_i + |T_i| - 1 \leq M$) representing hint $i$. The string $T_i$ consists of only uppercase characters. It is guaranteed that there are no hints $i$ and $j$ such that $i \neq j$ while $X_i = X_j$ and $T_i = T_j$.

输出格式

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

3 11
5 JAKARTA
1 ICPC
3 BINUS

ICPCJAKARTA

3 9
6 EX
8 AM
1 FINAL

FINALEXAM

3 8
1 GRAD
5 UAL
6 ATE

-1

3 5
1 BIN
4 US
4 OM

-2

提示

Explanation for the sample input/output #1

The only possible $S$ is ICPCJAKARTA assuming hint $3$ 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 $S$ 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 $1$ is false: There is no string consistent with the other two hints.
• Assuming hint $2$ is false or hint $3$ is false: There is more than one string consistent with the other two hints.

Explanation for the sample input/output #4

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