Problem description

W Bajtocji jest N pizzerii, wszystkie leżą wzdłuż jednej ulicy. Tak się składa, że jest to też ulubiona ulica Bajtka, po której często spaceruje ze swoją ekipą. W i-tej pizzerii pizza krojona jest na A_i kawałków. Każdy kawałek przypada jednej osobie, nie można więc ich dzielić. Jak wiadomo, pizza w Bajtocji jest tak pyszna, że każdy zjada całą swoją porcję i cała pizza zostaje zjedzona. Bajtek i jego kumple zawsze chodzili do pizzerii Ovarb, gdzie mogli się podzielić po równo, ale teraz gdy niektórzy znaleźli sobie dziewczyny, Bajtek musi poszukać nowego miejsca spotkań. W j-tym z pośród Q dni Bajtek przechadza się od pizzerii L_j-tej do pizzerii R_j-tej, a jego ekipa liczy wtedy K_j osób. Pyta się wtedy: ile jest pizzerii na przedziale [L_j,R_j], w których każdy zje jednakową liczbę kawałków?

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i Q, W drugim wierszu wejścia znajduje się ciąg N dodatnich liczb całkowitych - ciąg A. Następne Q wierszy zawiera zapytania Bajtka. W j-tym z nich podane są liczby L_j, R_j i K_j.

Wyjście

Należy wypisać Q wierszy. W j-tym z nich ma znaleźć się odpowiedź na j-te zapytanie Bajtka.

Ograniczenia

1 ≤ N, Q ≤ 100 000, 1 ≤ A_i, K_j ≤ 100 000, 1 ≤ L_j ≤ R_j ≤ N

Przykład

7 4
8 24 9 2 7 6 1
2 5 3
1 7 2
6 7 15
3 4 3

2
4
0
1