#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 and , and don't tell me your number. Just keep it in your mind." Junsu chose 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 ." 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 magic cards in each of which exactly integers between and , possibly with some redundancy, are written, and you perform the magic trick to friends. From the yes/no-sequences from the 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, , and ($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 lines, there are integers between 1 and , which represent the numbers written in each magic card. In each of the following lines, you are given a string of length over , which represents the answer of each friend such that a means a "yes" and an 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 lines. For each , the -th line should consists of the number in the -th friend's mind. If it is impossible to identify the one and only number of the -th friend, print out 0
in the -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