时间限制：1秒　　内存限制：256M

---

【问题描述】

　　定一个长度为 \(N\) 的序列，每个位置上的数只可能是 1，2，3 中的一种。有 \(Q\) 次询问，每次给定两个数 \(a,b\)，请分别输出区间 \([a,b]\) 里数字 1，2，3 的个数。

【输入格式】

　　第一行是整数 \(N\) 和 \(Q\)
　　第二行为 \(N\) 个数，表示序列
　　接下来的 \(Q\) 行，每行表示两个数，表示询问。

【输出格式】

　　输出每个询问的答案。

【输入输出样例1】

　Input

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

　Output

3 2 1
1 0 0
2 0 1

【数据说明】

　　\(1≤N≤100,000\)， \(1≤Q≤100,000\)

【来源】

　　Mr.he