CF1624E.Masha-forgetful

Masha meets a new friend and learns his phone number — $s$. She wants to remember it as soon as possible. The phone number — is a string of length $m$ that consists of digits from $0$ to $9$. The phone number may start with 0.

Masha already knows $n$ phone numbers (all numbers have the same length $m$). It will be easier for her to remember a new number if the $s$ is represented as segments of numbers she already knows. Each such segment must be of length at least $2$, otherwise there will be too many segments and Masha will get confused.

For example, Masha needs to remember the number: $s = $ '12345678' and she already knows $n = 4$ numbers: '12340219', '20215601', '56782022', '12300678'. You can represent $s$ as a $3$ segment: '1234' of number one, '56' of number two, and '78' of number three. There are other ways to represent $s$.

Masha asks you for help, she asks you to break the string $s$ into segments of length $2$ or more of the numbers she already knows. If there are several possible answers, print any of them.

玛莎结识了一位新朋友，并得知了他的电话号码——$s$。她希望尽快记住这个号码。该电话号码是一个长度为 $m$ 的字符串，仅由数字 $0$ 到 $9$ 组成，且可能以 $0$ 开头。

玛莎已经记住了 $n$ 个电话号码（所有号码长度均为 $m$）。如果新号码 $s$ 能被表示为若干她已知号码的连续子串（即“段”），那么她将更容易记住它。每个这样的段长度至少为 $2$；否则段数过多，玛莎会感到困惑。

例如，玛莎需要记住号码：$s = $ '12345678'，而她已知 $n = 4$ 个号码：'12340219'、'20215601'、'56782022'、'12300678'。我们可以将 $s$ 表示为 $3$ 段：取第一个已知号码中的 '1234'，第二个已知号码中的 '56'，以及第三个已知号码中的 '78'。此外还有其他可行的表示方式。

玛莎请你帮忙：将字符串 $s$ 划分为若干长度不小于 $2$ 的段，使得每一段均出现在她已知的某个电话号码中（即为该号码的连续子串）。若存在多种方案，输出任意一种即可。

The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) —the number of test cases.

Before each test case there is a blank line. Then there is a line containing integers $n$ and $m$ ($1 \le n, m \le 10^3$) —the number of phone numbers that Masha knows and the number of digits in each phone number. Then follow $n$ line, $i$-th of which describes the $i$-th number that Masha knows. The next line contains the phone number of her new friend $s$.

Among the given $n+1$ phones, there may be duplicates (identical phones).

It is guaranteed that the sum of $n \cdot m$ ($n$ multiplied by $m$) values over all input test cases does not exceed $10^6$.

输入数据的第一行包含一个整数 $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$。

You need to print the answers to $t$ test cases. The first line of the answer should contain one number $k$, corresponding to the number of segments into which you split the phone number $s$. Print -1 if you cannot get such a split.

If the answer is yes, then follow $k$ lines containing triples of numbers $l, r, i$. Such triplets mean that the next $r-l+1$ digits of number $s$ are equal to a segment (substring) with boundaries $[l, r]$ of the phone under number $i$. Both the phones and the digits in them are numbered from $1$. Note that $r-l+1 \ge 2$ for all $k$ lines.

你需要输出 $t$ 个测试用例的答案。答案的第一行应包含一个数字 $k$，表示将电话号码 $s$ 划分为多少段。若无法得到满足条件的划分，则输出 -1。

若存在可行解，则接下来输出 $k$ 行，每行包含三个数字 $l, r, i$。这样的三元组表示：电话号码 $s$ 中接下来的 $r-l+1$ 位数字，恰好等于编号为 $i$ 的电话号码中下标范围为 $[l, r]$ 的子串（即一段连续的数字）。所有电话号码及其内部的数字均从 $1$ 开始编号。注意：对所有 $k$ 行，均有 $r-l+1 \ge 2$。

The example from the statement.

In the second case, it is impossible to represent by segments of known numbers of length 2 or more.

In the third case, you can get the segments '12' and '21' from the first phone number.

题目描述中的示例。

在第二种情况下，无法用已知数字组成的、长度不小于 2 的线段来表示。

在第三种情况下，你可以从第一个电话号码中得到线段 “12” 和 “21”。