GCD Table

题意翻译

一张$n\times m$ 的表,第$i$ 行第$j$ 列是$GCD(i,j)$ 你有一个长度为$k$ 的数列$a$ ,询问是否存在$i,j$ ,满足对任意的$l$ ,均有$GCD(i,j+l-1)=a_l(1\leq l\leq k)$ 。 Translated by Fheiwn

题目描述

Consider a table $ G $ of size $ n×m $ such that $ G(i,j)=GCD(i,j) $ for all $ 1<=i<=n,1<=j<=m $ . $ GCD(a,b) $ is the greatest common divisor of numbers $ a $ and $ b $ . You have a sequence of positive integer numbers $ a_{1},a_{2},...,a_{k} $ . We say that this sequence occurs in table $ G $ if it coincides with consecutive elements in some row, starting from some position. More formally, such numbers $ 1<=i<=n $ and $ 1<=j<=m-k+1 $ should exist that $ G(i,j+l-1)=a_{l} $ for all $ 1<=l<=k $ . Determine if the sequence $ a $ occurs in table $ G $ .

输入输出格式

输入格式


The first line contains three space-separated integers $ n $ , $ m $ and $ k $ ( $ 1<=n,m<=10^{12} $ ; $ 1<=k<=10000 $ ). The second line contains $ k $ space-separated integers $ a_{1},a_{2},...,a_{k} $ ( $ 1<=a_{i}<=10^{12} $ ).

输出格式


Print a single word "YES", if the given sequence occurs in table $ G $ , otherwise print "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

说明

Sample 1. The tenth row of table $ G $ starts from sequence {1, 2, 1, 2, 5, 2, 1, 2, 1, 10}. As you can see, elements from fifth to ninth coincide with sequence $ a $ . Sample 2. This time the width of table $ G $ equals 8. Sequence $ a $ doesn't occur there.