페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3946

Breed Counting 2초 512MB

문제

Farmer John's N cows, conveniently numbered 1 \ldots N, are all standing in a row (they seem to do so often that it now takes very little prompting from Farmer John to line them up). Each cow has a breed ID: 1 for Holsteins, 2 for Guernseys, and 3 for Jerseys. Farmer John would like your help counting the number of cows of each breed that lie within certain intervals of the ordering.

Problem credits: Nick Wu


입력

The first line of input contains N and Q (1 \leq N \leq 100,000, 1 \leq Q \leq 100,000).

The next N lines contain an integer that is either 1, 2, or 3, giving the breed ID of a single cow in the ordering.

The next Q lines describe a query in the form of two integers a, b (a \leq b).


출력

For each of the Q queries (a,b), print a line containing three numbers: the number of cows numbered a \ldots b that are Holsteins (breed 1), Guernseys (breed 2), and Jerseys (breed 3).


예제1

입력
6 3
2
1
1
3
2
1
1 6
3 3
2 4
출력
3 2 1
1 0 0
2 0 1

출처

USACO 2015 December Silver

역링크 공식 문제집만