fsecv

Se consideră un șir A format din N numere întregi, numerotate de la $1$ la $N$. Numim secvență a șirului $A$ orice succesiune de elemente consecutive din șir de forma $A_i$, $A_{i+1}, \dots, A_j$, cu $0 < i < j \leq N$.

Cerințe

Fiind dat șirul $A$ cu $N$ numere întregi se cere să se răspundă la $Q$ întrebări de forma: i j k ($0 < i < j \leq N$). Pentru fiecare întrebare se cere să se determine câte numere din secvența $A_i, A_{i+1}, \dots, A_j$ au frecvența de apariții egală cu $k$.

Date de intrare

Fișierul de intrare fsecv.in conține pe prima linie numerele naturale nenule $N$ și $Q$ cu semnificația din enunț. Pe următoarea linie se găsesc $N$ numere întregi ce reprezintă valorile șirului $A$. Pe următoarele linii se află descrierea celor $Q$ întrebări, câte una pe linie, în formatul precizat $i \ j \ k$.

Date de ieșire

Fișierul de ieșire fsecv.out va conține $Q$ linii. Pe fiecare linie se va găsi răspunsul întrebării $i$, cu $1 \leq i \leq Q$.

Restricții și precizări

• $2 < N \leq 100 \ 000$;
• $1 < Q \leq 100 \ 000$;
• $0 < k \leq N$;
• $-100 \ 000 \leq A_i \leq 100 \ 000$;

Exemplu

fsecv.in

11 3
1 2 4 3 2 5 6 4 5 2 1
1 6 2
2 7 3
4 11 1

fsecv.out

1
0
4

Explicație

Secvența la care se referă prima întrebare este $1, 2, 4, 3, 2, 5$, iar răspunsul este egal cu $1$.
Secvența la care se referă a doua întrebare este $2, 4, 3, 2, 5, 6$, iar răspunsul este egal cu $0$.
Secvența la care se referă a treia întrebare este $3, 2, 5, 6, 4, 5, 2, 1$, iar răspunsul este egal cu $4$.