문제

호정이네 알고리즘 스터디에는 $N$명의 부원이 있으며, 이들은 $1$번부터 $N$번까지 번호가 매겨져 일렬로 서 있다. 각 부원은 주로 사용하는 프로그래밍 언어에 따라 $1, 2, 3$ 중 하나의 ID를 가지고 있다. 호정이는 특정 구간에 각 ID를 가진 부원이 몇 명씩 있는지 알고 싶어 한다.

호정이를 도와 주어진 구간 $[a, b]$에 속한 부원들 중 각 ID별 인원수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 부원의 수 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어진다. ($1 \le N \le 100\,000$; $1 \le Q \le 100\,000$)

이어서 $N$개의 줄에 걸쳐 각 부원의 언어 ID($1, 2, 3$ 중 하나)가 한 줄에 하나씩 주어진다.

다음 $Q$개의 줄에는 쿼리를 나타내는 두 정수 $a$와 $b$가 공백으로 구분되어 주어진다. ($1 \le a \le b \le N$)

출력

각 $Q$개의 쿼리 $(a, b)$에 대해, 번호가 $a$번부터 $b$번인 부원 중 ID가 $1$인 부원의 수, $2$인 부원의 수, $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