#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 base = 10007;
i64 mod = 1e9 + 7;
i64 mpow(i64 x, i64 y) {
  auto z = x;
  auto val = y & 1 ? x : 1;
  while (z = (z * z) % mod, y >>= 1) {
    if (y & 1) val = z * val % mod;
  }
  return val;
}
struct Segtree {
  int n;
  vector<i64> elm, length;
  Segtree(int n, string s) : n(n), elm(2 * n), length(2 * n, 1) {
    for (int i = 0; i < n; ++i) {
      elm[i + n] = s[i];
      length[i + n] = 1;
    }
    for (int i = n - 1; i >= 1; --i) {
      length[i] = length[2 * i] + length[2 * i + 1];
      elm[i] =
          (elm[2 * i] + (elm[2 * i + 1] * mpow(base, length[2 * i])) % mod) %
          mod;
    }
  }
  void set(int x, int val) {
    x += n;
    elm[x] = val;
    while (x >>= 1)
      elm[x] =
          (elm[2 * x] + (elm[2 * x + 1] * mpow(base, length[2 * x])) % mod) %
          mod;
  }
  i64 get(int x, int y) {
    int l = 0, r = 0;
    int l_len = 0;
    for (x += n, y += n - 1; x <= y; x >>= 1, y >>= 1) {
      if (x & 1) {
        l = (l + (elm[x] * mpow(base, l_len) % mod)) % mod;
        l_len += length[x];
        x++;
      }
      if (!(y & 1)) {
        r = (elm[y] + (r * mpow(base, length[y]) % mod)) % mod;
        y--;
      }
    }
    return (l + (r * mpow(base, l_len) % mod)) % mod;
  }
};
signed main() {
  int n, q;
  string s;
  cin >> n >> q >> s;
  auto div = [](int x) {
    vector<int> divisor;
    int sq = sqrt(x) + 1;
    for (int i = 1; i < sq; ++i)
      if (!(x % i)) {
        divisor.emplace_back(i);
        if (i * i != x) divisor.emplace_back(x / i);
      }
    sort(divisor.begin(), divisor.end());
    return divisor;
  };
  auto divs = div(n);
  int m = divs.size();
  Segtree seg(n, s);
  random_device rnd;
  mt19937 mt(rnd());
  uniform_int_distribution<> dst(0, n);
  vector<int> piv(m);
  vector<int> cnt(m, 0);
  for (int i = 0; i < m; ++i) {
    int v = n / divs[i];
    piv[i] = dst(mt) % divs[i];
    i64 correct = seg.get(piv[i] * v, (piv[i] + 1) * v);
    for (int j = 0; j < divs[i]; ++j) {
      i64 val = seg.get(j * v, (j + 1) * v);
      if (val == correct) ++cnt[i];
    }
  }
  for (int iii = 0; iii < q; ++iii) {
    int a;
    char b;
    cin >> a >> b;
    --a;
    for (int i = 0; i < m; ++i) {
      int v = n / divs[i];
      int j = a / v;
      i64 correct = seg.get(piv[i] * v, (piv[i] + 1) * v);
      i64 val = seg.get(j * v, (j + 1) * v);
      if (val == correct) --cnt[i];
    }
    seg.set(a, b);
    for (int i = 0; i < m; ++i) {
      int v = n / divs[i];
      if (piv[i] * v <= a && a < (piv[i] + 1) * v) {
        cnt[i] = 0;
        i64 correct = seg.get(piv[i] * v, (piv[i] + 1) * v);
        for (int j = 0; j < divs[i]; ++j) {
          i64 val = seg.get(j * v, (j + 1) * v);
          if (val == correct) ++cnt[i];
        }
      }
    }
    for (int i = 0; i < m; ++i) {
      int v = n / divs[i];
      if (piv[i] * v <= a && a < (piv[i] + 1) * v) continue;
      int j = a / (n / divs[i]);
      i64 correct = seg.get(piv[i] * v, (piv[i] + 1) * v);
      i64 val = seg.get(j * v, (j + 1) * v);
      if (val == correct) ++cnt[i];
    }
    for (int i = m - 1; i >= 0; --i)
      if (cnt[i] == divs[i]) {
        cout << n / divs[i] << endl;
        break;
      }
  }
}
