품종 세기

농부 존의 소 $N$마리가 $1$번부터 $N$번까지 번호를 달고 한 줄로 서 있다. 소마다 품종 번호가 하나씩 붙어 있는데, 1은 홀스타인, 2는 건지, 3은 저지를 뜻한다. 줄에서 구간을 하나 고를 때 그 구간에 선 소 중 각 품종이 몇 마리인지 세어라.

첫째 줄에 $N$과 $Q$가 주어진다 ($1 \le N \le 100{,}000$, $1 \le Q \le 100{,}000$).

다음 $N$개 줄에는 1, 2, 3 중 한 정수가 주어진다. $i$번째 줄의 수는 줄에서 $i$번째로 선 소의 품종 번호다.

다음 $Q$개 줄에는 질의를 나타내는 두 정수 $a$, $b$가 주어진다 ($1 \le a \le b \le N$).

질의 $(a, b)$마다 한 줄에 세 정수를 공백으로 구분해 출력한다. $a$번부터 $b$번까지의 소 중 홀스타인(품종 1), 건지(품종 2), 저지(품종 3)의 수를 이 순서대로 출력한다.