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