# [Usaco2015 dec]Breed Counting

时间限制：10s 空间限制：128MB

### 题目描述

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 NN and QQ (1≤N≤100,000 1≤Q≤100,000).

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

The next QQ lines describe a query in the form of two integers a,b (a≤b).

### 输出格式

For each of the QQ 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

### 提示

没有写明提示

### 题目来源

Silver鸣谢Claris提供译文