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

int n, c, q;
string s, t;

int tree[1000006];
int lazy[1000006];

void update(int v, int tl, int tr, int l, int r) {
  if (lazy[v]) {
    tree[v] = (tr - tl + 1) - tree[v];
    if (tl != tr) {
      lazy[2 * v] = 1;
      lazy[2 * v + 1] = 1;
    }
    lazy[v] = 0;
  }
  if (tl > tr || tl > r || tr < l) {
    return;
  }
  if (tl >= l && tr <= r) {
    tree[v] = (tr - tl + 1) - tree[v];
    if (tl != tr) {
      lazy[2 * v] = 1;
      lazy[2 * v + 1] = 1;
    }
    return;
  }
  int tm = (tl + tr) / 2;
  update(2 * v, tl, tm, l, r);
  update(2 * v + 1, tm + 1, tr, l, r);
  tree[v] = tree[2 * v] + tree[2 * v + 1];
}

int sum(int v, int tl, int tr, int l, int r) {
  if (lazy[v]) {
    tree[v] = (tr - tl + 1) - tree[v];
    if (tl != tr) {
      lazy[2 * v] = 1;
      lazy[2 * v + 1] = 1;
    }
    lazy[v] = 0;
  }
  if (tl > tr || tl > r || tr < l) {
    return 0;
  }
  if (tl >= l && tr <= r) {
    return tree[v];
  }
  int tm = (tl + tr) / 2;
  return sum(2 * v, tl, tm, l, r) + sum(2 * v + 1, tm + 1, tr, l, r);
}

void build(int v, int tl, int tr) {
  if (tl > tr) return;
  if (tl == tr) {
    tree[v] = s[tl] - '0';
    return;
  }
  int tm = (tl + tr) / 2;
  build(2 * v, tl, tm);
  build(2 * v + 1, tm + 1, tr);
  tree[v] = tree[2 * v] + tree[2 * v + 1];
}

int main() {
  cin >> n >> c >> q;
  cin >> s;
  if (c == 1) {
    while (q--) {
      int l, r; cin >> l >> r;
      l--; r--;
      t = s;
      for (int i = l; i <= r; i++) {
	if (s[i] == '0') t[i] = '1';
	if (s[i] == '1') t[i] = '0';
      }
      int cnt = 0;
      for (int i = 0; i < n; i++) {
	if (t[i] == '1' && (!i || (t[i - 1] == '0'))) cnt++;
      }
      cout << cnt << '\n';
    }
  } else {
    build(1, 0, n - 1);
    while (q--) {
      int l, r; cin >> l >> r;
      update(1, 0, n - 1, l - 1, r - 1);
      cout << sum(1, 0, n - 1, 0, n - 1) << '\n';
      update(1, 0, n - 1, l - 1, r - 1);
    }
  }
}