Masha 的记忆片段

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

题目描述

Masha 得到了新朋友的电话号码 $s$。这个号码是一个长度为 $m$ 的数字串，并且可能以 0 开头。

Masha 已经记住了 $n$ 个长度同为 $m$ 的电话号码。她希望把 $s$ 从左到右划分成若干段，每一段的长度都不少于 $2$，且每一段都恰好是某个已知电话号码的一段连续子串。

例如，若 $s=\texttt{12345678}$，已知号码为 12340219、20215601、56782022 和 12300678，则可以依次选择第一个号码中的 1234、第二个号码中的 56 和第三个号码中的 78。

请输出任意一种合法划分；如果不存在合法划分，输出 -1。

输入格式

第一行包含一个整数 $t$，表示测试组数。

每组数据开始前可能有空白行。每组数据的第一行包含两个整数 $n,m$。

接下来 $n$ 行，每行包含一个长度为 $m$ 的数字串，表示 Masha 已知的电话号码。最后一行包含一个长度为 $m$ 的数字串 $s$，表示需要记忆的新号码。

已知号码之间以及已知号码与 $s$ 之间都可能相同。

输出格式

依次输出每组数据的答案。

如果无解，输出一行 -1。

否则，先输出一行整数 $k$，表示划分的段数；随后输出 $k$ 行，每行三个整数 $l,r,i$，表示本段取自第 $i$ 个已知电话号码中下标从 $l$ 到 $r$（均从 $1$ 开始）的连续子串。

这些子串按输出顺序拼接后必须恰好等于 $s$，并且每一段都必须满足 $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

数据范围

对于所有数据，$1\le t\le 10^4$，$1\le n,m\le 10^3$，所有字符串只包含数字，且所有测试组的 $\sum n\cdot m\le 10^6$。