В скором времени начнется великая битва между Тун тун тун тун Сахуром и Тралалело Тралала, поэтому Тун тун тун тун Сахур решил собрать войско.
Его войско можно представить как массив из $$$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 групп. Баллы за группу начисляются при прохождении всех тестов этой и всех необходимых групп. Примеры из условия не оцениваются.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 1 | 17 | $$$n, q \leq 100$$$ | — |
| 2 | 21 | $$$n \leq 1000$$$ | 1 |
| 3 | 14 | Массив $$$a$$$ содержит не более 2 различных элементов | — |
| 4 | 36 | $$$n, q \leq 10^4$$$ | 1 |
| 5 | 12 | — | 1-4 |
5 3 1 6 3 9 8 2 4 3 5 3 4
NO NO YES
