分数: 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