Las $N$ vacas de Farmer John, numeradas $1 \ldots N$, están en fila (tan a menudo que apenas necesitan indicaciones). Raza $1$: Holsteins, $2$: Guernseys, $3$: Jerseys. Cuenta cada raza en intervalos de la fila.

Entrada

Primera línea: $N$, $Q$ ($1 \leq N \leq 100,000$, $1 \leq Q \leq 100,000$).

Las siguientes $N$ tienen un entero $1$, $2$ o $3$, raza de cada vaca en orden.

Las siguientes $Q$ dan consulta de dos enteros $a, b$ ($a \leq b$).

Salida

Para cada una de $Q$ consultas $(a,b)$ imprime tres números en una línea: cantidades en $a \ldots b$ de Holsteins ($1$), Guernseys ($2$), Jerseys ($3$), en ese orden.

Ejemplos

Entrada 1

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

Salida 1

3 2 1
1 0 0
2 0 1

Autor del problema: Nick Wu