$N$ krów Farmer John o numerach $1 \ldots N$ stoi w rzędzie (tak często, że wystarczy mała zachęta). Rasa $1$: Holsteins, $2$: Guernseys, $3$: Jerseys. Policz każdą rasę w przedziałach rzędu.

Wejście

Pierwszy wiersz: $N$, $Q$ ($1 \leq N \leq 100,000$, $1 \leq Q \leq 100,000$).

Następne $N$ zawierają całkowite $1$, $2$ lub $3$, rasę każdej krowy po kolei.

Następne $Q$ opisują zapytanie dwiema całkowitymi $a, b$ ($a \leq b$).

Wyjście

Dla każdego z $Q$ zapytań $(a,b)$ wypisz trzy liczby w wierszu: liczby krów $a \ldots b$ ras Holsteins ($1$), Guernseys ($2$), Jerseys ($3$), w tej kolejności.

Przykład

Wejście 1

6 3
2
1
1
3
2
1
1 6
3 3
2 4

Wyjście 1

3 2 1
1 0 0
2 0 1

Autor zadania: Nick Wu