Farmer John 的 $N$ 头奶牛编号 $1 \ldots N$，正排成一列（她们经常这样，现在他只需稍加提醒就能排好）。每头有品种编号：$1$ 为 Holsteins，$2$ 为 Guernseys，$3$ 为 Jerseys。帮助统计队列指定区间内各品种的奶牛数量。

输入格式

第一行包含 $N$ 和 $Q$（$1 \leq N \leq 100,000$，$1 \leq Q \leq 100,000$）。

接下来 $N$ 行各有一个整数 $1$、$2$ 或 $3$，依次表示一头奶牛的品种。

接下来 $Q$ 行各描述一次查询，为两个整数 $a, b$（$a \leq b$）。

输出格式

对每个 $Q$ 次查询 $(a,b)$，输出一行三个数，依次为编号 $a \ldots b$ 的奶牛中 Holsteins（品种 $1$）、Guernseys（品种 $2$）、Jerseys（品种 $3$）的数量。

样例

输入格式 1

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

输出格式 1

3 2 1
1 0 0
2 0 1

题目作者：Nick Wu