Masha-forgetful solution codeforces
Masha meets a new friend and learns his phone number — 0.. She wants to remember it as soon as possible. The phone number — is a string of length that consists of digits from to . The phone number may start with
Masha already knows at least , otherwise there will be too many segments and Masha will get confused. Masha-forgetful solution codeforcesphone numbers (all numbers have the same length ). It will be easier for her to remember a new number if the is represented as segments of numbers she already knows. Each such segment must be of length
For example, Masha needs to remember the number: 12345678‘ and she already knows numbers: ‘12340219‘, ‘20215601‘, ‘56782022‘, ‘12300678‘. You can represent as a segment: ‘1234‘ of number one, ‘56‘ of number two, and ‘78‘ of number three. There are other ways to represent .‘
Masha asks you for help, she asks you to break the string any of them.into segments of length or more of the numbers she already knows. If there are several possible answers, print
The first line of input data contains an integer( ) —the number of test cases.
Before each test case there is a blank line. Then there is a line containing integersand ( ) —the number of phone numbers that Masha knows and the number of digits in each phone number. Then follow line, -th of which describes the -th number that Masha knows. The next line contains the phone number of her new friend .
Among the givenphones, there may be duplicates (identical phones).
It is guaranteed that the sum of( multiplied by ) values over all input test cases does not exceed .
You need to print the answers to -1 if you cannot get such a split.test cases. The first line of the answer should contain one number , corresponding to the number of segments into which you split the phone number . Print
If the answer is yes, then followlines containing triples of numbers . Such triplets mean that the next digits of number are equal to a segment (substring) with boundaries of the phone under number . Both the phones and the digits in them are numbered from . Note that for all lines.
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
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.