Bờm có n con bò vừa đạt huy chương (vàng, bạc hoặc đồng) trong cuộc thi "Hoa hậu dành cho các cô bò sữa". Trong lễ chào mừng sự thành công của cuộc thi Bờm mời m thợ ảnh đến chụp ảnh trong buổi lễ.
Các con bò đứng thành một hàng ngang, chúng đều đeo huy chương để chụp ảnh. Máy ảnh của các thợ chụp ảnh có thể không thể chụp hết toàn bộ n con bò đạt giải, thợ ảnh thứ i chỉ có thể chụp được một dãy các con bò liên tiếp từ vị trí li đến ri.
Sau khi chụp ảnh, Bờm muốn biết trong mỗi bức ảnh của các thợ ảnh có bao nhiêu con bò đạt huy chương vàng, bao nhiêu con bò đạt huy chương bạc và bao nhiêu con bò đạt huy chương đồng.
Dữ liệu vào:
- Dòng đầu tiên là số nguyên dương n, m(1 ≤ n, m ≤ 100.000), đó là n con bò và m thợ ảnh.
- Dòng thứ hai chứa các số a1, a2, ..., an (1 ≤ ai ≤ 3) thể hiện huy chương đạt được của các con bò. Trong đó:
+ ai = 1 thể hiện con bò thứ i đạt huy chương vàng
+ ai = 2 thể hiện con bò thứ i đạt huy chương bạc
+ ai = 3 thể hiện con bò thứ i đạt huy chương đồng
- m dòng tiếp theo, mỗi dòng chứa hai số l và r (1 ≤ l ≤ r ≤ n) thể hiện đoạn liên tiếp các con bò đạt giải có trong bức ảnh của mỗi thợ chụp.
Kết quả ra:
- Gồm m dòng, mỗi dòng chứa ba số nguyên là số lượng con bò đạt huy chương vàng, huy chương bạc và huy chương đồng.
Bài này mình không nghĩ ra được thuật toán tối ưu để giảm bớt thời gian chạy, toàn bị quá thời gian ở mấy cái test sau :v Ai cao tăng thì chỉ giúp mình vs, thù lao 1000 magot
