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.


-----Input-----

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).


-----Output-----

Print a single word "YES", if the given sequence occurs in table G, otherwise print "NO".


-----Examples-----
Input
100 100 5
5 2 1 2 1

Output
YES

Input
100 8 5
5 2 1 2 1

Output
NO

Input
100 100 7
1 2 3 4 5 6 7

Output
NO



-----Note-----

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.

Difficulty: VERY_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def ext(a, b):
	if b == 0:
		return (1, 0)
	else:
		(y, x) = ext(b, a % b)
		y = y - a // b * x
		return (x, y)
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
lcm = 1
for i in a:
	lcm = lcm * i // gcd(lcm, i)
	if lcm > n:
		print('NO')
		exit()
j = 0
m1 = 1
s = True
for i in range(k):
	(x, y) = ext(m1, a[i])
	res = m1 * x + a[i] * y
	if (-i - j) % res != 0:
		s = False
		break
	res = (-i - j) // res
	(x, y) = (x * res, y * res)
	j += m1 * x
	t = m1 * a[i]
	if j > t:
		j -= j // t * t
	if j < 0:
		j += (-j + t - 1) // t * t
	if j == 0:
		j = t
	m1 = m1 * a[i] // gcd(m1, a[i])
if j + k - 1 > m or s == False:
	print('NO')
	exit()
b = [gcd(lcm, j + i) for i in range(k)]
for i in range(k):
	if a[i] != b[i]:
		print('NO')
		exit()
print('YES')


from math import gcd

def LCM(a, b):
	if min(a, b) == 0:
		return max(a, b)
	return a // gcd(a, b) * b

class Eqn:

	def __init__(self, r, mod):
		self.r = r
		self.mod = mod

def bye():
	print('NO')
	exit(0)

def exgcd(a, b):
	if b == 0:
		return (1, 0)
	(xp, yp) = exgcd(b, a % b)
	x = yp
	y = xp - a // b * yp
	return (x, y)

def merge(a, b):
	newmode = LCM(a.mod, b.mod)
	if (a.r - b.r) % gcd(a.mod, b.mod) != 0:
		bye()
	newr = exgcd(a.mod, b.mod)[0] * (b.r - a.r) // gcd(a.mod, b.mod) * a.mod + a.r
	newr %= newmode
	return Eqn(newr, newmode)
(x, y) = (0, 0)
(n, m, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
for i in a:
	x = LCM(x, i)
	if x > n:
		bye()
cur = Eqn(0, 1)
for i in range(0, len(a)):
	cur = merge(cur, Eqn(-i % a[i], a[i]))
y = cur.r
if y == 0:
	y += x
for i in range(0, len(a)):
	if gcd(x, y + i) != a[i]:
		bye()
if x > n or y + k - 1 > m:
	bye()
print('YES')


import math

def lcm(a, b):
	return a * b // math.gcd(a, b)

def egcd(a, b):
	if b == 0:
		return (a, 1, 0)
	(g, x, y) = egcd(b, a % b)
	return (g, y, x - a // b * y)

def crt(a, m1, b, m2):
	(g, x, y) = egcd(m1, m2)
	if (b - a) % g != 0:
		return (0, -1)
	m = m1 * m2 // g
	r = (b - a) // g * x % (m2 // g)
	r = (a + m1 * r) % m
	return (r, m)

def nel():
	print('NO')
	exit(0)
(x, y, n) = map(int, input().split())
v = list(map(int, input().split()))
mn = 1
for i in v:
	mn = lcm(mn, i)
	if mn > x:
		nel()
aux = (0, 1)
for i in range(0, n):
	aux = crt(aux[0], aux[1], (-i % v[i] + v[i]) % v[i], v[i])
	if aux[1] == -1:
		nel()
if aux[0] == 0:
	aux = (aux[1], aux[1])
if aux[0] + n - 1 > y:
	nel()
for (i, j) in enumerate(v, 0):
	res = math.gcd(aux[0] + i, aux[1])
	if res != j:
		nel()
print('YES')


def gcd(a, b):
	if a < b:
		c = b
		b = a
		a = c
	while b != 0:
		t = b
		b = a % b
		a = t
	return int(a)

def extendedEuclides(a, b):
	xx = y = 0
	yy = x = 1
	while b != 0:
		q = int(a / b)
		t = b
		b = a % b
		a = t
		t = xx
		xx = x - q * xx
		x = t
		t = yy
		yy = y - q * yy
		y = t
	return [a, x, y]

def chineseRemainder(x, y, a, b):
	[d, s, t] = extendedEuclides(x, y)
	if a % d != b % d:
		return [0, -1]
	return [int((s * b * x + t * a * y) % (x * y) / d), x * y / d]
[n, m, k] = input().split(' ')
n = eval(n)
m = eval(m)
k = eval(k)
arr = list(map(int, input().split(' ')))
I = 1
for el in arr:
	I = I * (el / gcd(I, el))
	if I > n:
		break
if I == 1:
	print('YES')
elif I > n:
	print('NO')
else:
	can = 1
	auxI = I
	fat = []
	occur = []
	for i in range(2, 1010000):
		if auxI % i == 0:
			v = 1
			while auxI % i == 0:
				v = v * i
				fat.append(v)
				occur.append(-1)
				auxI = int(auxI / i)
	if auxI > 1:
		fat.append(auxI)
		occur.append(-1)
	for (i, x) in enumerate(fat):
		for j in range(0, min(k, x)):
			if gcd(arr[j], x) == x:
				occur[i] = j
		if occur[i] == -1:
			can = 0
	for (i, x) in enumerate(fat):
		for j in range(0, k):
			if gcd(arr[j], x) != x and j % x == occur[i] or (gcd(arr[j], x) == x and j % x != occur[i]):
				can = 0
	I = 1
	J = 1
	lrem = 0
	for (i, x) in enumerate(fat):
		rem = (x - occur[i]) % x
		g = gcd(I, x)
		auxI = I * int(x / g)
		xxx = chineseRemainder(I, x, lrem % I, rem)
		lrem = xxx[0]
		I = auxI
	if lrem == 0:
		lrem = I
	if int(lrem) > m - k + 1:
		can = 0
	if can == 0:
		print('NO')
	else:
		print('YES')


from sys import stdin
from math import gcd

def lcm(a, b):
	return a * b // gcd(a, b)

def exgcd(a, b) -> (int, int, int):
	if b == 0:
		return (a, 1, 0)
	(d, x, y) = exgcd(b, a % b)
	t = x
	x = y
	y = t - a // b * y
	return (d, x, y)

def cal(v: list) -> int:
	now = v[0]
	for i in range(1, len(v)):
		a = now[0]
		b = -v[i][0]
		c = v[i][1] - now[1]
		(g, x, y) = exgcd(a, b)
		x *= c // g
		y *= c // g
		lc = lcm(a, b)
		now = (lc, (a * x + now[1]) % lc)
	return now[1]

def no():
	print('NO')
	exit(0)

def yes():
	print('YES')
	exit(0)
(n, m, k) = list(map(int, stdin.readline().split()))
a = list(map(int, stdin.readline().split()))
ll = a[0]
for x in a:
	ll = lcm(ll, x)
	if ll > n:
		no()
v = [(x, x - i % x) for (i, x) in enumerate(a)]
ans = cal(v)
ans = ans % ll
if ans <= 0:
	ans += ll
if ans + k - 1 > m:
	no()
for (i, x) in enumerate(a):
	if gcd(ll, ans + i) != x:
		no()
yes()