Counting Cow Breeds

Farmer John's N cows are lined up from left to right, numbered $1 \ldots N$. Each cow belongs to one of three breeds, represented by the numbers $1$, $2$, or $3$. You are given Q queries; each query asks for the count of cows of each breed within a specified interval.

For example, if the cows are represented by the sequence [1, 2, 3, 2, 1] and the query is [1, 5], then the counts for breeds $1$, $2$, and $3$ are $2$, $2$, and $1$, respectively.

Solve the problem efficiently.

inputFormat

The first line contains two integers $N$ and $Q$, where $N$ is the number of cows and $Q$ is the number of queries.

The second line contains $N$ integers, where the $i$-th integer represents the breed number of the $i$-th cow.

Each of the next $Q$ lines contains two integers $L$ and $R$, representing the left and right indices of the interval (inclusive) for the query.

outputFormat

For each query, output three integers separated by spaces, representing the count of cows of breed $1$, breed $2$, and breed $3$ in the interval from $L$ to $R$, respectively.

sample

5 3
1 2 3 2 1
1 5
2 4
3 3

2 2 1
0 2 1
0 0 1