#include <bits/stdc++.h>
#define MAXQ 200005
using namespace std;
int N,n=1,C,Q,rez[MAXQ];
string S;
void flip(int q1,int q2){
    for(int i=q1-1;i<q2;i++){
        if(S[i]=='0')S[i]='1';
        else S[i]='0';
    }
}
struct st{
int br,poj=0;
};
void cal(st A[]){
    n=1;
    A[0].br=S[0]-'0';
    A[0].poj++;
    for(int i=1;i<N;i++){
        if(S[i]==S[i-1])A[n-1].poj++;
        else{A[n].poj++;A[n].br=S[i]-'0';n++;}}
    }
void cc(st A[]){
    for(int i=0;i<n;i++){
        A[i].poj=0;
    }
}
int solve(st A[],int p,int duz){
    int poc=0;
    int ct0=0,ct1=0,r=0;
    if(A[0].br==1){ poc=0;ct1+=A[0].poj;}
    else{poc=1;ct1+=A[1].poj;}
    for(int i=poc+1;i<n;i++){
        if(A[i].br==0){
            if(A[i].poj>A[i-1].poj||i==n-1){
                if(ct1>C){r+=C+ct0;poc=i+1;ct0=0;ct1=0;}
                else{r+=ct1;ct1=0;ct0=0;poc=i+1;}
            }
            else{ct0+=A[i].poj;}
        }
        else if(A[i].br==1){
            ct1+=A[i].poj;
        }
        if(i==n-1){
            if(ct1>C){r+=C+ct0;poc=i+1;ct0=0;ct1=0;}
                else{r+=ct1;ct1=0;ct0=0;poc=i+1;}
        }
    }
    return r;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    scanf("%d %d %d",&N,&C,&Q);
    cin>>S;
    const int M=N;
    st A[M];
    for(int i=0;i<Q;i++){
        int q1,q2;
        scanf("%d %d",&q1,&q2);
        cc(A);
        flip(q1,q2);
        cal(A);
        rez[i]=solve(A,0,n);
  }
    for(int i=0;i<Q;i++){
        cout<<rez[i]<<endl;
    }
}