Farmer John 的 N 头奶牛，方便地编号为 1…N，都排成一排（他们似乎经常这样做，以至于现在几乎不需要 Farmer John 的提示就可以将它们排成一列）。每头奶牛都有一个品种 ID：1 代表荷斯坦奶牛，2 代表根西岛奶牛，3 代表泽西奶牛。Farmer John 希望您能帮助计算在订购的特定间隔内的每个品种的奶牛数量。

输入格式（文件 bcount.in）：

输入的第一行包含 N 和 Q (1≤N≤100,000, 1≤Q≤100,000)。接下来的 N 行包含一个整数，可以是 1、2 或 3，给出单头奶牛的品种 ID订购。

接下来的 Q 行以两个整数 a,b (a≤b) 的形式描述了一个查询。

输出格式（文件 bcount.out）：

对于每个 Q 查询 (a,b)，打印一行包含三个数字：编号为 a...b 的奶牛数量，分别是荷斯坦奶牛（品种 1）、根西岛奶牛（品种 2）和泽西奶牛（品种 3）。

SAMPLE INPUT:

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

SAMPLE OUTPUT:

3 2 1
1 0 0
2 0 1