3. Задача C. НОДовый двигатель
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Роман очень любит спать и опаздывать. Из-за таких качеств он проснулся только в $$$9$$$:$$$42$$$. Понимая, что он явно немного опаздывает и все уже уехали без него, он решил вызвать такси.

Выйдя из общежития, Роман увидел таксиста, который уже заждался его. И вот они уже собирались поехать, но машина не заводилась. К счастью, Роман разбирается в машинах и сразу понял, что кто-то слил все топливо из бака.

Но оказалось, что у машины был НОДовый двигатель, представляющий из себя массив натуральных чисел $$$a$$$ размером $$$n$$$. А его топливом были верные ответы на $$$q$$$ запросов вида:

  • $$$\; l \; r \; k$$$ — найти НОД всех $$$a_i$$$ ($$$l \le i \le r$$$), которые нацело делятся на $$$k$$$. Если нет таких $$$a_i$$$, которые делятся нацело на $$$k$$$, то ответом на запрос будет $$$0$$$.
Надо как можно быстрее ответить на все запросы, иначе Роман не успеет на тур.
Входные данные

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

Следующая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$1 \leq a_i \leq 5 \cdot 10^5$$$), разделенных пробелами — описание массива $$$a$$$.

Последние $$$q$$$ строк содержат три целых числа $$$l, r$$$ и $$$k$$$ ($$$1 \leq l \le r \leq n$$$, $$$1 \le k \le 5 \cdot 10^5$$$) — описание запросов.

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

Для каждого запроса выведите в отдельной строке ответ на него.

Система оценки
№Дополнительные ограниченияБаллы за подзадачуНеобходимые подзадачи
$$$1$$$$$$n, q \le 10^3$$$$$$3$$$
$$$2$$$$$$a_i \le 10$$$$$$8$$$
$$$3$$$Все $$$k_i$$$ равны$$$11$$$
$$$4$$$Все $$$a_i$$$ различны$$$12$$$
$$$5$$$Все $$$k_i$$$ различны$$$16$$$
$$$6$$$$$$l_i = 1$$$$$$9$$$
$$$7$$$$$$n, a_i \le 3 \cdot 10^4$$$$$$20$$$
$$$8$$$Нет дополнительных ограничений$$$21$$$$$$1$$$ — $$$7$$$
Пример
Входные данные
5 3
2 4 3 16 8
3 5 4
1 5 2
1 3 1
Выходные данные
8
2
1