#include <iostream>

using namespace std;

#define pb push_back
#define x first
#define y second
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;

const int N = 2e5 + 2;
pi seg[4 * N];
string s;

void change(int node, int ls, int rs) {
    seg[node].y++;
    seg[node].x = rs - ls + 1 - seg[node].x;
}

void push(int node, int ls, int rs, int ms) {
    if (seg[node].y % 2) change(2 * node, ls, ms);
    if (seg[node].y % 2) change(2 * node + 1, ms + 1, rs);
    seg[node].y = 0;
}

void build(int node, int ls, int rs) {
    if (ls == rs) {
        if (s[ls - 1] == '1') seg[node].x = 1; else seg[node].x = 0;
        seg[node].y = 0;
    } else {
        int ms = (ls + rs) / 2;
        build(2 * node, ls, ms);
        build(2 * node + 1, ms + 1, rs);
        seg[node].x = seg[2 * node].x + seg[2 * node + 1].x;
        seg[node].y = 0;
    }
}

void update(int node, int ls, int rs, int left, int right) {
    if (ls == left && right == rs) {
        change(node, ls, rs);
        //cout << node << " " << seg[node].x << " " << seg[node].y << " " << ls << " " << rs << " " << left << " " << right << endl;
    } else {
        int ms = (ls + rs) / 2;
        if (seg[node].y) push(node, ls, rs, ms);
        if (left > ms) update(2 * node + 1, ms + 1, rs, left, right); else
        if (right <= ms) update(2 * node, ls, ms, left, right); else {
            update(2 * node, ls, ms, left, ms);
            update(2 * node + 1, ms + 1, rs, ms + 1, right);
        }
        seg[node].x = seg[2 * node].x + seg[2 * node + 1].x;
        //cout << node << " " << seg[node].x << " " << seg[node].y << " " << ls << " " << rs << " " << left << " " << right << endl;
    }
}

int main()
{
    IOS;
    int n, c, q;
    cin >> n >> c >> q >> s;
    int cnt = 0;
    for (int i = 0; i < n; i++) if (s[i] == '1') cnt++;
    if (c == n) {
        if (n <= 4000 && q <= 4000) {
            while (q--) {
                int left, right;
                cin >> left >> right;
                --left;
                for (int i = left; i < right; i++) {
                    if (s[i] == '1') s[i] = '0', cnt--; else s[i] = '1', cnt++;
                }
                cout << cnt << endl;
            }
        } else {
            build(1, 1, n);
            while (q--) {
                int left, right;
                cin >> left >> right;
                update(1, 1, n, left, right);
                cout << seg[1].x << endl;
            }
        }
    } else {
        while (q--) {
            int left, right;
            cin >> left >> right;
            --left;
            for (int i = left; i < right; i++) {
                if (s[i] == '1') s[i] = '0'; else s[i] = '1';
            }
            char prev = 'a';
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (s[i] != prev) {
                    prev = s[i];
                    if (prev == '1') ++cnt;
                }
            }
            cout << cnt << endl;
        }
    }
    return 0;
}