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

题目背景

能预见后续的要求吗？从某种角度而言，预处理就是在知道后续要求的情况下做的。

题目描述

给定一个$n$个元素，且元素只有$1,2,3$的数组$A$。给定$Q$次查询，每次查询输入$l,r$，你需要分别求出$[l,r]$这个范围内里面$1,2,3$的个数

输入格式

第一行两个整数 $N,Q$（$1 \leq N,Q \leq 10^5$）。

接下来 $N$ 行，每行一个整数，第 $i$ 个整数为$A_i$

接下来 $Q$ 行，每行两个整数 $l,r$，表示第 $i$ 次查询的范围是 $[l,r]$。

输出格式

对于每个查询，输出三个整数，分别$[l,r]$这个范围内里面$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