|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||128 MB||0||0||0||0.000%|
Lingo is a once popular game show where the contestants have to guess words. In the original version the contestants would have to guess a five-letter word each round.
In between the rounds of regular word guessing, the contestants can win a bonus prize if they can guess a ten-letter word. The ten-letter word is displayed with the letters permuted. Some letters are colored indicating that they are displayed in the right position. Since there are not that many ten-letter words, it happens frequently that the word is actually a compound: a word constructed by concatenating two shorter words. In this problem we assume that the ten-letter word is always of this form.
Given a dictionary and a sequence of ten letters, you must calculate the possible solutions to the ten-letter word game. Two solutions are considered different if they are constructed from different parts, even if their concatenation is the same. This is illustrated by the the second sample case.
On the first line an integer t (1 ≤ t ≤ 100): the number of test cases. Then for each test case:
All words in the dictionary for a single test case are distinct.
For each test case, output for each query:
The solutions to a single query must be ordered lexicographically. If the number of solutions exceeds 1000, then only output the first 1000 solutions.
2 5 gunner integral relating tail un 4 TAILGUNNER unINTEGRAL UNrelating IMPOSSIBLE 3 aaaa aaaaa aaaaaa 1 AAAAAAAAAA
6 gunner-tail integral-un relating-un tail-gunner un-integral un-relating 2 un-integral un-relating 1 un-relating 0 3 aaaa-aaaaaa aaaaa-aaaaa aaaaaa-aaaa
If s and t are strings of equal length and si denotes the ith character of s, then s precedes t lexicographically if for some i: si < ti and sj = tj for all j < i. In this problem statement, the hyphen precedes all letters lexicographically.