/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 475 点
問題文
クイズ大会の予選が行われました。参加者は 1 から N の番号がついた N 人で、予選を通過できるのは最大で M 人です。
予選は K 問の 2 択クイズからなり、各問題の答えは 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 が予選通過できるかどうかを判定する。
なお各クエリにおける回答変更は以降のクエリを処理する際にも残り続けます。
制約
- 1 \leq M \leq N \leq 3\times 10^4
- 1 \leq K \leq 200
- S_i,T は
o,xのみからなる長さ K の文字列 - 1 \leq Q \leq 5\times 10^4
- 各クエリについて、1\leq i \leq N、1 \leq j \leq K
入力
入力は以下の形式で標準入力から与えられる。
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
5 3 3 oxo oxo oxx xxo xox xoo 3 5 1 1 3 4 1
出力例 1
Yes Yes No
- 1 番目のクエリが来る前の時点では、 1 問目で参加者 1,2 が通過、 2 問目で参加者 3 が通過し、予選通過者は参加者 1,2,3 の 3 人です。
- 1 番目のクエリのあと、1 問目で参加者 1,2,5 が通過し、予選通過者は参加者 1,2,5 の 3 人になります。参加者 5 は予選通過するので
Yesを出力します。 - 2 番目のクエリのあと、変わらず 1 問目で参加者 1,2,5 が通過し、予選通過者は参加者 1,2,5 の 3 人です。参加者 1 は予選通過するので
Yesを出力します。 - 3 番目のクエリのあと、1 問目で参加者 3 が脱落、2 問目で参加者 1,2 が通過、3 問目で参加者 5 が通過し、予選通過者は変わらず参加者 1,2,5 の 3 人です。参加者 4 は予選通過しないので
Noを出力します。
入力例 2
3 1 2 ox xo oo ox 4 3 1 1 1 2 2 1 2
出力例 2
No No Yes No
入力例 3
1 1 1 o o 2 1 1 1 1
出力例 3
No Yes
Score : 475 points
Problem Statement
A preliminary round of a quiz competition was held. There are N participants, numbered 1 to N, and at most M of them can pass the preliminary round.
The preliminary round consists of K two-choice quiz questions, and the answer to each question is o or x.
Participant i's answer to the j-th question is given as the j-th character of the string S_i.
The correct answer to the j-th question is given as the j-th character of the string T.
The qualifiers are determined by the following procedure.
- Initially, the numbers of qualifiers and non-qualifiers are both 0; all N participants are undetermined.
- For k=1,2,\dots,K in this order, perform the following process.
- If the number of qualifiers plus the number of undetermined participants who answered the k-th question correctly is at most M, then all undetermined participants who answered the k-th question correctly become qualifiers.
- Otherwise, all undetermined participants who answered the k-th question incorrectly become non-qualifiers.
- All remaining undetermined participants become non-qualifiers.
You are given Q queries in the following format. Process them in order.
- Integers i and j are given. Change participant i's answer to the j-th question from
otox, or fromxtoo. Then, determine whether participant i passes the preliminary round.
The change of the answer in each query remains in effect when processing subsequent queries as well.
Constraints
- 1 \leq M \leq N \leq 3\times 10^4
- 1 \leq K \leq 200
- S_i and T are strings of length K consisting of
oandx. - 1 \leq Q \leq 5\times 10^4
- For each query, 1\leq i \leq N and 1 \leq j \leq K.
Input
The input is given from Standard Input in the following format:
N M K
T
S_1
\vdots
S_N
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q
Here, \mathrm{query}_q represents the q-th query, and is given in the following format:
i j
Output
Output Q lines.
The q-th line should contain Yes if the participant specified in the q-th query passes the preliminary round, and No otherwise.
Sample Input 1
5 3 3 oxo oxo oxx xxo xox xoo 3 5 1 1 3 4 1
Sample Output 1
Yes Yes No
- Before the first query, participants 1,2 pass on the first question and participant 3 passes on the second question, so the qualifiers are the three participants 1,2,3.
- After the first query, participants 1,2,5 pass on the first question, so the qualifiers are the three participants 1,2,5. Since participant 5 passes the preliminary round, output
Yes. - After the second query, participants 1,2,5 still pass on the first question, so the qualifiers are the three participants 1,2,5. Since participant 1 passes the preliminary round, output
Yes. - After the third query, participant 3 is eliminated on the first question, participants 1,2 pass on the second question, and participant 5 passes on the third question, so the qualifiers remain the three participants 1,2,5. Since participant 4 does not pass the preliminary round, output
No.
Sample Input 2
3 1 2 ox xo oo ox 4 3 1 1 1 2 2 1 2
Sample Output 2
No No Yes No
Sample Input 3
1 1 1 o o 2 1 1 1 1
Sample Output 3
No Yes