问题描述

农夫约翰有n 头奶牛，为了方便我们把它们编号为1 ~ n，现在它们站成了一排。每头奶牛都有一个血统的类型：1 代表荷斯坦奶牛，2 代表根西奶牛，3 代表泽西奶牛。农夫约翰想要你帮忙数一下某些特定的区间内，每种奶牛各有多少头。

输入格式 第一行包含两个整数n 和q，表示奶牛的头数和询问数。 第二行包含n 个正整数，每个是1; 2 或3 中的一个，表示每头奶牛的血统。 接下来q行，每行两个整数a; b，询问区间a， a + 1， ...... ， b 的情况。

输出格式 输出文件共q 行，每行三个用空格隔开的非负整数，分别代表每种奶牛的数量。

样例输入 6 3

2

1

1

3

2

1

1 6

3 3

2 4

样例输出

3 2 1

1 0 0

2 0 1

提示 对于编号为1-3的测试点，满足n，q<=1000对于编号为4-14的测试点，满足n，q<=100000对于所有的测试点，保证i<=a<=b<=n。