Masha-forgetful

Description:

Input:

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$$$.

Output:

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.

Sample Input:

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

Sample Output:

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

Note:

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.