401570: GYM100495 B Don't swear!

Memory Limit:256 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Don't swear!time limit per test0.25 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Povilas is developing a social network called "Dwidder". He almost have it finished. However, there is one major problem. Povilas is very polite and he would never publish swear words. But you can't say that about other users of "Dwidder".

Povilas has almost solved this problem. He already prepared a dictionary which contains all the swear words. He will check every message word by word and see if any of the words are in the dictionary.

However, "Dwidder" users are pretty smart. They know that if you leave the first and last letter in place and shuffle the inside ones, the word will remain readable. For elamxpe, you can raed tihs snetence, dno't you? "Dwidder" users are not afraid to use this ability for the worse.

Povilas needs your help. He is giving you the dictionary and the words from the message. You must tell if there are swear words in the message, even if the inside letters are shuffled.

Input

The first line contains the number of test cases T (T ≤ 10). In the first line of every test case there are numbers n and m (1 ≤ n, m ≤ 1000) — the size of the dictionary and the count of words in the message. In the following line there are n strings — words from the dictionary — separated by a single space. In the next line there are m strings — words from the message — separated by a single space. Every word consists of lowercase English letters and none of them are longer than 10 characters.

Output

For each test case output one line containing “Case #tc: s”, where tc is the number of the test case (starting from 1) and s is a string consisting of zeroes and ones. The i-th character of the string corresponds to the i-th word from the message, '1' meaning that the word is a swear word and '0' that it's not.

ExamplesInput
1
2 5
pig goat
pig gaot peg goat gota
Output
Case #1: 11010

加入题单

上一题 下一题 算法标签: