Nhờ sự giúp đỡ của thần vũ trụ, Vegeta đã có dịp đến thăm hành tinh Vegeta ở vũ trụ thứ 7 — thứ mà đã bị hủy diệt từ lâu trên vũ trụ thứ 6. Tại hành tinh này, anh đã ra lệnh triệu hồi tất cả các chiến binh Saiyan lại, xếp thành một hàng và đánh số họ từ \(1\) đến \(N\).

Có tất cả 3 kiểu chiến binh, Saiyan (1), Super Saiyan (2), và Saiyan God (3). Vegeta, vì muốn chơi thách đố với Son Goku, đã yêu cầu Goku phải đếm số lượng mỗi chiến binh trong từng khoảng anh yêu cầu.

Bạn hãy giúp Goku trả lời các câu hỏi của Vegeta.

Dữ liệu

• Dòng 1: Ghi hai số nguyên dương \(N\) và \(Q\) \((N ≤ 100000, Q ≤ 100000)\) — tổng số các chiến binh, số câu hỏi mà Vegeta đặt ra.
• Dòng tiếp theo ghi \(N\) số nguyên : Cho biết kiểu của các chiến binh.
• \(Q\) dòng tiếp theo: Mỗi dòng gồm hai số \(a\) và \(b\) — Vegeta hỏi Goku có bao nhiêu chiến binh mỗi loại, từ chiến binh thứ \(a\) đến chiến binh 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 Vegeta rằng có \(x\) chiến binh loại 1, \(y\) chiến binh loại 2, \(z\) chiến binh loại 3.

Ví dụ