// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;

// Rolling Hash
// Verified: AOJ 2444 (Substring)

struct RollingHash {
public:
    using int_type = long long int;
    using hash_type = pair<int_type, int_type>;
    int_type base_1, base_2, mod_1, mod_2;
    vector<int_type> hash1, hash2, pow1, pow2;

    // init (constructor)
    RollingHash(string s, int_type bs_1 = 1013, int_type bs_2 = 1007) :
        base_1(bs_1), base_2(bs_2),
        mod_1(1000000007), mod_2(1000000009),
        hash1(s.length()+1,0), hash2(s.length()+1,0),
        pow1(s.length()+1,1), pow2(s.length()+1,1) {
            for(size_t i=0; i<s.length(); i++) {
                hash1[i+1] = (hash1[i] + s[i]) * base_1 % mod_1;
                hash2[i+1] = (hash2[i] + s[i]) * base_2 % mod_2;
                pow1[i+1] = pow1[i] * base_1 % mod_1;
                pow2[i+1] = pow2[i] * base_2 % mod_2;
            }
        }

    // calc str[l,r) hash (0-indexed)
    // if get(i1,j1) == get(i2,j2) -> identical string
    hash_type get(int l, int r) {
        int_type t1 = ((hash1[r] - hash1[l] * pow1[r-l]) % mod_1);
        if(t1 < 0) t1 += mod_1;
        int_type t2 = ((hash2[r] - hash2[l] * pow2[r-l]) % mod_2);
        if(t2 < 0) t2 += mod_2;
        return make_pair(t1, t2);
    }
};

int main() {
    int N, Q; scanf("%d%d", &N, &Q);
    string s; cin >> s;
    RollingHash rh(s);
    
    vector<int> divs;
    for(int i=1; i*i<=N; i++) {
        if(N % i == 0) {
            divs.emplace_back(i);
            if(N / i != i) divs.emplace_back(N / i);
        }
    }

    vector< vector<RollingHash::hash_type> > rec(divs.size());
    vector< multiset<RollingHash::hash_type> > hashes(divs.size());
    for(size_t i=0; i<divs.size(); i++) {
        int d = divs[i];
        for(int j=0, k=0; k<N; j++, k+=d) {
            int l = k, r = l + d;
            auto h = rh.get(l, r);
            hashes[i].emplace(h);
            rec[i].emplace_back(h);
        }
    }

    while(Q--) {
        int p; char c; scanf(" %d %c", &p, &c); p--;
        int ans = INF;
        for(size_t i=0; i<divs.size(); i++) {
            int d = divs[i];
            int b = p / d, m = p % d;
            
            // delete
            hashes[i].erase(hashes[i].find(rec[i][b]));
            // fprintf(stderr, "before: %lld %lld\n", rec[i][b].first, rec[i][b].second);

            // replace (hash)
            rec[i][b].first -= rh.pow1[d-m] * (ll)s[p] % rh.mod_1;
            rec[i][b].first += rh.pow1[d-m] * (ll)c % rh.mod_1;
            rec[i][b].first %= rh.mod_1;
            if(rec[i][b].first < 0) rec[i][b].first += rh.mod_1;
            
            rec[i][b].second -= rh.pow2[d-m] * (ll)s[p] % rh.mod_2;
            rec[i][b].second += rh.pow2[d-m] * (ll)c % rh.mod_2;
            rec[i][b].second %= rh.mod_2;
            if(rec[i][b].second < 0) rec[i][b].second += rh.mod_2;

            // fprintf(stderr, "after: %lld %lld\n", rec[i][b].first, rec[i][b].second);
            
            // add
            hashes[i].emplace(rec[i][b]);

            // size ?
            /*
            for(auto e : hashes[i]) {
                ll x, y; tie(x, y) = e;
                fprintf(stderr, "p = %d, d = %d: (%lld, %lld)\n", p, d, x, y);
            }
            */
            if(*hashes[i].begin() == *prev(hashes[i].end())) chmin(ans, d);

        }
        printf("%d\n", ans);

        // replace (string)
        s[p] = c;
    }
    return 0;
}



Measured memory_bytes: 33056