Masha meets a new friend and learns his phone number — ss. She wants to remember it as soon as possible. The phone number — is a string of length mm that consists of digits from 00 to 99. The phone number may start with 0. Masha already knows nn phone numbers (all numbers have the same length mm). It will be easier for her to remember a new number if the ss is represented as segments of numbers she already knows. Each such segment must be of length at least 22, otherwise there will be too many segments and Masha will get confused. Masha-forgetful solution codeforces For example, Masha needs to remember the number: s=s= ‘12345678’ and she already knows n=4n=4 numbers: ‘12340219’, ‘20215601’, ‘56782022’, ‘12300678’. You can represent ss as a 33 segment: ‘1234’ of number one, ’56’ of number two, and ’78’ of number three. There are other ways to represent ss.

Masha-forgetful solution codeforces

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

Masha already knows nn phone numbers (all numbers have the same length mm). It will be easier for her to remember a new number if the ss is represented as segments of numbers she already knows. Each such segment must be of length at least 22, otherwise there will be too many segments and Masha will get confused. Masha-forgetful solution codeforces

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

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

Input Masha-forgetful solution codeforces

The first line of input data contains an integer tt (1t1041≤t≤104) —the number of test cases.

Before each test case there is a blank line. Then there is a line containing integers nn and mm (1n,m1031≤n,m≤103) —the number of phone numbers that Masha knows and the number of digits in each phone number. Then follow nn line, ii-th of which describes the ii-th number that Masha knows. The next line contains the phone number of her new friend ss.

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

It is guaranteed that the sum of nmn⋅m (nn multiplied by mm) values over all input test cases does not exceed 106106.

Output Masha-forgetful solution codeforces

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

If the answer is yes, then follow kk lines containing triples of numbers l,r,il,r,i. Such triplets mean that the next rl+1r−l+1 digits of number ss are equal to a segment (substring) with boundaries [l,r][l,r] of the phone under number ii. Both the phones and the digits in them are numbered from 11. Note that rl+12r−l+1≥2 for all kk lines.

Example

input

Copy Masha-forgetful solution codeforces
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

output

Copy Masha-forgetful solution codeforces
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.

Leave a Comment

Your email address will not be published. Required fields are marked *