Chinese knot is a decorative handicraft that began as a form of Chinese folk artifact in the Tang and Song Dynasty in China. It was later popularized in the Ming.
Alice is learning Chinese knotting. To take the first step, she went to the store and bought a string. To her surprise, she found the string was composed of characters! Anyway, she made a simple Chinese knot. It consists of one knot with 4 loops:
Look at the picture above. There are four loops connected at the center black knot. To make the image clear and neat, the characters on the string are shown as red and yellow points. As a Mid-Autumn Festival gift, Alice give this handcrafted Chinese knot to you. Then she asked you a question:
You are given a target character sequence. Can you get the sequence by walking on the knot? "Walking on the knot" means:
You can start at any point you want.
You can not start at or move to the black knot in the center.
Each step, you can only move to an adjacent point, except for the point you came from immediately.
The 8 points closely around the black knot are adjacent to each other. For example, in the picture above, they are the 8 yellow points adjacent to the black knot.
Your path should not contain three continuous points which are both one of the 8 points mentioned above.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains two integers N and M (3 <= N, M <= 100000). The total length of string that Alice bought from store is 4 * N.
Then followed by 4 lines, each line contains N lower case letters as a loop of the Chinese knot. These characters are indexed from 1 to 4 * N corresponding to the input order.
The next line contains M lower case letters indicating the target character sequence.
Output
For each test case, output the M indexes of characters you visited. If there are multiple solutions, output any one. If there is no solution, output "No solution!" instead.
Sample Input
2
3 3
abc
abc
abc
abc
baa
3 3
abc
abc
abc
abc
bab
Sample Output
2 1 4
No solution!
