该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 Z 准备给小 Y 送上彩色手串作为礼物，这手串上面总共有 $n$ 颗珠子，我们将这些珠子从左到右编号为 $1,2,\dots,n$。

所有珠子可以分成三种颜色，具体地说，每颗珠子一定是 $1,2,3$ 三种颜色中的一种。

现在，小 Y 会问小 Z 共 $q$ 个问题，每个问题希望小 Z 说出编号 $x\sim y$ 这一段区间（包括 $x$ 和 $y$）种每种颜色的珠子的数量。

输入格式

第一行两个整数 $n,q$。

接下来 $n$ 行，每行一个整数，第 $i$ 个整数表示第 $i$ 颗珠子的颜色。

接下来有 $q$ 行，每行两个整数 $x,y$，表示第 $i$ 次询问的范围是 $[x,y]$。

输出格式

对于每一个查询，输出三个整数，分别是询问区间种颜色 $1$ 的珠子数量，颜色 $2$ 的珠子数量，颜色 $3$ 的珠子数量。

输入输出样例

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

3 2 1
1 0 0
2 0 1

提示

【数据范围】

对于前 $30\%$ 的数据，$3 \le n \le 1000, 1 \le q \le 1000$；

对于 $100\%$ 的数据，$3 \le n \le 10^5, 1 \le q \le 10^5, 1\le x \le y \le n$。