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ẻ.

Input

• Dòng ~1~: Ghi hai số nguyên dương ~N~ và ~Q~ ~(N \le 100000, Q \le 100000)~ là tổng số quả măng cụt, số câu hỏi mà dì ghẻ đặt ra.

• ~N~ dòng tiếp theo: 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~. Dì ghẻ hỏi có bao nhiêu măng cụt mỗi loại từ quả thứ ~a~ đến quả thứ ~b~.

Output

• 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~.

Sample Input 1

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

Sample Output 1

3 2 1
1 0 0
2 0 1