#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+45;

ll n,c,q;
int l[N],r[N],a[N];
int drvo[4*N],lazy[4*N];

void build(int i,int j,int node){
    if(i == j){
        drvo[node] = a[i];
        return;
    }
    int mid = i+(j-i)/2;
    build(i,mid,2*node);
    build(mid+1,j,2*node+1);
    drvo[node] = drvo[2*node]+drvo[2*node+1];
}

void push(int i,int j,int node){
    if(lazy[node]){
        drvo[node] = (j-i+1)-drvo[node];
        if(i != j){
            lazy[2*node] ^= 1;
            lazy[2*node+1] ^= 1;
        }
        lazy[node] = 0;
    }
}

void update(int i,int j,int l,int r,int node){
    push(i,j,node);
    if(j < l || i > r){
        return;
    }
    if(l <= i && r >= j){
        lazy[node] ^= 1;
        push(i,j,node);
        return;
    }
    int mid = i+(j-i)/2;
    update(i,mid,l,r,2*node);
    update(mid+1,j,l,r,2*node+1);
    drvo[node] = drvo[2*node]+drvo[2*node+1];
}

int get(int i,int j,int l,int r,int node){
    push(i,j,node);
    if(j < l || i > r){
        return 0;
    }
    if(l <= i && r >= j){
        return drvo[node];
    }
    int mid = i+(j-i)/2;
    return get(i,mid,l,r,2*node)+get(mid+1,j,l,r,2*node+1);
}

void prvatri(){
    build(1,n,1);
    for(int i = 1; i <= q; i++){
        update(1,n,l[i],r[i],1);
        cout << get(1,n,1,n,1) << "\n";
    }
}

struct cvor{
    int brs,levo,desno;
};

cvor drvo1[4*N];
int lazy1[4*N];

cvor komb(cvor a,cvor b){
    if(a.brs == -1) return b;
    if(b.brs == -1) return a;
    int nbr = a.brs+b.brs;
    if(a.desno && b.levo) nbr--;
    return {nbr,a.levo,b.desno};
}

void build1(int i,int j,int node){
    if(i == j){
        drvo1[node] = {a[i] == 1,a[i],a[i]};
        return;
    }
    int mid = i+(j-i)/2;
    build1(i,mid,2*node);
    build1(mid+1,j,2*node+1);
    drvo1[node] = komb(drvo1[2*node],drvo1[2*node+1]);
}

void push1(int i,int j,int node){
    if(lazy1[node]){
        int sad = drvo1[node].brs,levi = drvo1[node].levo,desni = drvo1[node].desno;
        drvo1[node] = {sad-1+!levi+!desni,!levi,!desni};
        if(i != j){
            lazy1[2*node] ^= 1;
            lazy1[2*node+1] ^= 1;
        }
        lazy1[node] = 0;
    }
}

void update1(int i,int j,int l,int r,int node){
    push1(i,j,node);
    if(j < l || i > r){
        return;
    }
    if(l <= i && r >= j){
        lazy1[node] = 1;
        push1(i,j,node);
        return;
    }
    int mid = i+(j-i)/2;
    update1(i,mid,l,r,2*node);
    update1(mid+1,j,l,r,2*node+1);
    drvo1[node] = komb(drvo1[2*node],drvo1[2*node+1]);
}

cvor get1(int i,int j,int l,int r,int node){
    push1(i,j,node);
    if(j < l || i > r){
        return {-1,-1,-1};
    }
    if(l <= i && r >= j){
        return drvo1[node];
    }
    int mid = i+(j-i)/2;
    return komb(get1(i,mid,l,r,2*node),get1(mid+1,j,l,r,2*node+1));
}

void cetpet(){
    build1(1,n,1);
    for(int i = 1; i <= q; i++){
        update1(1,n,l[i],r[i],1);
        cout << get1(1,n,1,n,1).brs << "\n";
    }
}

struct cv{
    int brv0,brv1,zbm0,zbm1,levi,desni,duzlevi,duzdesni,len;
};

cv drv[4*N];
int lejzi[4*N];

void pisi(cv x){
    cout << x.brv0 << " " << x.brv1 << " " << x.zbm0 << " " << x.zbm1 << " " << x.levi << " " << x.desni << " " << x.duzlevi << " " << x.duzdesni << " " << x.len << endl;
}

cv spoji(cv a,cv b){
    if(a.brv0 == -1) return b;
    if(b.brv0 == -1) return a;

    int nzbm0 = a.zbm0+b.zbm0;
    if(!a.desni && !b.levi && a.duzdesni < c && b.duzlevi >= c) nzbm0 -= a.duzdesni;
    if(!a.desni && !b.levi && a.duzdesni >= c && b.duzlevi < c) nzbm0 -= b.duzlevi;
    if(!a.desni && !b.levi && a.duzdesni < c && b.duzlevi < c && a.duzdesni+b.duzlevi >= c) nzbm0 -= a.duzdesni+b.duzlevi;

    int nzbm1 = a.zbm1+b.zbm1;
    if(a.desni && b.levi && a.duzdesni < c && b.duzlevi >= c) nzbm1 -= a.duzdesni;
    if(a.desni && b.levi && a.duzdesni >= c && b.duzlevi < c) nzbm1 -= b.duzlevi;
    if(a.desni && b.levi && a.duzdesni < c && b.duzlevi < c && a.duzdesni+b.duzlevi >= c) nzbm1 -= a.duzdesni+b.duzlevi;

    int nbrv0 = a.brv0+b.brv0;
    if(!a.desni && !b.levi && a.duzdesni >= c && b.duzlevi >= c) nbrv0--;
    if(!a.desni && !b.levi && a.duzdesni < c && b.duzlevi < c && a.duzdesni+b.duzlevi >= c) nbrv0++;

    int nbrv1 = a.brv1+b.brv1;
    if(a.desni && b.levi && a.duzdesni >= c && b.duzlevi >= c) nbrv1--;
    if(a.desni && b.levi && a.duzdesni < c && b.duzlevi < c && a.duzdesni+b.duzlevi >= c) nbrv1++;

    int nduzlevi = a.duzlevi;
    if(a.duzlevi == a.len && a.levi == b.levi) nduzlevi += b.duzlevi;

    int nduzdesni = b.duzdesni;
    if(b.duzdesni == b.len && a.desni == b.desni) nduzdesni += a.duzdesni;

    return {nbrv0,nbrv1,nzbm0,nzbm1,a.levi,b.desni,nduzlevi,nduzdesni,a.len+b.len};
}

void bilduj(int i,int j,int node){
    if(i == j){
        drv[node] = {(!a[i] && c == 1),(a[i] && c == 1),(!a[i] && c > 1),(a[i] && c > 1),a[i],a[i],1,1,1};
        return;
    }
    int mid = i+(j-i)/2;
    bilduj(i,mid,2*node);
    bilduj(mid+1,j,2*node+1);
    drv[node] = spoji(drv[2*node],drv[2*node+1]);
}

void gurni(int i,int j,int node){
    if(lejzi[node]){
        swap(drv[node].brv0,drv[node].brv1);
        swap(drv[node].zbm0,drv[node].zbm1);
        drv[node].levi ^= 1;
        drv[node].desni ^= 1;
        if(i != j){
            lejzi[2*node] ^= 1;
            lejzi[2*node+1] ^= 1;
        }
        lejzi[node] = 0;
    }
}

void apdejt(int i,int j,int l,int r,int node){
    gurni(i,j,node);
    if(j < l || i > r){
        return;
    }
    if(l <= i && r >= j){
        lejzi[node] ^= 1;
        gurni(i,j,node);
        return;
    }
    int mid = i+(j-i)/2;
    apdejt(i,mid,l,r,2*node);
    apdejt(mid+1,j,l,r,2*node+1);
    drv[node] = spoji(drv[2*node],drv[2*node+1]);
}

cv daj(int i,int j,int l,int r,int node){
    gurni(i,j,node);
    if(j < l || i > r){
        return {-1,-1,-1,-1,-1,-1,-1,-1};
    }
    if(l <= i && r >= j){
        return drv[node];
    }
    int mid = i+(j-i)/2;
    return spoji(daj(i,mid,l,r,2*node),daj(mid+1,j,l,r,2*node+1));
}

void sve(){
    bilduj(1,n,1);
    for(int i = 1; i <= q; i++){
        apdejt(1,n,l[i],r[i],1);
        cv sta = daj(1,n,1,n,1);
        //cout << sta.brv0 << " " << sta.brv1 << " " << sta.zbm0 << " " << sta.zbm1 << " " << sta.levi << " " << sta.desni << " " << sta.duzlevi << " " << sta.duzdesni << endl;
        ll sol1 = ll(c)*ll(sta.brv1)+ll(sta.zbm1);

        if(!sta.levi && !sta.desni){
            if(sta.duzlevi >= c) sta.brv0--;
            else sta.zbm0 -= sta.duzlevi;

            if(sta.duzlevi != sta.len){ /// ne preklapaju se krajevi
                if(sta.duzdesni >= c) sta.brv0--;
                else sta.zbm0 -= sta.duzdesni;
            }
        }
        else if(!sta.levi){
            if(sta.duzlevi >= c) sta.brv0--;
            else sta.zbm0 -= sta.duzlevi;
        }
        else if(!sta.desni){
            if(sta.duzdesni >= c) sta.brv0--;
            else sta.zbm0 -= sta.duzdesni;
        }
        ll sol2 = ll(c)+ll(c)*ll(sta.brv0)+ll(sta.zbm0);

        ll sol = min(sol1,sol2);
        cout << sol << "\n";
    }
}

void sestsedam(){
    for(int x = 1; x <= q; x++){
        for(int i = l[x]; i <= r[x]; i++) a[i] ^= 1;

        vector <pair<ll,int>> v;

        for(int i = 1; i <= n; ){
            int j = i;
            while(j < n && a[j+1] == a[j]){
                j++;
            }
            v.push_back({j-i+1,a[i]});
            i = j+1;
        }

        ll brvecih = 0,zbirmanjih = 0;
        for(auto f : v){
            if(!f.second) continue;
            if(f.first >= c) brvecih++;
            else zbirmanjih += f.first;
        }

        ll sol1 = c*brvecih+zbirmanjih;

        ll sol2 = 0;
        for(int i = 0; i < v.size(); i++){
            if(!v[i].second) continue;
            int j = i;
            ll sum = 0;
            while(j < v.size()-2 && v[j+1].first <= c){
                sum += v[j+1].first;
                j += 2;
            }

            sol2 += sum+min(c,ll(j-i+1));

            i = j+1;
        }

        ll sol = min(sol1,sol2);

        cout << sol << endl;
    }
}

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

    cin >> n >> c >> q;
    string s;
    cin >> s;
    for(int i = 1; i <= n; i++){
        a[i] = s[i-1]-'0';
    }
    for(int i = 1; i <= q; i++){
        cin >> l[i] >> r[i];
    }

    if(c == n){ /// broj keceva
        prvatri();
        return 0;
    }

    if(c == 1){ /// broj segmenata keceva
        cetpet();
        return 0;
    }

    if(n*q <= 100000000){
        sestsedam();
        return 0;
    }

    sve();

    /*c = 3;
    cv a = {0,0,1,0,0,0,1,1,1};
    cv b = {0,0,1,0,0,0,1,1,1};
    cv c = spoji(a,b);
    pisi(c);
    cv d = {0,0,1,1,1,0,1,1,2};
    pisi(d);
    cv e = spoji(d,c);
    pisi(e);*/
}