← 返回题目列表

Codeforces · 596/E

E. 威尔伯和弦

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

小猪威尔伯现在想玩弦乐。他找到了一个 n × m 的表,仅包含 0 到 9 的数字,其中行编号为 1 到 n,列编号为 1 到 m。威尔伯从某个方格开始并做出某些动作。如果他在方格 (x, y) 处,并且数字 d (0 ≤ d ≤ 9) 写在位置 (x, y) 处,那么他必须移动到方格 (x + ad, y + bd),如果该方格位于表内,否则他留在方格 (x, y) 中。在威尔伯采取行动之前,他可以选择是否将这个方格中写下的数字写在白板上。白板上写的所有数字形成一些字符串。每次写入新数字时,它都会到达当前字符串的末尾。

威尔伯有他担心的q 弦。对于每个字符串 si,威尔伯想知道是否存在起始位置 (x, y),以便通过进行有限多次移动,威尔伯最终可以得到白板上写下的字符串 si。

输入

输入的第一行由三个整数 n、m 和 q (1 ≤ n, m, q ≤ 200) 组成——分别是表的维度和要处理的字符串数量。

接下来的 n 行中的每一行都包含从 0 到 9 的 m 位数字,给出了表格本身。

然后执行 10 行。其中第 i 个包含值 ai - 1 和 bi - 1 (- 200 ≤ ai, bi ≤ 200),即 Wilbur 用于从包含数字 i - 1 的方格中移动的向量。

接下来有 ​​q 行。其中第 i 个将包含一个仅由 0 到 9 的数字组成的字符串 si。保证这 q 个字符串的总长度不会超过 1 000 000。

输出

对于每个 q 字符串,如果 Wilbur 可以选择 x 和 y,则打印“YES”,以便在有限次数的移动后完成该字符串。如果不可能,则为相应的字符串打印“NO”。

示例

输入 #1

1 1 2
0
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
0000000000000
2413423432432

输出 #1

YES
NO

输入 #2

4 2 5
01
23
45
67
0 1
0 -1
0 1
0 -1
0 1
0 -1
0 1
0 -1
0 1
0 -1
0000000000
010101011101
32232232322
44343222342444324
6767

输出 #2

YES
YES
YES
NO
YES

注意

在第一个示例中,有一个由唯一的数字 0 组成的 1 x 1 表。唯一可以进行的移动是停留在正方形上。第一个字符串可以通过重复写0来写在白板上。第二个字符串无法写入,因为表中没有 2。