#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cerr.tie(NULL);
cout.tie(NULL);
long long c,n,q,a,b,s;
cin>>n>>c>>q;
cin>>s;
long long niz[n];
for(int i=0; i<n; i++){
    niz[i]=(s/pow(10,n-i-1));
    niz[i]=niz[i]%10;
}
if(c==n){
for(int i=0; i<q; i++){
    cin>>a>>b;
    for(int j=a-1; j<b; j++)
        niz[j]=abs(1-niz[j]);
    long long br1=0;
    for(int j=0; j<n; j++){
        if(niz[j]==1) br1++;
    }
    cout<<br1<<endl;
}
}
else if(c==1){
    for(int i=0; i<q; i++){
        cin>>a>>b;
        for(int j=a-1; j<b; j++)
            niz[j]=abs(1-niz[j]);
        long long brgrupa1=0,brgrupa0=0;
        for(int j=0; j<n-1; j++){
            if(niz[j]!=niz[j+1] && niz[j]==1) brgrupa1++;
            if(niz[j]!=niz[j+1] && niz[j]==0) brgrupa0++;
        }
        if(niz[n-1]==1) brgrupa1++;
        else brgrupa0++;
        if(brgrupa1>=brgrupa0+2) cout<<brgrupa0+1;
        else cout<<brgrupa1;
    }
}
else{
        int m;
    for(m=0; m<q; m++){
        cin>>a>>b;
        for(int j=a-1; j<b; j++)
            niz[j]=abs(1-niz[j]);
        long long br1=0;
        long long niz2[n];
            for(int i=0; i<n; i++){
                niz2[i]=niz[i];
            }
        for(int j=0; j<n; j++){
            if(niz[j]==1) br1++;
        }
        long long brgrupa1=0,brgrupa0=0;
        for(int j=0; j<n-1; j++){
            if(niz[j]!=niz[j+1] && niz[j]==1) brgrupa1++;
            if(niz[j]!=niz[j+1] && niz[j]==0) brgrupa0++;
        }
        if(niz[n-1]==1) brgrupa1++;
        else brgrupa0++;
            vector<int> pocinjujedinice;
            vector<int> krajjedinica;
            for(int i=0; i<n; i++){
                if((niz[i]==1 && niz[i-1]==0) || (niz[i]==1 && i==0)) pocinjujedinice.push_back(i);
                if((niz[i]==1 && niz[i+1]==0) || (niz[i]==1 && i==n-1)) krajjedinica.push_back(i);
            }
            long long ostatak1=pow(10,17),trenutno1=0,najboljapozpoc,najboljapozkraj;
            for(int i=0; i<pocinjujedinice.size(); i++){
                for(int j=i; j<pocinjujedinice.size(); j++){
                        trenutno1=0;
                    for(int k=pocinjujedinice[i]; k<=krajjedinica[j]; k++){
                        if(niz2[k]==1) trenutno1++;
                    }
                if(br1-trenutno1<=ostatak1){
                    ostatak1=br1-trenutno1;
                najboljapozpoc=pocinjujedinice[i];
                najboljapozkraj=krajjedinica[j];
                }
                }
            }
            for(int z=najboljapozpoc; z<=najboljapozkraj; z++)
                niz2[z]=abs(1-niz[z]);
            long long najnoviji=0;
            for(int z=0; z<n; z++){
                if(niz2[z]==1) najnoviji++;
            }
            if(c+najnoviji<=br1 && c+najnoviji<=c+n-br1) cout<<c+najnoviji<<endl;
            else if(br1<=c+n-br1) cout<<br1<<endl;
            else cout<<c+n-br1<<endl;
    }
}
return 0;
}