Farmer John의 $N$마리 소는 $1 \ldots N$ 번호로 한 줄이다 (자주 해서 살짝만 말해도 줄 선다). 품종 번호는 $1$ Holsteins, $2$ Guernseys, $3$ Jerseys다. 특정 구간의 각 품종 수를 구하라.

입력

첫 줄은 $N$, $Q$ ($1 \leq N \leq 100,000$, $1 \leq Q \leq 100,000$)다.

다음 $N$줄은 순서대로 한 소의 품종인 정수 $1$, $2$, $3$ 중 하나다.

다음 $Q$줄은 정수 $a, b$ ($a \leq b$)로 조회를 나타낸다.

출력

$Q$개 조회 $(a,b)$마다 번호 $a \ldots b$의 Holsteins ($1$), Guernseys ($2$), Jerseys ($3$) 수를 이 순서로 한 줄에 출력하라.

예제

입력 1

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

출력 1

3 2 1
1 0 0
2 0 1

문제 출제: Nick Wu