(mangosteen.*)

Năm nay, quả thực là một năm tam tai của quả măng cụt. Hôm nay, dì ghẻ đã mua về \(n\) quả măng cụt và xếp thành một hàng và đánh số từ 1 đến \(n\). Có tất cả 3 loại măng cụt: Loại 1, Loại 2, Loại 3. Do không muốn cho Tấm đi dự hội nên dì ghẻ đã bắt Tấm phải đếm số lượng mỗi loại măng cụt trong từng khoảng theo dì ghẻ yêu cầu.

Bạn hãy giúp Tấm trả lời các câu hỏi của dì ghẻ.

Dữ liệu vào:

• Dòng 1: Ghi hai số nguyên dương \(n\) và \(q\) \((n \leq 10^{5},\ q \leq 10^{5})\) là tổng số quả măng cụt, số câu hỏi mà dì ghẻ đặt ra.

• Dòng 2 ghi lần lượt các số \(a_{1},\ a_{2},\ldots,a_{n}\) trong đó số thứ \(i\ (1 \leq i \leq n;1 \leq a_{i} \leq 3)\) cho biết loại măng cụt của quả thứ \(i\)

• \(q\) dòng tiếp theo: Mỗi dòng gồm hai số \(a\) và \(b\). Dì ghẻ hỏi có bao nhiêu măng cụt mỗi loại từ quả thứ \(a\) đến quả thứ \(b\).

Kết quả:

• Gồm \(q\) dòng, mỗi dòng chứa 3 số nguyên không âm \(x,\ y,\ z\) trả lời câu hỏi tương ứng của dì ghẻ rằng có \(x\) quả loại 1, \(y\) quả loại 2, \(z\) quả loại 3.

Ví dụ: