#P14091. [ICPC 2023 Seoul R] Magic Cards

[ICPC 2023 Seoul R] 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, N,K,MN,K,M, and FF ($1 \le N\le 500,000, 1\le K\le 100, 1 \le M\le5,000, 1 \le F\le 50,000$). In each of the following KK lines, there are MM integers between 1 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}\{\texttt Y, \texttt N\}, which represents the answer of each friend such that a Y\texttt Y means a "yes" and an N\texttt 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,,Fi=1,2,\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