Les $N$ vaches de Farmer John, numérotées $1 \ldots N$, sont en file (si souvent qu’il suffit maintenant de les inciter à peine). Identifiants : $1$ pour Holsteins, $2$ pour Guernseys, $3$ pour Jerseys. Comptez chaque race dans des intervalles de la file.

Entrée

Première ligne : $N$, $Q$ ($1 \leq N \leq 100,000$, $1 \leq Q \leq 100,000$).

Les $N$ suivantes contiennent chacune $1$, $2$ ou $3$, la race d’une vache dans l’ordre.

Les $Q$ suivantes donnent une requête par deux entiers $a, b$ ($a \leq b$).

Sortie

Pour chacune des $Q$ requêtes $(a,b)$, affichez une ligne de trois nombres : les effectifs des numéros $a \ldots b$ de races Holsteins ($1$), Guernseys ($2$), Jerseys ($3$), dans cet ordre.

Exemples

Entrée 1

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

Sortie 1

3 2 1
1 0 0
2 0 1

Auteur du problème : Nick Wu