农夫约翰有 N 头奶牛排成一排，依次编号为 1∼N。
每头奶牛都有一个品种 ID：荷斯坦牛的 ID 为 1，根西岛牛的 ID 为 2，泽西岛牛的 ID 为 3。
约翰共有 Q 个询问，每个询问需要你计算某一区间内各品种奶牛的数量。
第一行包含两个整数 N 和 Q。
接下来 N 行，每行包含一个整数（1,2,3 中的一个），按顺序给出了每头奶牛的品种 ID。
接下来 Q 行，每行包含两个整数 a,b，表示询问在范围 [a,b] 内，各品种奶牛的数量。
每个询问输出一行答案。
答案依次给出询问区间内品种 ID 为 1,2,3 的奶牛各有多少头。
1≤N,Q≤105,
1≤a≤b≤N
6 3
2
1
1
3
2
1
1 6
3 3
2 43 2 1
1 0 0
2 0 1