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 cạnh 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ố con ốc sên đã được đặt lên thanh gỗ, thoả 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 \ge 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\) dự định 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ìm 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

• Dòng đầu chứa hai số nguyên dương \(n, Q\) \((n, Q \le 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\) \((|a_i| \le 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 \le L_i \le R_i \le b)\).

Dữ liệu bảo đảm có ít nhất một con ốc sên trong đoạn \([L_i, R_i]\)

Dữ liệu ra

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

Input 1

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

Output 1

3
2
1
1
0

Ràng buộc

• Có 16% số test có \(a_i \ge 0\) \(∀i = 1,2,3, … , n; n \le 8000; Q = 1\);
• Có 14% số test có \(n \le 8000;Q = 1\) và \(a_i = 0\) nếu ô thứ \(i\) có ốc sên, \(a_i \lt 0\) nếu ô thứ \(i\) không có ốc sên;
• Có 16% số test với \(n \le 8000;Q = 1\);
• Có 12% số test với \(n,Q \le 8000\);
• Có 18% số test với \(n,Q \le 50000\);
• Có 24% số test với ràng buộc gốc.