迷妹

【题目描述】

小钟、小皓和小曦都是著名偶像派OI选手，他们都有很多迷妹。

现在，有n个妹子排成了一行，从左到右编号为1到n。这些妹子中，任意一个都是其中一个人的迷妹。

现在，蒟蒻wyz有Q个问题，第i个问题为：编号在l[i]到r[i]范围内的妹子中，分别有几个小钟的迷妹、小皓的迷妹、和小曦的迷妹。

【输入格式】

输入到fans.in

第一行2个正整数n,Q。

第2行到第n+1行每行一个正整数a[i]，描述了第i个妹子是谁的迷妹。a[i]=1表示小钟的迷妹，a[i]=2表示小皓的迷妹，a[i]=3表示小曦的迷妹。

第n+2行到第n+Q+1行，每行2个整数，表示第i个问题。

【输出格式】

输出到fans.out

共Q行，每行3个用空格分开的整数，分别表示对于第i个问题，有多少小钟、小皓、小曦的迷妹。

【样例输入】

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

【样例输出】

3 2 1
1 0 0
2 0 1

【提示】

【数据范围】

对于10%的数据，保证1<=n<=10，Q<=10，

对于25%的数据，保证1<=n<=100，Q<=100，

对于45%的数据，保证1<=n<=1000，Q<=1000，

对于100%的数据，保证1<=n<=100,000，Q<=100,000。

保证1<=a[i]<=3，1<=l[i]<=r[i]<=n。

【来源】

QBXT2017春令营第一次测试T1