题目描述

$10$ 年一度的国庆阅兵仪式，编号从 $1\sim n$ 的 $n$ 个士兵整齐的排成一排，等待检阅。

每位士兵胸口上都有他的兵种徽章： $1$ 表示海军，$2$ 表示陆军，$3$ 表示空军。

主席同志会进行 $Q$ 次检阅，每次检阅区间 $[a,b]$ 中的士兵，请你帮忙统计每次检阅中海陆空三军的士兵数量分别是多少？

输入格式

第一行两个正整数 $n,Q$ ；

接下来的 $n$ 行每行一个数字（ $1$ 或 $2$ 或 $3$ ），表示士兵的兵种；

接下来的 $Q$ 行每行两个整数 $a,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

数据范围

对于 $100\%$ 的数据： $1\le n\le 10^5,1\le Q\le 10^5,1\le a\le b\le n$ 。