← 返回题目列表

Codeforces · 338/D

D. GCD 表

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

考虑一个大小为 n × m 的表 G,对于所有 1 ≤ i ≤ n、1 ≤ j ≤ m,G(i, j) = GCD(i, j)。 GCD(a, b) 是数字 a 和 b 的最大公约数。

您有一个正整数序列 a1, a2, ..., ak。如果这个序列与某行中从某个位置开始的连续元素重合,我们就说这个序列出现在表 G 中。更正式地说,这样的数字 1 ≤ i ≤ n 和 1 ≤ j ≤ m - k + 1 应该存在,对于所有 1 ≤ l ≤ k,G(i, j + l - 1) = al。

判断序列a是否出现在表G中。

输入

第一行包含三个空格分隔的整数 n、m 和 k (1 ≤ n, m ≤ 1012; 1 ≤ k ≤ 10000)。第二行包含 k 个空格分隔的整数 a1, a2, ..., ak (1 ≤ ai ≤ 1012)。

输出

如果给定序列出现在表 G 中,则打印单个单词“YES”,否则打印“NO”。

示例

输入 #1

100 100 5
5 2 1 2 1

输出 #1

YES

输入 #2

100 8 5
5 2 1 2 1

输出 #2

NO

输入 #3

100 100 7
1 2 3 4 5 6 7

输出 #3

NO

注意

示例 1。表 G 的第十行从序列 {1, 2, 1, 2, 5, 2, 1, 2, 1, 10} 开始。如您所见,第五到第九个元素与序列 a 重合。

样本 2。这次表 G 的宽度等于 8。那里没有出现序列 a。