Contents
Mashaforgetful solution codeforces

For Solution
Click Here!
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. Mashaforgetful 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.
The first line of input data contains an integer tt (1≤t≤1041≤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 (1≤n,m≤1031≤n,m≤103) —the number of phone numbers that Masha knows and the number of digits in each phone number. Then follow nn line, iith of which describes the iith 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 n⋅mn⋅m (nn multiplied by mm) values over all input test cases does not exceed 106106.
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 r−l+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 r−l+1≥2r−l+1≥2 for all kk lines.
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
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
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.

For Solution
Click Here!