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

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

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.