#include <bits/stdc++.h>
using namespace std;
const int N=200050;
const int M=N*20;
int n,c,q,a[N];
int st[M],lzy[M];
void Build(int c,int ss,int se){
    if(ss>se)return;
    if(se==ss){st[c]=a[se];return;}
    int mid=ss+se>>1;
    Build(c*2+1,ss,mid);
    Build(c*2+2,mid+1,se);
    st[c]=st[c*2+1]+st[c*2+2];
}
void Set(int c,int ss,int se,int l,int r){
    if(lzy[c]==1){
        st[c]=se-ss+1-st[c];
        lzy[c]=0;
        if(ss!=se)lzy[c*2+1]^=1,lzy[c*2+2]^=1;
    }
    if(ss>se||ss>r||se<l)return;
    if(l<=ss&&se<=r){
        st[c]=se-ss+1-st[c];
        lzy[c]=0;
        if(ss!=se)lzy[c*2+1]^=1,lzy[c*2+2]^=1;
        return;
    }
    int mid=ss+se>>1;
    Set(c*2+1,ss,mid,l,r);
    Set(c*2+2,mid+1,se,l,r);
    st[c]=st[c*2+1]+st[c*2+2];
}
int Get(int c,int ss,int se,int l,int r){
    if(lzy[c]!=0){
        st[c]=se-ss+1-st[c];
        lzy[c]=0;
        if(ss!=se)lzy[c*2+1]^=1,lzy[c*2+2]^=1;
    }
    if(ss>se||ss>r||se<l)return 0;
    if(ss>=l&&se<=r)return st[c];
    int mid=ss+se>>1;
    return Get(c*2+1,ss,mid,l,r)+Get(c*2+2,mid+1,se,l,r);
}
int main(){
    scanf("%i %i %i",&n,&c,&q);
    char s[n];scanf("%s",&s);
    for(int i=0;i<n;i++)a[i+1]=(int)(s[i]-'0');
    if(c==n){
        Build(0,1,n);
        while(q--){
            int l,r;scanf("%i %i",&l,&r);
            Set(0,1,n,l,r);
            printf("%i\n",Get(0,1,n,1,n));
        }
        return 0;
    }
    if(c==1){
        if(n<=4000){
            while(q--){
                int l,r;scanf("%i %i",&l,&r);
                for(int i=l;i<=r;i++){
                    a[i]=1-a[i];
                }
                int cnt1=0,cnt2=0;
                for(int i=1;i<=n;i++){
                    if(a[i]==1&&(i==1||a[i-1]==0))cnt1++;
                }
                for(int i=1;i<=n;i++){
                    if(a[i]==0&&(i==1||a[i-1]==1))cnt2++;
                }
                printf("%i\n",min(cnt1,cnt2+1));
            }
            return 0;
        }/*else{

        }*/
    }
    if(q==1){
        int l,r;scanf("%i %i",&l,&r);
        for(int i=l;i<=r;i++)a[i]=1-a[i];
        int cnt=0;
        vector<int> one,zer;
        int from=1,to=n;
        for(int i=1;i<=n;i++){
            if(a[i]==0)from++;
            else break;
        }
        for(int i=n;i>=1;i--){
            if(a[i]==0)to--;
            else break;
        }
        for(int i=from;i<=to;i++){
            if(i>0&&a[i]!=a[i-1]){
                if(a[i]==1)zer.push_back(cnt);
                else one.push_back(cnt);
                cnt=1;
            }else cnt++;
        }
        one.push_back(cnt);
        //for(int r:zer)printf("%i\n",r);
        int ans=0,mudjaa=0,mudjab=c;
        for(int r:one)mudjaa+=min(r,c);
        for(int r:zer)mudjab+=min(r,c);
        ans=min(mudjaa,mudjab);
        printf("%i\n",ans);
        return 0;
    }
    while(q--){
        int l,r;scanf("%i %i",&l,&r);
        for(int i=l;i<=r;i++)a[i]=1-a[i];
        int cnt=0;
        vector<int> one,zer;
        int from=1,to=n;
        for(int i=1;i<=n;i++){
            if(a[i]==0)from++;
            else break;
        }
        for(int i=n;i>=1;i--){
            if(a[i]==0)to--;
            else break;
        }
        for(int i=from;i<=to;i++){
            if(i>0&&a[i]!=a[i-1]){
                if(a[i]==1)zer.push_back(cnt);
                else one.push_back(cnt);
                cnt=1;
            }else cnt++;
        }
        one.push_back(cnt);
        int mudjaa=0,mudjab=c;
        for(int r:one)mudjaa+=min(c,r);
        for(int r:zer)mudjab+=min(c,r);
        printf("%i\n",min(mudjaa,mudjab));
    }
    return 0;
}