#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define endl "\n"

using namespace std;

int n,c,q;
string s;

ll pref[200005];

ll suma(int i, int j) {
    if(!i)
        return pref[j];
    return pref[j]-pref[i-1];
}

void test6() {
    while(q--) {
        int L,R; cin >> L >> R;
        L--,R--;

        for(int i=L;i<=R;i++) {
            if(s[i]=='0')
                s[i]='1';
            else
                s[i]='0';
        }

        for(int i=0;i<n;i++) {
            if(i)
                pref[i]=pref[i-1]+(ll)(s[i]-'0');
            else
                pref[i]=(ll)(s[i]-'0');
        }

        ll nula=0, kec=0;
        for(char c:s) {
            if(c=='0')
                nula++;
            else
                kec++;
        }

        ll ans=kec;

        for(int i=0;i<n;i++) {
            for(int j=i;j<n;j++) {
                ll kecIzmedju=suma(i,j);
                ll nulaIzmedju=j-i+1-kecIzmedju;

//                if(i==0 && j==n-1)
//                    cout << c+(nova1-suma(i,j));
                ans=min(ans, c+(nulaIzmedju+kec-kecIzmedju));
            }
        }
        cout << ans << endl;
    }
}

void test4() {

    while(q--) {
        int L,R; cin >> L >> R;
        L--,R--;
        if(n==1) {
            if(s[0]=='0') s[0]='1';
            else s[0]='0';
            cout << (s[0]=='0'?"0":"1") << endl;
            continue;
        }

        int ans=0;
        bool unutra=false;

        for(int i=0;i<n;i++) {
            if(i>=L && i<=R) {
                if(s[i]=='0') s[i]='1';
                else s[i]='0';
            }

            if(unutra==false) {
                if(s[i]=='0')
                    continue;
                else {
                    unutra=true;
                    ans++;
                }
            }
            else {
                if(s[i]=='0')
                    unutra=false;
            }

        }

        cout << ans << endl;
    }
}

void test2() {
    int nula=0;
    for(char c:s)
        nula+=(c=='0'?1:0);

    while(q--) {
        int L,R; cin >> L >> R;
        L--,R--;

        if(s[L]=='0') {
            s[L]='1';
            nula--;
        }
        else {
            s[L]='0';
            nula++;
        }

        cout << n-nula << endl;
    }
}

void test1() {
    //n<=4000 q<=4000 c==n

    int nula=0;
    for(char c:s)
        nula+=(c=='0'?1:0);

    while(q--) {
        int L,R; cin >> L >> R;
        L--,R--;

        for(int i=L;i<=R;i++) {
            if(s[i]=='0') {
                s[i]='1';
                nula--;
            }
            else {
                s[i]='0';
                nula++;
            }
        }
        cout << n-nula << endl;
    }
}

void test0() {
    while(q--) {
        int r=rand()%1000;
        int x; cin >> x >> x;
        cout << 420*r*23*3 << endl;
    }
}

void solve()
{
    cin >> n >> c >> q;
    cin >> s;

    if(n<=4000 && q<=4000 && c==n)
        test1();
    else if(c==n) //Li=Ri
        test2();
    else if(n<=4000 && q<=4000 && c==1)
        test4();
//    else if(c==1)
//        test5();
    else if(n<=1000 && q==1)
        test6();
//    else if(q==1)
//        test7();
    else
        test0();
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int t=1; //cin >> t;
    while(t--)
        solve();
}