Farmer Johns $N$ Kühe mit Nummern $1 \ldots N$ stehen in einer Reihe (so oft, dass sie kaum noch Aufforderung brauchen). Rassenkennung $1$: Holsteins, $2$: Guernseys, $3$: Jerseys. Zähle jede Rasse in bestimmten Intervallen.

Eingabe

Erste Zeile: $N$, $Q$ ($1 \leq N \leq 100,000$, $1 \leq Q \leq 100,000$).

Die nächsten $N$ enthalten je $1$, $2$ oder $3$, die Rasse jeder Kuh in Reihenfolge.

Die nächsten $Q$ geben eine Anfrage mit zwei ganzen Zahlen $a, b$ ($a \leq b$).

Ausgabe

Für jede der $Q$ Anfragen $(a,b)$ gib drei Zahlen in einer Zeile aus: Anzahlen bei Nummern $a \ldots b$ von Holsteins ($1$), Guernseys ($2$), Jerseys ($3$), in dieser Reihenfolge.

Beispiele

Eingabe 1

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

Ausgabe 1

3 2 1
1 0 0
2 0 1

Autor der Aufgabe: Nick Wu