#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, Q;
  cin >> N >> Q;
  string S;
  cin >> S;
  vector<int> fact;
  for (int i = 1; i <= N; i++){
    if (N % i == 0){
      fact.push_back(i);
    }
  }
  int fact_cnt = fact.size();
  vector<vector<vector<int>>> cnt(fact_cnt);
  for (int i = 0; i < fact_cnt; i++){
    cnt[i] = vector<vector<int>>(fact[i], vector<int>(26, 0));
  }
  for (int i = 0; i < N; i++){
    for (int j = 0; j < fact_cnt; j++){
      cnt[j][i % fact[j]][S[i] - 'a']++;
    }
  }
  vector<vector<int>> type_cnt(fact_cnt);
  for (int i = 0; i < fact_cnt; i++){
    type_cnt[i] = vector<int>(fact[i], 0);
    for (int j = 0; j < fact[i]; j++){
      for (int k = 0; k < 26; k++){
        if (cnt[i][j][k] > 0){
          type_cnt[i][j]++;
        }
      }
    }
  }
  vector<int> ng_cnt(fact_cnt, 0);
  for (int i = 0; i < fact_cnt; i++){
    for (int j = 0; j < fact[i]; j++){
      if (type_cnt[i][j] > 1){
        ng_cnt[i]++;
      }
    }
  }
  for (int i = 0; i < Q; i++){
    int p;
    char c;
    cin >> p >> c;
    p--;
    int ans = N;
    for (int j = 0; j < fact_cnt; j++){
      cnt[j][p % fact[j]][S[p] - 'a']--;
      if (cnt[j][p % fact[j]][S[p] - 'a'] == 0){
        type_cnt[j][p % fact[j]]--;
        if (type_cnt[j][p % fact[j]] == 1){
          ng_cnt[j]--;
        }
      }
      cnt[j][p % fact[j]][c - 'a']++;
      if (cnt[j][p % fact[j]][c - 'a'] == 1){
        type_cnt[j][p % fact[j]]++;
        if (type_cnt[j][p % fact[j]] == 2){
          ng_cnt[j]++;
        }
      }
      if (ng_cnt[j] == 0){
        ans = min(ans, fact[j]);
      }
    }
    cout << ans << endl;
    S[p] = c;
  }
}
