← 返回题目列表

Codeforces · 1624/E

E. 玛莎健忘

中文机器翻译题面 查看原题

玛莎遇到了一位新朋友,并得知了他的电话号码 — $$$s$$$。她想尽快记住这件事。电话号码 — 是一个长度为 $$$m$$$ 的字符串,由从 $$$0$$$ 到 $$$9$$$ 的数字组成。电话号码可能以 0 开头。

Masha 已经知道 $$$n$$$ 电话号码(所有号码的长度都相同 $$$m$$$)。如果 $$$s$$$ 表示为她已经知道的数字片段,她会更容易记住新数字。每个这样的段的长度必须至少为$$$2$$$,否则会有太多段,玛莎会感到困惑。

例如,Masha 需要记住数字:$$$s = $$$ '12345678' 并且她已经知道 $$$n = 4$$$ 数字:'12340219'、'20215601'、'56782022'、'12300678'。您可以将 $$$s$$$ 表示为 $$$3$$$ 段:第一个为“1234”,第二个为“56”,第三个为“78”。还有其他方法来表示 $$$s$$$。

玛莎向你寻求帮助,她要求你将字符串 $$$s$$$ 分成长度为 $$$2$$$ 或更多她已经知道的数字的段。如果有多个可能的答案,请打印其中任何一个。

输入

输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) – 测试用例的数量。

每个测试用例之前都有一个空行。然后有一行包含整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^3$$$) - 玛莎知道的电话号码数量以及每个电话号码的位数。然后沿着$$$n$$$行,其中第$$$i$$$描述了玛莎知道的第$$$i$$$个数字。下一行包含她的新朋友 $$$s$$$ 的电话号码。

在给定的 $$$n+1$$$ 电话中,可能存在重复的电话(相同的电话)。

保证所有输入测试用例的 $$$n \cdot m$$$ ($$$n$$$ 乘以 $$$m$$$)值之和不超过 $$$10^6$$$。

输出

您需要打印 $$$t$$$ 测试用例的答案。答案的第一行应包含一个数字 $$$k$$$,对应于您将电话号码 $$$s$$$ 分成的段数。如果无法得到这样的分割,则打印 -1。

如果答案是肯定的,则遵循包含三元组数字 $$$l、r、i$$$ 的 $$$k$$$ 行。这样的三元组意味着数字 $$$s$$$ 的接下来的 $$$r-l+1$$$ 数字等于数字 $$$i$$$ 下电话的边界 $$$[l, r]$$$ 的段(子串)。电话及其中的数字均从 $$$1$$$ 开始编号。请注意,对于所有 $$$k$$$ 行, $$$r-l+1 \ge 2$$$ 。

示例

输入 #1

5
4 8
12340219
20215601
56782022
12300678
12345678
2 3
134
126
123
1 4
1210
1221
4 3
251
064
859
957
054
4 7
7968636
9486033
4614224
5454197
9482268

输出 #1

3
1 4 1
5 6 2
3 4 3
-1
2
1 2 1
2 3 1
-1
3
1 3 2
5 6 3
3 4 1

注意

语句中的示例。

在第二种情况下,不可能用长度为 2 或更大的已知数字的线段来表示。

在第三种情况下,您可以从第一个电话号码中获取分段“12”和“21”。