F. Тун тун тун тун Сахур
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В скором времени начнется великая битва между Тун тун тун тун Сахуром и Тралалело Тралала, поэтому Тун тун тун тун Сахур решил собрать войско.

Его войско можно представить как массив из $$$n$$$ натуральных чисел. Тун тун тун тун Сахур не был бы Тун тун тун туном Сахуром, если бы его не заинтересовало $$$q$$$ отрезков этого массива. Для каждого из этих отрезков ему стало интересно: а правда ли, что можно перемешать элементы на этом отрезке так, чтобы каждый следующий элемент делился на предыдущий?

Помогите Тун тун тун тун Сахуру и ответьте на все его запросы.

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

В первой строке вводятся натуральные числа $$$n$$$, $$$q$$$ — длина массива и число запросов ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$).

Во второй строке вводятся $$$n$$$ натуральных чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

Затем идут $$$q$$$ строк, в $$$i$$$-й из которых два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$) — границы $$$i$$$-го отрезка запроса.

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

Для каждого запроса в порядке входа выведите на отдельной строке слово «YES», если элементы на отрезке $$$[l_i, r_i]$$$ можно переставить так, чтобы каждый следующий делился на предыдущий, или «NO» в противном случае.

Система оценки

Тесты в этой задаче разбиты на 5 групп. Баллы за группу начисляются при прохождении всех тестов этой и всех необходимых групп. Примеры из условия не оцениваются.

ПодзадачаБаллыДоп. ограниченияНеобх. подзадачи
117$$$n, q \leq 100$$$—
221$$$n \leq 1000$$$1
314Массив $$$a$$$ содержит не более 2 различных элементов—
436$$$n, q \leq 10^4$$$1
512—1-4
Пример
Входные данные
5 3
1 6 3 9 8
2 4
3 5
3 4
Выходные данные
NO
NO
YES