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ę A_i – 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 A_L, A_L + 1, …, A_P, że ich NWD  jest równe D. (liczba wszystkich par (i,j) takich, że NWD (A_i,…,A_j) = 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 A₁, A₂, …, A_n. 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 ≤ A_i ≤ 1 000 000.

Przykład

8 4
1 12 24 8 4 16 2 3
3 7 4
1 8 1
1 4 3
2 6 4

6
14
0
9