Description

给定一个长度为N的序列，每个位置上的数只可能是$1，2，3$中的一种。

有$Q$次询问，每次给定两个数$a,b$，请分别输出区间$[a,b]$里数字$1，2，3$的个数。

Format

Input

第一行两个整数$n$和$q$，

接下来$n$行表示$n$个数字，且每个数字均为$1，2，3$中的一种，

接下来$q$行，每行两个数字$a$和$b$，表示询问区间$[a,b]$里数字$1，2，3$的个数。

Output

对于每一次询问，每行输出三个用空格隔开的数字，分别表示区间内1，2，3出现的个数

Samples

样例输入

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

样例输出

3 2 1  
1 0 0  
2 0 1

Limitation

$12\%$的分数，$n \leq 10, q \leq 10$

另有$12\%$的分数，$n \leq 1000, q \leq 1000$

$100\%$的分数，$n \leq 100000, q \leq 100000$