Роман очень любит спать и опаздывать. Из-за таких качеств он проснулся только в $$$9$$$:$$$42$$$. Понимая, что он явно немного опаздывает и все уже уехали без него, он решил вызвать такси.
Выйдя из общежития, Роман увидел таксиста, который уже заждался его. И вот они уже собирались поехать, но машина не заводилась. К счастью, Роман разбирается в машинах и сразу понял, что кто-то слил все топливо из бака.
Но оказалось, что у машины был НОДовый двигатель, представляющий из себя массив натуральных чисел $$$a$$$ размером $$$n$$$. А его топливом были верные ответы на $$$q$$$ запросов вида:
В первой строке заданы два целых положительных числа $$$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
