题目描述

Farmer John 的 $N$ 头奶牛，从左到右编号为 $1 \ldots N$，排成一队。

所有牛都可以分为三个品种，每头牛都有一个品种编号（只能为 $1,2,3$ 中的一个）。FJ 有 $Q$ 个询问，每个询问希望求出某个区间内每个品种奶牛的数量。

输入格式

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

接下来 $N$ 行，每行一个整数，第 $i$ 个整数代表第 $i$ 头奶牛的品种编号。

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

输出格式

对于每个查询，输出三个整数，分别是指定区间内品种 $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