Рассмотрим таблицу 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.
Выходные данные
Выведите единственное слово «YES», если данная последовательность встречается в таблице G, и «NO» в противном случае.
Примечание
Пример 1. Десятая строка таблицы G начинается с последовательности {1, 2, 1, 2, 5, 2, 1, 2, 1, 10}. Как вы можете видеть, элементы с пятого по девятый совпадают с последовательностью a.
Пример 2. На этот раз ширина таблицы G равна 8-ми. Последовательность a в ней не встречается.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
100 100 5
5 2 1 2 1
|
YES
|
|
2
|
100 8 5
5 2 1 2 1
|
NO
|
|
3
|
100 100 7
1 2 3 4 5 6 7
|
NO
|