#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define dif(x) ((x).yy-(x).xx)
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define ub(a,x) upper_bound(all(a),x)
#define lb(a,x) lower_bound(all(a),x)
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
#define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p (a, b, (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p (a, b, (__typeof__ ((a) + (b))) 0)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
const ld PI = 3.14159265359;
//const int mod = 998244353;
const int mod = 1000000007;
const li inf = 9223372036854775807ll;

using namespace __gnu_pbds;
template <class T> using oset = tree<T, null_type,greater<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using omset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

inline int power(li _a, int _n)
{
    li _c = 1;
    while (_n>0)
    {
        if (_n % 2) _c = _c * _a%mod;
        _a = _a * _a%mod;
        _n/=2;
    }
    return _c;
}





//Note to self: Check for overflow

int c;

struct node
{
    int val=-1,t0,t1;
    bool L,R; int duzL,duzR;
    int siz;
};
node fake_node;

int k=1;
node seg[530001]; bool upd[530001];
int l[530001],r[530001];

int cost(int x)
{
    return min(c,x);
}

node mrg(node a, node b)
{
    if (a.val==-1) return b; if (b.val==-1) return a;

    node res;
    bool z=true;

    res.siz=a.siz+b.siz;
    res.val=a.val+b.val;
    res.duzL=a.duzL;
    res.duzR=b.duzR;
    res.L=a.L;
    res.R=b.R;

    if (a.duzL==a.siz && a.L==b.L) res.duzL+=b.duzL;
    if (b.duzR==b.siz && b.R==a.R) res.duzR+=a.duzR;

    if (a.R!=b.L)
    {
        if (a.duzL==a.siz)
        {
            res.t0=0;
            res.t1=0;
        }
        else
        {
            res.t0=a.t0+cost((a.R==1)*a.duzR);
            res.t1=a.t1+cost((a.R==0)*a.duzR);
        }

        if (b.duzR==b.siz)
        {
            res.t0+=0;
            res.t1+=0;
        }
        else
        {
            res.t0+=b.t0+cost((b.L==1)*b.duzL);
            res.t1+=b.t1+cost((b.L==0)*b.duzL);
        }
    }
    else
    {
        if (a.duzL==a.siz)
        {
            if (b.duzR==b.siz)
            {
                res.t0=0;
                res.t1=0;
            }
            else
            {
                res.t0 = b.t0;
                res.t1 = b.t1;
            }
        }
        else if (b.duzR==b.siz)
        {
            res.t0 = a.t0;
            res.t1 = a.t1;
        }
        else
        {
            res.t0 = a.t0 + cost((a.R==1)*(a.duzR+b.duzL)) + b.t0;
            res.t1 = a.t1 + cost((a.R==0)*(a.duzR+b.duzL)) + b.t1;
        }
    }

    return res;
}

void Upd(int p)
{
    if (!upd[p]) return;
    seg[p]={seg[p].siz-seg[p].val, seg[p].t1, seg[p].t0, !seg[p].L, !seg[p].R, seg[p].duzL, seg[p].duzR, seg[p].siz};
    if (p<k) upd[2*p]^=1,upd[2*p+1]^=1; upd[p]=0;
}

node Set(int p, int ll, int rr)
{
    Upd(p);
    if (ll>r[p] || rr<l[p]) return seg[p];

    if (ll<=l[p] && rr>=r[p])
    {
        upd[p]=1;
        return  {r[p]-l[p]+1-seg[p].val, seg[p].t1, seg[p].t0, !seg[p].L, !seg[p].R, seg[p].duzL, seg[p].duzR, seg[p].siz};
    }

    seg[p]=mrg(Set(2*p,ll,rr),Set(2*p+1,ll,rr));
    return seg[p];
}

node Qry(int p, int ll, int rr)
{
    if (ll>r[p] || rr<l[p]) return fake_node;
    Upd(p);

    if (ll<=l[p] && rr>=r[p]) return seg[p];
    return mrg(Qry(2*p,ll,rr),Qry(2*p+1,ll,rr));
}

void ispisi()
{
    for (int kk=1;kk<=k;kk*=2)
    {
        ff(i,kk,2*kk) cout<<seg[i].val<<" ";
        cout<<endl;
    } cout<<endl;

    for (int kk=1;kk<=k;kk*=2)
    {
        ff(i,kk,2*kk) cout<<upd[i]<<" ";
        cout<<endl;
    } cout<<endl;
}

int main()
{
    FAST;

    #define nmp (s[i]-'0')

    int n,q; cin>>n>>c>>q;
    string s; cin>>s;

    while (k<n) k*=2;

    ff(i,0,n) seg[i+k]={nmp,0,0,nmp,nmp,1,1,1};
    ff(i,0,k) l[i+k]=i,r[i+k]=i;

    bff(i,1,k) seg[i]=mrg(seg[2*i],seg[2*i+1]),l[i]=l[2*i],r[i]=r[2*i+1];

    while (q--)
    {
        int ll,rr;
        cin>>ll>>rr;
        ll--; rr--;

        Set(1,ll,rr);
        node res=Qry(1,0,k-1);
        //cout<<res.val<<" : "<<res.t0<<" "<<res.t1<<" : "<<res.duzL<<" "<<res.duzR<<" : "<<res.L<<" "<<res.R<<endl;

        if (res.duzL==res.siz) cout<<cost((res.L==1)*res.siz)<<endl;
        else
        {
            if (res.L==0 && res.R==0) cout<<min(res.t0,res.t1+cost(res.siz-res.duzL-res.duzR))<<endl;
            else if (res.L==0 && res.R==1) cout<<min(res.t0+cost(res.duzR),res.t1+cost(res.siz-res.duzL))<<endl;
            else if (res.L==1 && res.R==0) cout<<min(res.t0+cost(res.duzR),res.t1+cost(res.siz-res.duzR))<<endl;
            else cout<<min(res.t0+cost(res.duzL)+cost(res.duzR),res.t1+cost(res.siz))<<endl;
        }
    }

    /*while (true)
    {
        string s; cin>>s;
        int ll,rr; cin>>ll>>rr; ll--; rr--;

        if (s=="sum")
        {
            node res=Qry(1,ll,rr);
            cout<<res.val<<" "<<res.t0<<" "<<res.t1<<" "<<res.duzL<<" "<<res.duzR<<endl;
        }
        else if (s=="set") Set(1,ll,rr);
    }*/
}

//Note to self: Check for overflow