题目描述

农民约翰的$\red{N}$头牛，方便地编号为$\red{1…}$$\red{N，}$都站成一排（他们似乎经常这样做，现在几乎不需要农民约翰的提示就可以把它们排成一行）。每头奶牛都有一个品种$\red{ID：}$$\red{1}$头用 于霍尔斯泰因牛，$\red{2}$头用于根西岛牛，$\red{3}$头用于球衣牛。农场主约翰希望您能帮助他计算在订购的特定时间间隔内每种奶牛的数量。

输入格式

第一行输入包含$\red{N}$和$\red{Q（}$$\red{1≤}$$\red{N≤}$$\red{100,000, 1≤}$$\red{Q≤}$$\red{100,000).}$

接下来的$\red{N}$行包含一个$\red{1}$、$\red{2}$或$\red{3}$的整数，在排序中给出了一头奶牛的品种$\red{ID}$。

接下来的$\red{Q}$行以两个整数$\red{a}$、$\red{b}$的形式描述查询（$\red{a≤}$$\red{b）}$ 。

输出格式

对于每个$\red{Q}$查询（$\red{a，}$$\red{b）}$，打印一行包含三个数字：编号为$\red{a…}$$\red{b}$的奶牛数量，这些奶牛是霍尔斯泰牛（品种$\red{1）}$、根西岛牛（品种$\red{2）}$和球衣牛（品种$\red{3）}$。

样例

输入样例

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

输出样例

3 2 1
1 0 0
2 0 1