玛莎遇到了一位新朋友,并得知了他的电话号码 — $$$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”。