Las ~N~ vacas del Granjero Juan, convenientemente numeradas ~1...N~, están paradas en una fila (ellas hacen eso tan frecuentemente que ahora le cuesta poco al Granjero Juan alinearlas). Cada vaca tiene un identificador de raza: 1 para Holsteins, 2 para Guernseys y 3 para Jerseys. Al Granjero Juan le gustaria su ayuda contando el número de vacas de cada raza que están en cierto intervalo del ordenamiento.

Entrada

La primera línea de la entrada contiene ~N~ y ~Q~ ~( 1 \leq N, Q \leq 100,000)~.

Las siguientes ~N~ líneas contienen un entero que es 1, 2 ó 3, dando el identificador de raza de una sola vaca en el ordenamiento.

Las siguientes ~Q~ líneas describen una pregunta en la forma de dos enteros ~a,b~ ~(a \leq b)~.

Salida

Para cada una de las ~Q~ preguntas ~(a, b)~, imprima una línea conteniendo tres números: el número de vacas numeradas ~a...b~ que son Holsteins (raza 1), Guernseys (raza 2) y Jerseys (raza 3).

Ejemplo de Entrada

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

Ejemplo de Salida

3 2 1    
1 0 0    
2 0 1