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