题目描述

某科研机构正在对一条生产线进行管理分析。生产线上依次站着 N名工作人员，从左到右依次编号为 1∼N。
机构的所有工作人员划分为 三种不同的岗位类型，每名工作人员恰好属于其中一种，岗位类型编号分别为 1,2,3。
管理部门需要频繁统计某一连续区间内，各种岗位类型的人员数量。为此，他们提出了Q次统计请求，每次请求都会给出一个区间 [l,r]，要求统计编号在该区间内的工作人员中，三种岗位类型分别有多少人。
请你编写程序，高效地回答所有统计请求。

输入格式

第一行包含两个整数 N,Q，分别表示工作人员人数和统计请求次数。
接下来 N行，每行一个整数，第 i行表示编号为i的工作人员所属的岗位类型（只可能为 1,2,3中的一个）。
接下来Q行，每行包含两个整数 l,r，表示一次统计请求，要求统计区间 [l,r]内三种岗位类型的人数。

输出格式

对于每一次统计请求，输出一行，包含三个整数，依次表示在指定区间内：岗位类型分别为 1 2 3的人数，整数之间用空格分隔。

样例

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

3 2 1
1 0 0
2 0 1

10 5
1
2
3
1
2
2
3
1
1
2
1 10
3 7
4 9
2 5
6 6

4 4 2
1 2 2
3 2 1
1 2 1
0 1 0

数据范围

对于 40%的数据，满足1≤N,Q≤1000。
对于 100%的数据，满足 1≤N,Q≤100000，岗位类型编号只可能为1,2,3，查询区间满足1≤l≤r≤N。