Sửu có một xâu nhị phân ~S~ độ dài ~N~. Trong một thao tác, Sửu có thể chọn một vị trí ~i~ ~(1 \leq i \leq N - 1)~ sao cho ~S_i~ ~\neq~ ~S_{i+1}~ và đổi chổ ~S_i~ và ~S_{i + 1}~ cho nhau. Nói cách khác, Sửu có thể dịch chuyển một kí tự 1 qua lại trong một thao tác.

Ví dụ: Cho xâu 1101010. Sửu có thể chọn ~i = 3~ để nhận được xâu mới là 1110010, hay ~i = 4~ để nhận được xâu mới là 1100110.

Gọi độ đẹp của xâu ~S~ là độ dài của xâu con dài nhất chỉ chứa kí tự 1.

Ví dụ: Độ đẹp của xâu 1101010 là ~2~.

Gọi ~G(S)~ là độ đẹp lớn nhất của xâu ~S~ sau khi thực hiện không quá ~K~ thao tác. Để tăng thử thách cho mình, Sửu đặt thêm ~Q~ câu hỏi. Ở câu hỏi thứ ~i~, Sửu sẽ đảo ngược đoạn ~[l, r]~ ~(1 \leq l \leq r \leq N)~ của xâu ~S~ (Chuyển kí tự 1 thành 0 hoặc ngược lại).

Gọi ~S_i~ là xâu ~S~ sau câu hỏi thứ ~i~, với mỗi câu hỏi, bạn hãy giúp Sửu tính ~G(S_i)~.

Input

• Dòng đầu tiên nhập ba số ~N~, ~K~ và ~Q~ ~(N \leq 10^6, K \leq 10^9, Q \leq 50)~ lần lượt là độ dài của xâu ~S~, số thao tác tối đa và số câu hỏi mà Sửu đặt ra.
• Dòng thứ hai nhập vào xâu ~S~.
• ~Q~ dòng sau, dòng thứ ~i + 2~ nhập vào hai số ~l~ và ~r~ ~(1 \leq l \leq r \leq N)~ thể hiện cho câu hỏi thứ ~i~.

Output

• Gồm ~Q + 1~ dòng, dòng thứ ~i~ thể hiện cho ~G(S_i)~.

Sample Input

5 2 3
10101
3 3
2 4
1 5

Sample Output

3
1
5
0

Giải thích test mẫu:

• ~S~ ban đầu là 10101, ta có thể chọn ~i = 1~, sau đó chọn ~i = 4~ để nhận được xâu 01110 có độ đẹp là ~3~ trong ~2~ thao tác, đây cũng là độ đẹp lớn nhất có thể.
• Sau câu hỏi thứ ~1~, ~S~ trở thành 10001 có độ đẹp là ~1~, có thể chứng minh được ta không thể tăng độ đẹp trong không quá ~2~ thao tác.
• Sau câu hỏi thứ ~2~, ~S~ trở thành 11111 có độ đẹp là ~5~, vì ta không thể thực hiện thêm thao tác nên đây là độ đẹp lớn nhất có thể.
• Sau câu hỏi thứ ~3~, ~S~ trở thành 00000 có độ đẹp là ~0~, vì ta không thể thực hiện thêm thao tác nên đây là độ đẹp lớn nhất có thể.

Scoring