题目描述

一场问答竞赛的预赛已经举行。共有 $N$ 位参赛者，编号为 $1$ 到 $N$，最多可以有 $M$ 位参赛者通过预赛。

预赛由 $K$ 道二选一的问答题组成，每道题的答案都是 o 或 x。参赛者 $i$ 对第 $j$ 题给出的回答由字符串 $S_i$ 的第 $j$ 个字符给出。第 $j$ 题的正确答案由字符串 $T$ 的第 $j$ 个字符给出。

晋级者按以下过程确定。

• 最初，晋级者与淘汰者的人数都是 $0$；$N$ 位参赛者全部处于未定状态。
• 按 $k=1,2,\dots,K$ 的顺序，依次执行以下操作。
  • 如果「晋级者人数」加上「未定参赛者中第 $k$ 题答对的人数」不超过 $M$，那么所有未定参赛者中第 $k$ 题答对的人都成为晋级者。
  • 否则，所有未定参赛者中第 $k$ 题答错的人都成为淘汰者。
• 剩余所有未定的参赛者都成为淘汰者。

你会得到 $Q$ 个如下形式的询问，请按顺序处理它们。

• 给定整数 $i$ 与 $j$。把参赛者 $i$ 对第 $j$ 题的回答从 o 改成 x，或从 x 改成 o。然后判断参赛者 $i$ 是否能通过预赛。

每个询问中对回答的改动，在处理其后的询问时同样有效。

输入格式

输入按以下格式从标准输入读入：

• $N$ $M$ $K$
• $T$
• $S_1$
• $\vdots$
• $S_N$
• $Q$
• $\mathrm{query}_1$
• $\vdots$
• $\mathrm{query}_Q$

这里，$\mathrm{query}_q$ 表示第 $q$ 个询问，其格式如下：

• $i$ $j$

输出格式

输出 $Q$ 行。第 $q$ 行在「第 $q$ 个询问中指定的参赛者通过预赛」时输出 Yes，否则输出 No。

数据范围

• $1 \leq M \leq N \leq 3\times 10^4$
• $1 \leq K \leq 200$
• $S_i$ 与 $T$ 是长度为 $K$ 的、仅由 o 与 x 组成的字符串。
• $1 \leq Q \leq 5\times 10^4$
• 对每个询问，$1\leq i \leq N$ 且 $1 \leq j \leq K$。
• 所有输入值均为整数。

5 3 3
oxo
oxo
oxx
xxo
xox
xoo
3
5 1
1 3
4 1

Yes
Yes
No

• 在第一个询问之前，参赛者 $1,2$ 在第 $1$ 题通过，参赛者 $3$ 在第 $2$ 题通过，因此晋级者是参赛者 $1,2,3$ 这三人。
• 在第一个询问之后，参赛者 $1,2,5$ 在第 $1$ 题通过，因此晋级者是参赛者 $1,2,5$ 这三人。由于参赛者 $5$ 通过了预赛，输出 Yes。
• 在第二个询问之后，参赛者 $1,2,5$ 仍然在第 $1$ 题通过，因此晋级者是参赛者 $1,2,5$ 这三人。由于参赛者 $1$ 通过了预赛，输出 Yes。
• 在第三个询问之后，参赛者 $3$ 在第 $1$ 题被淘汰，参赛者 $1,2$ 在第 $2$ 题通过，参赛者 $5$ 在第 $3$ 题通过，因此晋级者仍然是参赛者 $1,2,5$ 这三人。由于参赛者 $4$ 没有通过预赛，输出 No。

3 1 2
ox
xo
oo
ox
4
3 1
1 1
2 2
1 2

No
No
Yes
No

1 1 1
o
o
2
1 1
1 1

No
Yes

• 来源：AtCoder ABC 475 E

子任务设置

• 子任务 1（30 分）：$N \le 3000$，$K \le 30$，$Q \le 100$（允许 $O(QNK)$ 的暴力做法通过）。
• 子任务 2（30 分）：$K \le 30$ 且 $Q \le 2000$。
• 子任务 3（40 分）：无特殊限制。