Problem description
Jaś postanowił spróbować czegoś nowego i poszedł do wegańskiej restauracji. W tej restauracji wytwarzane są kostki smaku. Jest N różnych kostek, i-ta ma liczbę Ai – oznaczająca numer mieszaniny składników, z których jest zrobiona. Zestaw kolejnych kostek jest uznawany za pyszny, jeżeli NWD ich mieszanek jest równe dokładnie D.
Ponieważ Jaś chce spróbować wielu pysznych zestawów, wciąż zadaje pewne pytania kelnerowi. Każde zapytanie składa sie z trzech liczb naturalnych L, P, D i Jaś chce wiedzieć, ile jest takich zestawów kolejnych kostek w zakresie AL, AL + 1, …, AP, że ich NWD jest równe D. (liczba wszystkich par (i,j) takich, że NWD (Ai,…,Aj) = D i L ≤ i ≤ j ≤ P).
Ponieważ kelner ma dużo pracy poprosił Cię o pomoc w odpowiadaniu Jasiowi na pytania. Czy możesz to zrobić?
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N, Q. W drugim wierszu znajduje się N liczb naturalnych A1, A2, …, An. W kolejnych Q wierszach znajdują się po trzy liczby naturalne L, P, D (1 ≤ L, P ≤ N, 1 ≤ D ≤ 1 000 000).
Wyjście
W i-tym wierszu wyjścia należy wypisać jedną liczbę całkowitą – odpowiedź na i-te zapytanie Jasia.
Ograniczenia
1 ≤ N ≤ 100 000, 1 ≤ Q ≤ 50 000, 1 ≤ Ai ≤ 1 000 000.
Przykład
| Input | Output | |
|
|