Magic Cards

문제

Chansu and Junsu are friends in International College of Programming Convergence. One day, Chansu met Junsu and said that “I’ll do a magic trick for you. Pick any number between $11$ and $1212$, and don’t tell me your number. Just keep it in your mind.” Junsu chose $1111$ in mind. Chansu then showed Junsu the following four cards one by one, asking “Is there your number in this card?” at each time.

So, Junsu answered “Yes, yes, no, yes” in this order. After Chansu did some magically looking gestures with his arms and legs for a while, he finally shouted, “I’ve got your number. It is $1111$.” And Junsu was quite surprised because it was exactly the number he kept in mind.

Chansu didn’t tell Junsu the secret of the trick, but only “These cards have a great magic power, so they can read your mind and tell me something only in a magical language, which only I can understand.”

How does this work? Can you figure out the secret?

Now, you are to write a program that answers the number in your friends’ minds. We can generalize the magic trick as follows: You have $KK$ magic cards in each of which exactly $MM$ integers between $11$ and $NN$, possibly with some redundancy, are written, and you perform the magic trick to $FF$ friends. From the yes/no-sequences from the $FF$ friends, you will be able to pick out the correct numbers.

입력

Your program is to read from standard input. The input starts with a line containing four integers, $NN$, $KK$, $MM$, and $FF$ (1 ≤ N ≤ 500\,000, 1 ≤ K ≤ 100, 1 ≤ M ≤ 5\,000, 1 ≤ F ≤ 50\,000). In each of the following $KK$ lines, there are $MM$ integers between $11$ and $NN$, which represent the $MM$ numbers written in each magic card. In each of the following $FF$ lines, you are given a string of length $KK$ over {Y, N}, which represents the answer of each friend such that a Y means a “yes” and an N means a “no”. You can assume that all the answers from the friends are correctly given according to their numbers chosen in mind.

출력

Your program is to write to standard output. Print exactly $FF$ lines. For each $i=1,2,\dots ,Fi\; =\; 1,2,\; \backslash dots\; ,\; F$, the $ii$-th line should consists of the number in the $ii$-th friend’s mind. If it is impossible to identify the one and only number of the $ii$-th friend, print out 0 in the $ii$-th line.

12 4 6 3
1 9 7 11 3 5
2 10 3 6 7 11
4 5 6 7 6 12
8 11 10 9 12 9
YYNY
NNNY
YNNN

11
8
1

13 4 6 4
1 9 7 11 3 5
2 10 3 6 7 11
4 5 6 7 6 12
8 11 10 9 12 9
YYNY
NNNY
YNNN
NNNN

11
8
1
13

14 4 6 4
1 9 7 11 3 5
2 10 3 6 7 11
4 5 6 7 6 12
8 11 10 9 12 9
YYNY
NNNY
YNNN
NNNN

11
8
1
0