Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Таблица НОД
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим таблицу G размером n × m такую, что G(i, j) = НОД(i, j) для всех 1 ≤ i ≤ n, 1 ≤ j ≤ m. НОД(a, b) обозначает наибольший общий делитель чисел a и b.

Вам дана последовательность целых положительных чисел a1, a2, ..., ak. Будем говорить, что эта последовательность встречается в таблице G, если она совпадает с подряд идущими элементами в некоторой строке начиная с некоторой позиции. Более формально, должны существовать такие числа 1 ≤ i ≤ n и 1 ≤ j ≤ m - k + 1, что G(i, j + l - 1) = al для всех 1 ≤ l ≤ k.

Определите, встречается ли последовательность a в таблице G.

Входные данные

Первая строка содержит три целых числа n, m и k (1 ≤ n, m ≤ 1012; 1 ≤ k ≤ 10000), записанные через пробел. Во второй строке через пробел записаны k целых чисел a1, a2, ..., ak (1 ≤ ai ≤ 1012).

Выходные данные

Выведите единственное слово «YES», если данная последовательность встречается в таблице G, и «NO» в противном случае.

Примеры
Входные данные
100 100 5
5 2 1 2 1
Выходные данные
YES
Входные данные
100 8 5
5 2 1 2 1
Выходные данные
NO
Входные данные
100 100 7
1 2 3 4 5 6 7
Выходные данные
NO
Примечание

Пример 1. Десятая строка таблицы G начинается с последовательности {1, 2, 1, 2, 5, 2, 1, 2, 1, 10}. Как вы можете видеть, элементы с пятого по девятый совпадают с последовательностью a.

Пример 2. На этот раз ширина таблицы G равна 8-ми. Последовательность a в ней не встречается.