Le $N$ mucche di Farmer John, numerate $1 \ldots N$, sono in fila (così spesso che basta un piccolo invito). Razza $1$: Holsteins, $2$: Guernseys, $3$: Jerseys. Conta ogni razza in intervalli della fila.

Input

Prima riga: $N$, $Q$ ($1 \leq N \leq 100,000$, $1 \leq Q \leq 100,000$).

Le successive $N$ contengono un intero $1$, $2$ o $3$, la razza di ciascuna mucca in ordine.

Le successive $Q$ danno una richiesta con due interi $a, b$ ($a \leq b$).

Output

Per ciascuna delle $Q$ richieste $(a,b)$ stampa tre numeri su una riga: quantità nei numeri $a \ldots b$ di Holsteins ($1$), Guernseys ($2$), Jerseys ($3$), in quest’ordine.

Esempi

Input 1

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

Output 1

3 2 1
1 0 0
2 0 1

Autore del problema: Nick Wu