[Usaco2015 Dec] Breed Counting

题目描述

Farmer John's N cows, conveniently numbered 1…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.

给定一个长度为 N 的序列，每个位置上的数只可能是 1、2、3 中的一种。有 Q 次询问，每次给定两个数 a,b，请分别输出区间 [a,b] 里数字 1、2、3 的个数。

输入描述

The first line of input contains N and Q (1 ≤ N ≤ 100000, 1 ≤ Q ≤ 100000). 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 ≤ b).

输出描述

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

输入样例

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

输出样例

3 2 1
1 0 0
2 0 1