Breed Counting

Input

The first line contains two integers $n$ and q~(1 \le n, q \le 10^5).

Each of the next $n$ lines contains one integer, $1,2$, or $3$, which is the breed identifier of the corresponding cow.

The following $q$ lines describe the queries, each consisting of two integers $a$ and b~(a \le b).

Output

For each of the $q$ queries $(a,b)$, print a line containing three integers — the number of cows of each breed in the interval from $a$ to $b$, inclusive.

Examples