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

int 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) << endl;
    }
}

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 << 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){
        prvatri();
        return 0;
    }

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