Một cửa hàng nọ có một thanh gỗ kích thước ~1 \times n~ dùng để nuôi ốc sên. Người ta đã dùng bút đánh dấu, chia thanh gỗ thành ~n~ ô vuông có độ dài bằng nhau; được đánh số từ 1 đến ~n~ từ trái sang phải. Do thanh gỗ không đều, các ô có thể có mức độ phù hợp khác nhau cho ốc sên; độ phù hợp của ô thứ ~i~ là ~a_i~. Một số ô còn ốc sên đã được đặt lên thanh gỗ, thỏa mãn mỗi con ốc sên nằm gọn vào một ô và mỗi ô đều chứa không quá một con ốc sên.

Quyền đến cửa hàng để mua ốc sên về nuôi. Cậu dự định phương án là mua các ô từ ~L~ đến ~R~ và các con ốc sên ở trên đó. Vì Quyền muốn nuôi riêng từng con ốc nên chủ cửa hàng sẽ phải cắt phần gỗ được chọn thành một số đoạn, sao cho trên mỗi đoạn có đúng một con ốc sên. Cụ thể hơn, giả sử có ~k~ con ốc sên trên đoạn ~[L, R]~, chủ cửa hàng cần cắt đoạn ~[L, R]~ thành đúng ~k~ đoạn sao cho mỗi đoạn có đúng một con ốc sên và không có đoạn nào của ~[L, R]~ bị thừa ra. Để có phát triển tốt, một con ốc sên (trong số vừa được chọn ra) sẽ chỉ được bán nếu tổng độ phù hợp của các ô của đoạn mà nó đứng là không âm. Tức là, con ốc trên đoạn ~[u, v]~ được bán nếu ~a_u + a_{u+1} + ... + a_v \geq 0~. Do có thể có nhiều cách cắt khác nhau, chủ cửa hàng muốn cắt sao cho bán được nhiều ốc sên nhất có thể.

Yêu cầu: Quyền đưa ra ~Q~ truy vấn mua, dự định thử ~i~ được mô tả bởi hai số nguyên dương ~L_i, R_i~. Hãy giúp chủ cửa hàng tính cách cắt cho từng dự định, sao cho số lượng ốc sên bán được cho dự định đó là lớn nhất có thể và in ra số lượng đó. Lưu ý Quyền chỉ đưa ra các dự định và chủ cửa hàng đưa ra giải pháp chứ chưa thực sự cắt thanh gỗ ban đầu.

Dữ liệu:

Vào từ file văn bản QSNAIL.INP

• Dòng đầu tiên chứa hai số nguyên dương ~n, Q~, ~(n, Q \leq 5 \times 10^5)~.
• Dòng tiếp theo chứa một xâu nhị phân độ dài ~n~, ký tự thứ ~i~ là 0 hoặc 1 tương ứng là ô thứ ~i~ không đặt hoặc có đặt một con ốc sên;
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~, ~(-10^9 \leq a_i \leq 10^9)~;
• Dòng thứ ~i~ trong số ~Q~ dòng tiếp theo chứa hai số nguyên ~L_i, R_i \ (1 \leq L_i \leq R_i \leq n)~.

Dữ liệu bảo đảm: Có ít nhất một con ốc sên trong đoạn ~[L_i, R_i]~ với ~i = 1, 2, ..., Q~.

Kết quả: Ghi ra file văn bản QSNAIL.OUT trên ~Q~ dòng, dòng thứ ~i~ ghi một số nguyên là số ốc sên bán được nhiều nhất với dự định thứ ~i~ của Quyền.

Ví dụ

QSNAIL.INP

8 5  
01001101  
1 -2 1 -2 1 -1 -3 1  
1 8  
1 5  
2 5  
5 8  
1 2  

QSNAIL.OUT

3  
2  
1  
2  
1  

Ràng buộc

• Có ~16\%~ số test có ~a_i \geq 0 \ \forall i = 1, 2, ..., n; n \leq 8000; Q = 1~;
• Có ~14\%~ số test có ~n \leq 8000; Q = 1 \ và \ a_i = 0~ nếu ô thứ ~i~ có ốc sên, ~a_i < 0~ nếu ô thứ ~i~ không có ốc sên;
• Có ~16\%~ số test với ~n \leq 8000; Q = 1~;
• Có ~12\%~ số test với ~n, Q \leq 8000~;
• Có ~18\%~ số test với ~n, Q \leq 50000~;
• Có ~24\%~ số test với ràng buộc gốc.