Problems
Breed Counting
Breed Counting
Farmer John's $n$ cows, conveniently numbered $1 ... n$, are all standing in a row (they seem to do so often that it now takes very little prompting from Farmer John to line them up). Each cow has a breed ID: $1$ for Holsteins, $2$ for Guernseys, and $3$ for Jerseys. Farmer John would like your help counting the number of cows of each breed that lie within certain intervals of the ordering.
\InputFile
The first line contains $n$ and $q~(1 \le n, q \le 10^5)$.
The next $n$ lines contain an integer that is either $1, 2$ or $3$, giving the breed ID of a single cow in the ordering.
The next $q$ lines describe a query in the form of two integers $a, b~(a \le b)$.
\OutputFile
For each of the $q$ queries $(a, b)$, print a line containing three numbers: the number of cows numbered $a, b~(a \le b)$ that are Holsteins (breed $1$), Guernseys (breed $2$), and Jerseys (breed $3$).
Input example #1
6 3 2 1 1 3 2 1 1 6 3 3 2 4
Output example #1
3 2 1 1 0 0 2 0 1