#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

int c, inf = 1e6;

int minimum(int a, int b, int C, int d){
	a = min(a, inf); b = min(b, inf); C = min(C, inf); d = min(d, inf);
	return min(min(a,b), min(C,d)); 
}
template<int MAXN>
struct segtree{


	struct update{
		int x;

		update(int x = 0) : x(x){}

		update& operator+=(const update& other){
            x += other.x;
            if (x > 1)
            	x %= 2;
            return *this;
        }

        update operator+(const update& other){
            update tmp = *this;
            return tmp += other;
        }
	};

	struct node{
		vi a, r;

		node(vi a = vi(4,-1), vi r = vi(4,-1)) : a(a), r(r) {}

		node operator+(const node& other){

			if (other.a[0] == -1){
				return *this;
			}

			node tmp = node{};
			tmp.a[0] = minimum(a[0]+other.a[0], a[1] + other.a[0], a[0] + other.a[2], a[1] + other.a[2] - c);
			tmp.a[1] = minimum(a[0]+other.a[1], a[0] + other.a[3], a[1] + other.a[1], a[1] + other.a[3] - c);
			tmp.a[2] = minimum(a[2]+other.a[0], a[2] + other.a[2], a[3] + other.a[0], a[3] + other.a[2] - c);
			tmp.a[3] = minimum(a[2]+other.a[1], a[2] + other.a[3], a[3] + other.a[1], a[3] + other.a[3] - c);

			tmp.r[0] = minimum(r[0]+other.r[0], r[1] + other.r[0], r[0] + other.r[2], r[1] + other.r[2] - c);
			tmp.r[1] = minimum(r[0]+other.r[1], r[0] + other.r[3], r[1] + other.r[1], r[1] + other.r[3] - c);
			tmp.r[2] = minimum(r[2]+other.r[0], r[2] + other.r[2], r[3] + other.r[0], r[3] + other.r[2] - c);
			tmp.r[3] = minimum(r[2]+other.r[1], r[2] + other.r[3], r[3] + other.r[1], r[3] + other.r[3] - c);

			return tmp;
		}

		node& operator+=(const update& other){
			if (other.x % 2)
				swap(a, r);
			return *this;
		}

		node operator+(const update& other){
			node tmp = *this;
			return tmp += other;
		}
	};

	node t[2*MAXN];
	update lazy[2*MAXN];

	void init(vi tmp){
		for (int i = 1; i <= MAXN; ++i){
			t[i+MAXN-1] = node{{-1,-1,-1,-1}, {-1,-1,-1,-1}};
		}

		int n = tmp.size();
		for (int i = 1; i <= n; ++i){
			int x = tmp[i-1];
			if (!x)
				t[i+MAXN-1] = node{{0,inf, inf, c+1}, {1,inf,inf,c}};
			else
				t[i+MAXN-1] = node{{1, inf, inf, c}, {0,inf,inf,c+1}};
		}

		for (int i = MAXN-1; i > -1; --i){
			t[i] = t[2*i] + t[2*i+1];
		}
	}
	void push(int i){
        if (lazy[i].x == 0) return;

        t[i] += lazy[i];
        if (i < MAXN){
            lazy[2 * i] += lazy[i];
            lazy[2 * i + 1] += lazy[i];
        }

        lazy[i] = update{};
    }

    void add(int l, int r, update v, int pos = 1, int L = 1, int R = MAXN){
        push(pos);

        if (l > R || L > r) return;
        if (l <= L && R <= r){
            lazy[pos] += v;
            push(pos);
            return;
        }

        int mid = (L + R) / 2;
        add(l,r,v,2*pos,L,mid);
        add(l,r,v,2*pos+1,mid+1,R);
        
        t[pos] = t[pos * 2] + t[pos * 2 + 1];
    }

	int get(){
		return minimum(t[1].a[0], t[1].a[2], t[1].a[3], t[1].a[1]);
	}

	void print(){
		for (int i = 1; i < 2*MAXN; ++i){
			for (int j = 0; j < 4; ++j){
				cout << t[i].a[j] << ' ';
			}
			cout << '\n';
		}
	}
};
segtree<131072*2> drvo;

signed main()
{
	ios_base::sync_with_stdio(false); 
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	cerr.tie(nullptr);

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

	string s;
	cin >> s;

	vi t;
	for (int i = 0; i < n; ++i)
		t.push_back(s[i]-'0');

	drvo.init(t);

	for (int e = 0; e < q; ++e){
		int l, r;
		cin >> l >> r;

		drvo.add(l, r, 1);

		cout << drvo.get() << '\n';
	}
}