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

int n, c, q, a[maxn], ans;
struct node
{
	int xorV, lazy, oTotal, zTotal, oN, zN, sV, eV;
	node(){
		xorV = lazy = oN = zN = oTotal = zTotal = 0;
		sV=eV =-1;
	}
};

node segTree[maxn];

void prop(int idx){
	if(segTree[idx].lazy){
		swap(segTree[idx].oTotal, segTree[idx].zTotal);
		swap(segTree[idx].oN, segTree[idx].zN);
		segTree[idx].sV ^= 1;
		segTree[idx].eV ^= 1;
		if(idx*2+2 < maxn){
			segTree[idx*2+1].lazy ^= 1;
			segTree[idx*2+2].lazy ^= 1;
		}
		segTree[idx].lazy = 0;
	}
}

void kidsO(int idx){
	if(idx*2+2 < maxn){
		prop(idx);
		prop(idx*2+1);
		prop(idx*2+2);
		segTree[idx].oTotal = segTree[idx*2+1].oTotal + segTree[idx*2+2].oTotal;
		segTree[idx].zTotal = segTree[idx*2+1].zTotal + segTree[idx*2+2].zTotal;
		bool tmp = (segTree[idx*2+1].eV == segTree[idx*2+2].sV);
		segTree[idx].oN = segTree[idx*2+1].oN+segTree[idx*2+2].oN-(tmp&(segTree[idx*2+1].eV==1));
		segTree[idx].zN = segTree[idx*2+1].zN+segTree[idx*2+2].zN-(tmp&(segTree[idx*2+1].eV==0));
		segTree[idx].sV = segTree[idx*2+1].sV;
		segTree[idx].eV = segTree[idx*2+2].eV;
	}
}

void init(int idx, int l, int r){
	if(l == r){
		segTree[idx].xorV = a[l];
		segTree[idx].sV = a[l];
		segTree[idx].eV = a[l];
		if(a[l]){
			segTree[idx].oN = 1;
			segTree[idx].oTotal=1;
		} else {
			segTree[idx].zN = 1;
			segTree[idx].zTotal=1;
		}
		return;
	}
	int mid = (l+r)/2;
	init(idx*2+1, l, mid);
	init(idx*2+2, mid+1, r);
	kidsO(idx);
	//cerr << l << ' ' << r << ' ' << segTree[idx].oTotal << '\n';
}

void upd(int idx, int qL, int qR, int l, int r){
	prop(idx);
	if(l >= qL and r <= qR){
		segTree[idx].lazy ^= 1;
		prop(idx);
		return;
	}
	if(l > qR or r < qL){
		return;
	}
	int mid = (l+r)/2;
	upd(idx*2+1, qL, qR, l, mid);
	upd(idx*2+2, qL, qR, mid+1, r);
	kidsO(idx);
}

int queryT(int idx, int qL, int qR, int l, int r){
	prop(idx);
	if(l >= qL and r <= qR){
		return segTree[idx].oTotal;
	}
	if(l > qR or r < qL){
		return 0;
	}
	int mid = (l+r)/2;;
	int res= queryT(idx*2+1, qL,qR,l,mid)+queryT(idx*2+2,qL,qR,mid+1,r);
	kidsO(idx);
	return res;
}

int queryN(int idx, int qL, int qR, int l, int r){
	prop(idx);
	if(l >= qL and r <= qR){
		return segTree[idx].oN;
	}
	if(l > qR or r < qL){
		return 0;
	}
	int mid = (l+r)/2;;
	int res = queryN(idx*2+1, qL,qR,l,mid)+queryN(idx*2+2,qL,qR,mid+1,r);
	kidsO(idx);
	return res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n >> c >> q;
	for(int i = 0; i < n; ++i){
		char c;
		cin >> c;
		a[i] = c-'0';
	}
	if(c != 1 and c != n){
		while(q--){
		int l, r;
		cin >> l >> r;
		for(int i = l-1; i < r; ++i){
			a[i] ^= 1;
		}
		int prVal = -1, dp0=c,dp1=0,cena0=0,cena1=0;
		for(int i = 0; i < n; ++i){
			if(a[i] != prVal){
				int tmp1 = min(dp1,dp0)+cena1, tmp0 = min(dp1+cena0+c, dp0+cena0);
				dp1 = tmp1;
				dp0 = tmp0;
				cena0 = 0;
				cena1 = 0;
			}
			cena0 += (a[i]==0);
			cena0 = min(cena0, c);
			cena1 += (a[i]==1);
			cena1 = min(cena1, c);
			prVal = a[i];
		}
		int tmp1 = min(dp1,dp0)+cena1, tmp0 = min(dp1+cena0+c, dp0+cena0);
		dp1 = tmp1;
		dp0 = tmp0;
		ans = min(dp1, dp0);
		cout << ans << '\n';
		}
		return 0;
	}
	init(0, 0, n-1);
	//cout << queryT(0, 1, 3, 0, n-1) << ' ' << queryT(0, 3, 6, 0, n-1);
	while(q--){
		int l, r;
		cin >> l>>r;
		--l,r--;
		upd(0, l, r, 0, n-1);
		if(c == 1){
			cout << queryN(0, 0, n-1, 0, n-1) << '\n';
		} else {
			cout << queryT(0, 0, n-1, 0, n-1) << '\n';
		}
	}/*7 2 1
0111011
1 2
1 2
2 6*/
}