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 Ai 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 Lj-tej do pizzerii Rj-tej, a jego ekipa liczy wtedy Kj osób. Pyta się wtedy: ile jest pizzerii na przedziale [Lj,Rj], 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 Lj, Rj i Kj.
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 ≤ Ai, Kj ≤ 100 000, 1 ≤ Lj ≤ Rj ≤ N
Przykład
| Wejście | Wyjście | |
|
|