Đếm giống bò (Breed Counting)

Nguồn: USACO Silver

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ con bò đứng thành một hàng và được đánh số từ $1$ đến $N$. Mỗi con thuộc đúng một trong ba giống, được mã hóa bởi các số $1$, $2$ hoặc $3$.

Bạn cần trả lời $Q$ truy vấn. Mỗi truy vấn cho một đoạn vị trí $[a,b]$ và yêu cầu xác định riêng:

• số bò giống $1$ trong đoạn;
• số bò giống $2$ trong đoạn;
• số bò giống $3$ trong đoạn.

Các bò ở cả vị trí $a$ và $b$ đều được tính.

Input

• Dòng đầu chứa hai số nguyên $N,Q$.
• $N$ dòng tiếp theo: dòng thứ $i$ chứa mã giống của con bò thứ $i$.
• $Q$ dòng cuối, mỗi dòng chứa hai số nguyên $a,b$.

Output

Với mỗi truy vấn, in ba số nguyên trên một dòng theo thứ tự: số bò giống $1$, giống $2$, giống $3$ trong đoạn $[a,b]$.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le N,Q\le10^5$

• $breed_i\in\{1,2,3\}$

• $1\le a\le b\le N$

• Subtask 1 — 20%: $N,Q\le40$

• Subtask 2 — 30%: Mọi truy vấn đều có $a=1$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

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

Output

3 2 1
1 0 0
2 0 1

Giải thích

Dãy giống bò là

• Truy vấn $[1,6]$ chứa ba bò giống $1$, hai bò giống $2$ và một bò giống $3$, nên in 3 2 1.
• Truy vấn $[3,3]$ chỉ có con bò thứ $3$, thuộc giống $1$, nên in 1 0 0.
• Truy vấn $[2,4]$ chứa các giống $1,1,3$, nên in 2 0 1.