Description

Farmer John has $N$ cows, numbered from $1 \ldots N$ from left to right, standing in a line.

All cows belong to one of three breeds, and each cow has a breed ID (only one of $1,2,3$). FJ has $Q$ queries, and each query asks for the number of cows of each breed within a certain interval.

Input Format

The first line contains two integers $N, Q$ ($1 \leq N, Q \leq 10^5$).

The next $N$ lines each contain one integer. The $i$-th integer represents the breed ID of the $i$-th cow.

The next $Q$ lines each contain two integers $a, b$, meaning the range of the $i$-th query is $[a,b]$.

Output Format

For each query, output three integers: the number of breed $1$ cows, the number of breed $2$ cows, and the number of breed $3$ cows in the specified interval.

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

3 2 1
1 0 0
2 0 1

Hint

Translated by ChatGPT 5