ZOJ Problem Set - 3817
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:
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.
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.
2 3 3 abc abc abc abc baa 3 3 abc abc abc abc bab
2 1 4 No solution!
In the first case, we start at the second character of the first loop and stop at the first character of the second loop.
Author: CHEN, Weijie
Source: The 2014 ACM-ICPC Asia Mudanjiang Regional First Round