← 返回题目列表

AtCoder · awc0039_a

A. 密码验证

中文机器翻译题面 查看原题

分数: 266 分

问题陈述

高桥是某个系统的管理员。登录本系统必须正确输入由小写英文字母组成的密码 N.

然而,由于服务器故障,存储密码的部分数据已损坏。幸运的是, M 字符的密码已成功恢复。具体来说,对于 i-th (1 \leq i \leq M)恢复的数据,已知 P_i密码的第一个字符是字符 C_i。所有其他位置的字符均未知。

作为临时修复,高桥修改了密码验证系统如下:

  • 对于每个位置 j (1 \leq j \leq N) 的输入字符串长度 N:如果位置上的数据 j 已恢复(即 P_i = j 对于一些 i),检查是否 j输入字符串的第一个字符匹配 C_i.
  • 如果位置上的数据 j 尚未恢复,该位置接受任何字符。
  • 如果所有恢复位置的字符都匹配,则判断密码正确。

Aoki 正在尝试登录此系统并已准备好 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
  • 第一行包含三个空格分隔的整数: N 代表密码的长度, M 代表恢复的字符数,以及 Q 表示候选字符串的数量。
  • 以下 M 行提供有关每个恢复字符的信息。如果 M = 0,这部分不存在。
  • 的 树的 i- 第行 (1 \leq i \leq M) 包含一个空格分隔的整数 P_i (1 或更大并且 N 或更小)代表恢复数据的位置,小写英文字母 C_i 在那个位置。
  • 全部 P_i 是不同的。
  • 以下 Q 行给出 Aoki 将尝试的候选字符串,每行一个。
  • 的 树的 j- 第行 (1 \leq j \leq Q) 包含一个字符串 T_j 长度 N 由小写英文字母组成。

输出

输出 Q 行。上 j第行,输出 Yes 如果候选字符串 T_j 被判断为正确的密码,并且 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