A - Password Verification Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君はあるシステムの管理者です。このシステムにログインするためには、長さ N の英小文字からなるパスワードを正しく入力する必要があります。

しかし、サーバーの障害により、パスワードを保存していたデータの一部が破損してしまいました。幸い、パスワードの M 文字分は復旧に成功しました。具体的には、i 番目（1 \leq i \leq M）の復旧データとして、パスワードの P_i 文字目が文字 C_i であることが判明しています。それ以外の位置の文字は不明です。

高橋君は応急処置として、以下のようにパスワード照合システムを修正しました：

  • 入力された長さ N の文字列の各位置 j（1 \leq j \leq N）について、位置 j のデータが復旧されている場合（すなわち、ある i に対して P_i = j である場合）、入力文字列の j 文字目が C_i と一致しているかを確認する。
  • 位置 j のデータが復旧されていない場合、その位置はどんな文字でも受理する。
  • すべての復旧済み位置で文字が一致していれば、パスワードは正しいと判定する。

青木君がこのシステムにログインを試みており、Q 個の候補文字列 T_1, T_2, \ldots, T_Q を用意しています。それぞれの候補文字列について、パスワードとして正しいと判定されるかどうかを判定してください。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq N
  • 1 \leq Q \leq 10^3
  • 1 \leq P_i \leq N
  • P_i はすべて互いに異なる
  • C_i は英小文字
  • 各 T_j は長さ N の英小文字からなる文字列

入力

N M Q
P_1 C_1
P_2 C_2
\vdots
P_M C_M
T_1
T_2
\vdots
T_Q
  • 1 行目には、パスワードの長さを表す整数 N、復旧できた文字数を表す整数 M、候補文字列の数を表す整数 Q が、スペース区切りで与えられる。
  • 続く M 行では、復旧できた各文字の情報が与えられる。M = 0 の場合、この部分は存在しない。
  • このうち i 行目（1 \leq i \leq M）では、復旧データの位置を表す整数 P_i（1 以上 N 以下）と、その位置の英小文字 C_i が、スペース区切りで与えられる。
  • すべての P_i は互いに異なる。
  • 続く Q 行では、青木君が試す候補文字列が 1 行に 1 つずつ与えられる。
  • このうち j 行目（1 \leq j \leq Q）には、長さ N の英小文字からなる文字列 T_j が与えられる。

出力

Q 行出力せよ。j 行目には、候補文字列 T_j がパスワードとして正しいと判定される場合は Yes を、そうでない場合は No を出力せよ。

入力例 1

5 2 3
1 a
4 d
abcde
xbcde
abcdz

出力例 1

Yes
No
Yes

入力例 2

3 0 2
abc
xyz

出力例 2

Yes
Yes

入力例 3

10 4 5
2 b
5 e
7 g
10 z
abcdefghiz
xbxdexgxxz
abcdeagxyz
xbxdexhxxz
abcdefghij

出力例 3

Yes
Yes
Yes
No
No

Score : 266 pts

Problem Statement

Takahashi is the administrator of a certain system. To log in to this system, one must correctly enter a password consisting of lowercase English letters of length N.

However, due to a server failure, part of the data storing the password has been corrupted. Fortunately, M characters of the password were successfully recovered. Specifically, for the i-th (1 \leq i \leq M) piece of recovered data, it is known that the P_i-th character of the password is the character C_i. The characters at all other positions are unknown.

As a temporary fix, Takahashi modified the password verification system as follows:

  • For each position j (1 \leq j \leq N) of the input string of length N: if the data at position j has been recovered (that is, P_i = j for some i), check whether the j-th character of the input string matches C_i.
  • If the data at position j has not been recovered, any character is accepted at that position.
  • If the characters match at all recovered positions, the password is judged to be correct.

Aoki is attempting to log in to this system and has prepared Q candidate strings T_1, T_2, \ldots, T_Q. For each candidate string, determine whether it would be judged as a correct password.

Constraints

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq N
  • 1 \leq Q \leq 10^3
  • 1 \leq P_i \leq N
  • All P_i are distinct
  • C_i is a lowercase English letter
  • Each T_j is a string of length N consisting of lowercase English letters

Input

N M Q
P_1 C_1
P_2 C_2
\vdots
P_M C_M
T_1
T_2
\vdots
T_Q
  • The first line contains three space-separated integers: N representing the length of the password, M representing the number of recovered characters, and Q representing the number of candidate strings.
  • The following M lines give information about each recovered character. If M = 0, this part does not exist.
  • The i-th line (1 \leq i \leq M) contains a space-separated integer P_i (1 or greater and N or less) representing the position of the recovered data, and a lowercase English letter C_i at that position.
  • All P_i are distinct.
  • The following Q lines give the candidate strings that Aoki will try, one per line.
  • The j-th line (1 \leq j \leq Q) contains a string T_j of length N consisting of lowercase English letters.

Output

Output Q lines. On the j-th line, output Yes if the candidate string T_j is judged to be a correct password, and No otherwise.

Sample Input 1

5 2 3
1 a
4 d
abcde
xbcde
abcdz

Sample Output 1

Yes
No
Yes

Sample Input 2

3 0 2
abc
xyz

Sample Output 2

Yes
Yes

Sample Input 3

10 4 5
2 b
5 e
7 g
10 z
abcdefghiz
xbxdexgxxz
abcdeagxyz
xbxdexhxxz
abcdefghij

Sample Output 3

Yes
Yes
Yes
No
No