Breed Counting

Several seasons of hot summers and cold winters have significantly damaged Farmer John's fence for $n$ cows, which are lined up in a row and consecutively numbered from $1$ to $n$. Each cow belongs to one of three breeds: $1$ – Holsteins, $2$ — Guernseys, $3$ — Jerseys. Farmer John asks you to count the number of cows of each breed within a given range.

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