Farmer John's NN cows, conveniently numbered 1…N1…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.
输入描述:
The first line of input contains NN and QQ (1≤N≤100,0001≤N≤100,000, 1≤Q≤100,0001≤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,ba,b (a≤ba≤b).
输出描述:
For each of the QQ queries (a,b)(a,b), print a line containing three numbers: the number of cows numbered a…ba…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