用出现位置染色

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个只含小写字母的文本 $t$，以及 $n$ 个只含小写字母的字符串 $s_1,s_2,\ldots,s_n$。

一次操作中，你可以选择某个字符串 $s_i$ 在 $t$ 中的一次完整出现，并把这次出现覆盖的所有字符染成红色。每个字符串可以使用任意多次，不同操作染色的区间也可以互相重叠。

请用最少的操作把 $t$ 的每个字符都染成红色，并输出任意一种达到最少操作数的方案。如果无法完成，输出 $-1$。

输入格式

第一行包含一个整数 $q$，表示测试用例数。

每个测试用例的第一行是文本 $t$，第二行包含整数 $n$，接下来的 $n$ 行依次给出字符串 $s_1,s_2,\ldots,s_n$。

输出格式

对每个测试用例分别输出答案。

如果无法把全部字符染红，输出一行 $-1$。

否则先输出一行整数 $m$，表示最少操作次数。接下来输出 $m$ 行，每行两个整数 $w_j,p_j$，表示使用字符串 $s_{w_j}$ 覆盖从 $t$ 的第 $p_j$ 个位置开始的子串。多种最优方案可以输出任意一种，操作的输出顺序也任意。

样例输入 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

数据范围

$1\le q\le100$，$1\le|t|\le100$，$1\le n\le10$，$1\le|s_i|\le10$；所有字符串均只含小写英文字母。