Breed Counting

Farmer John's $N$ cows, numbered $1$ through $N$, stand in a row. Each cow carries a breed ID: 1 for Holsteins, 2 for Guernseys, and 3 for Jerseys. Given an interval of the row, count how many cows of each breed stand inside it.

The first line contains $N$ and $Q$ ($1 \le N \le 100{,}000$, $1 \le Q \le 100{,}000$).

Each of the next $N$ lines contains an integer that is 1, 2, or 3. The number on line $i$ is the breed ID of the $i$-th cow in the row.

Each of the next $Q$ lines contains two integers $a$ and $b$ describing one query ($1 \le a \le b \le N$).

For each query $(a, b)$, print three integers on one line, separated by spaces: the number of Holsteins (breed 1), Guernseys (breed 2), and Jerseys (breed 3) among cows $a$ through $b$, in that order.