P15618 [ICPC 2022 Jakarta R] Nightmare Brother

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.

#### 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).