说明

你的兄弟有一个长度为 $M$ 的字符串 $S$，下标从 $1$ 到 $M$。你想确切地知道 $S$ 是什么。为了帮助你，他给了你 $N$ 条可能有助于推断 $S$ 的提示。第 $i$ 条提示由一个整数 $X_i$ 和一个字符串 $T_i$ 表示，表明字符串 $T_i$ 作为子串出现在 $S$ 中，并且起始于 $S$ 的下标 $X_i$ 处。所有提示都是唯一的，即不存在两条不同的提示 $i$ 和 $j$（$i \neq j$）满足 $X_i = X_j$ 且 $T_i = T_j$。

然而，你的兄弟以调皮著称，他告诉你，在他给出的所有 $N$ 条提示中，最多有一条是假提示，但他没有告诉你具体是哪一条。

一个字符串 $S$ 是一个可能的解，当且仅当存在一个包含至少 $N - 1$ 条提示（这些提示被假定为真）的集合，使得字符串 $S$ 是唯一一个与该集合中所有提示都一致的字符串。

你想找到一个可能的解。如果不存在可能的解，你应该输出 $-1$。如果存在多于一个可能的解，你应该输出 $-2$。

输入格式

输入以两个整数 $N$ $M$（$1 \leq N \leq 100$；$1 \leq M \leq 100$）开始，分别表示提示的数量和神秘字符串 $S$ 的长度。接下来的 $N$ 行，每行包含一个整数和一个字符串 $X_i$ $T_i$（$1 \leq X_i, |T_i|$；$X_i + |T_i| - 1 \leq M$），表示第 $i$ 条提示。字符串 $T_i$ 仅由大写字母组成。保证不存在两条不同的提示 $i$ 和 $j$（$i \neq j$）满足 $X_i = X_j$ 且 $T_i = T_j$。

输出格式

如果根据上述问题描述恰好存在一个可能的解，则在一行中输出字符串 $S$。如果不存在可能的解，则在一行中输出 $-1$。如果存在多于一个可能的解，则在一行中输出 $-2$。

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

提示

样例输入/输出 #1 的解释

唯一的可能解 $S$ 是 ICPCJAKARTA，这需要假设第 $3$ 条提示是假的。如果假设假提示是其他某一条，则不存在与其余两条提示都一致的字符串。同样地，如果假设没有假提示，也不存在一致的字符串。

样例输入/输出 #2 的解释

唯一的可能解 $S$ 是 FINALEXAM，这需要假设没有假提示。如果假设任何一条提示是假的，则存在多于一个字符串与其余提示一致。

样例输入/输出 #3 的解释

不存在可能的解。

• 假设没有假提示：不存在与所有三条提示都一致的字符串。
• 假设第 $1$ 条提示是假的：不存在与其余两条提示都一致的字符串。
• 假设第 $2$ 条提示是假的或第 $3$ 条提示是假的：存在多于一个字符串与其余两条提示一致。

样例输入/输出 #4 的解释

存在 $2$ 个可能的解：BINOM（假设第 $2$ 条提示是假的）和 BINUS（假设第 $3$ 条提示是假的）。

翻译由 DeepSeek 完成