给你一些文本 $$$t$$$ 和一组 $$$n$$$ 字符串 $$$s_1, s_2, \dots, s_n$$$。
在一步中,您可以选择文本 $$$t$$$ 中任意出现的任意字符串 $$$s_i$$$,并将文本中相应的字符着色为红色。例如,如果 $$$t=\texttt{bababa}$$$ 和 $$$s_1=\texttt{ba}$$$、$$$s_2=\texttt{aba}$$$,则可以得到 $$$t=\color{red}{\texttt{ba}}\texttt{baba}$$$, $$$t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$$$ 或 $$$t=\texttt{bab}\color{red}{\texttt{aba}}$$$ 一步完成。
您想要将文本 $$$t$$$ 的所有字母着色为红色。当您再次将字母涂成红色时,它会保持红色。
在上面的示例中,三个步骤就足够了:
- 让我们将 $$$t[2 \dots 4]=s_2=\texttt{aba}$$$ 涂成红色,我们得到 $$$t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$$$;
- 让我们将 $$$t[1 \dots 2]=s_1=\texttt{ba}$$$ 涂成红色,我们得到 $$$t=\color{red}{\texttt{baba}}\texttt{ba}$$$;
- 让我们将 $$$t[4 \dots 6]=s_2=\texttt{aba}$$$ 涂成红色,我们得到 $$$t=\color{red}{\texttt{bababa}}$$$。
每个字符串 $$$s_i$$$ 可以应用任意次(或根本不应用)。着色的出现可以任意交叉。
确定将所有字母 $$$t$$$ 涂成红色所需的最少步骤数以及如何操作。如果无法将文本 $$$t$$$ 的所有字母着色为红色,则输出 -1。
输入
输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 100$$$) - 测试中的测试用例数量。
测试用例的描述如下。
每个测试用例的第一行包含文本 $$$t$$$ ($$$1 \le |t| \le 100$$$),仅由小写拉丁字母组成,其中 $$$|t|$$$ 是文本 $$$t$$$ 的长度。
每个测试用例的第二行包含一个整数 $$$n$$$ ($$$1 \le n \le 10$$$) — 集合中字符串的数量。
接下来是 $$$n$$$ 行,每行包含一个仅由小写拉丁字母组成的字符串 $$$s_i$$$ ($$$1 \le |s_i| \le 10$$$),其中 $$$|s_i|$$$ — 字符串 $$$s_i$$$ 的长度。
输出
对于每个测试用例,将答案打印在单独的行上。
如果无法将文本中的所有字母着色为红色,请打印包含数字 -1 的单行。
否则,在第一行打印数字 $$$m$$$ — 将所有字母 $$$t$$$ 变成红色所需的最少步骤数。
然后在接下来的 $$$m$$$ 行中打印索引对:$$$w_j$$$ 和 $$$p_j$$$ ($$$1 \le j \le m$$$),这表示索引为 $$$w_j$$$ 的字符串被用作子字符串来覆盖从位置 $$$p_j$$$ 开始的文本 $$$t$$$ 中出现的情况。这些对可以按任何顺序输出。
如果有多个答案,则输出其中任何一个。
示例
输入 #1
6 bababa 2 ba aba caba 2 bac acab abacabaca 3 aba bac aca baca 3 a c b codeforces 4 def code efo forces aaaabbbbcccceeee 4 eeee cccc aaaa bbbb
输出 #1
3 2 2 1 1 2 4 -1 4 1 1 2 6 3 3 3 7 4 3 1 1 2 2 3 1 4 2 4 5 2 1 4 3 1 4 5 2 9 1 13
注意
第一个测试用例在问题陈述中进行了解释。
在第二个测试用例中,不可能将文本的所有字母都涂成红色。