$N$ cô bò Farmer John, đánh số $1 \ldots N$, đứng thành hàng (thường xuyên tới mức chỉ cần nhắc nhẹ). Mã giống $1$: Holsteins, $2$: Guernseys, $3$: Jerseys. Đếm mỗi giống trong các đoạn hàng.

Dữ liệu vào

Dòng đầu: $N$, $Q$ ($1 \leq N \leq 100,000$, $1 \leq Q \leq 100,000$).

$N$ dòng sau chứa nguyên $1$, $2$ hoặc $3$, giống mỗi cô theo thứ tự.

$Q$ dòng sau là truy vấn với hai nguyên $a, b$ ($a \leq b$).

Dữ liệu ra

Mỗi trong $Q$ truy vấn $(a,b)$ in một dòng ba số: số cô đánh số $a \ldots b$ giống Holsteins ($1$), Guernseys ($2$), Jerseys ($3$), theo thứ tự ấy.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3 2 1
1 0 0
2 0 1

Tác giả bài toán: Nick Wu