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\le i\le N-1)$ sao cho $S_i$ $\ne$ $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\le l\le r\le 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\le {10}^6,K\le {10}^9,Q\le 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\le l\le r\le 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