P14091 [ICPC 2023 Seoul R] Magic Cards

Chansu 和 Junsu 是国际编程融合学院的朋友。一天，Chansu 遇见 Junsu，并说：“我给你表演一个魔术。你在 $1$ 到 $12$ 之间挑一个数字，不要告诉我，只记在心里。”Junsu 心里选了 $11$。Chansu 随后依次给 Junsu 展示了下图中的四张卡片，每次都问：“你的数字出现在这张卡片中吗？”。  所以，Junsu 按顺序回答了：“是，是，否，是”。Chansu 做了一些神秘的手势和动作后，最终喊道：“我知道你的数字了，是 $11$。”这让 Junsu 非常吃惊，因为这正是他心里想的数字。 Chansu 没有告诉 Junsu 魔术的秘密，只说：“这些卡片有很强的魔法力量，它们能读懂你的心思，并用只有我能明白的魔法语言告诉我一些事情。” 这是如何做到的？你能揭秘这个魔术的原理吗？ 现在，你需要编写一个程序，来回答朋友们心中的数字。我们可以将魔术的一般情形归纳如下：你有 $K$ 张魔法卡片，每张卡片上写有恰好 $M$ 个 $1$ 到 $N$ 之间的整数（可能有重复），你要为 $F$ 个朋友表演魔术。通过 $F$ 个朋友对应的“是/否”序列，你要找出他们心中的数字。

你的程序需要从标准输入读取数据。输入的第一行包含四个整数 $N,K,M,F$（$1 \le N \le 500,000,\ 1 \le K \le 100,\ 1 \le M \le 5,000,\ 1 \le F \le 50,000$）。接下来的 $K$ 行，每行有 $M$ 个 $1$ 到 $N$ 的整数，表示每张魔法卡片上写下的数字。再接下来的 $F$ 行，每行是长度为 $K$ 的只包含 $\texttt Y$ 和 $\texttt N$ 的字符串，表示每个朋友的回答，$\texttt Y$ 代表“是”，$\texttt N$ 代表“否”。你可以假定所有朋友的回答都与他们所选的数字严格对应。

你的程序要输出 $F$ 行。对于每个 $i=1,2,\dots,F$，第 $i$ 行应输出第 $i$ 个朋友心里的数字。如果无法唯一确定某个朋友的数字，则在该行输出 $0$。

由 ChatGPT 5 翻译