#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ll long long
#define PB push_back
#define F first
//#define S second
#define all(a) a.begin(), a.end()
#define MAX (int)1e6
#define Fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define w(a) cout<<#a<<" : "<<a<<endl;
#define ldb long double
#define vi vector<int>
#define pii pair<int,int>
#define pdi pair<ldb,int>
#define N 1450
#define INF (int)1'450'000

/// peti

void test1(int n, int c, int q, string s)
{
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        l--;
        r--;
        for(int i=l; i<=r; ++i) s[i]=(s[i]=='0')+'0';
        int ans=0;
        for(int i=0; i<n; ++i)
        {
            if(s[i]=='1')
            {
                while(s[i]=='1' && i<n) ++i;
                ans++;
            }
        }
        cout<<ans<<endl;
    }
    //exit(0);
}
void test2(int n, int c, int q, string s)
{
    int br=0;
    for(auto x:s) br+=(x=='1');
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        l--;
        r--;
        for(int i=l; i<=r; ++i)
        {
            if(s[i]=='0')
            {
                br++;
                s[i]='1';
            }
            else
            {
                br--;
                s[i]='0';
            }

        }
        cout<<br<<endl;
    }
    //exit(0);
}

struct mica
{
    int l,r,sum;
};
mica f(string str, int n)
{
    int maxi=-2,x=0,l=0,r=0,s=0;
    for(int i=0; i<n; ++i)
    {
        if(str[i]=='0') x--;
        else x++;

        if(maxi<x)
        {
            maxi=x;
            l=s;
            r=i;
        }
        if(x==-1)
        {
            x=0;
            s=i+1;
        }
    }
    mica ans= {l,r,maxi};
    return ans;
}

void test3(int n, int c, int q, string s)
{
    string S=s;
    while(q--)
    {
        s=S;
        //cout<<s<<endl;
        int l,r;
        cin>>l>>r;
        l--;
        r--;
        for(int i=l; i<=r; ++i) s[i]=(s[i]=='0')+'0';
        S=s;
        //int a[n]; for(int i=0; i<n; ++i) if(s[i]=='1') a[i]=1; else a[i]=-1;
        int res=0;
        while(1)
        {
            mica ans=f(s,n);
            if(ans.sum==0) break;
            int nn=ans.r-ans.l+1;
            int jed=(ans.sum+nn)/2;
            int nul=nn-jed;
            if(jed<nul+c)
            {
                for(auto x:s) if(x=='1') res++;
                break;
            }
            else
            {
                for(int i=ans.l; i<=ans.r; ++i) s[i]='0';
                res+=nul+c;
            }
        }
        cout<<res<<endl;
        //exit(0);
    }
}

int main()
{
    Fast;
    int n,c,q; cin>>n>>c>>q;
    string s; cin>>s;

    if(c==1 && n<=4000 && q<=4000) test1(n,c,q,s);
    else if(c==n /*&& n<=4000 && q<=4000*/) test2(n,c,q,s);
    else /*if(q==1)*/ test3(n,c,q,s);

    return 0;
}