Problem: In the ancient nation of Iwashiro, priests pray to calm disasters in the event of a disaster.

The priest selects the character string S from the ancient documents and proceeds with the ritual by repeating the following.

* Select one place in the string $ S $, replace the character written there with another character, and update $ S $.
* Find out what kind of string repetitions $ S $ can represent, and recite the found string. However, if $ S $ cannot be represented by repeating a character string, $ S $ is chanted.



Prayer is most effective when you recite the shortest string that represents the original string. For example, for the string abababab, prayer is most effective when you say ab instead of the string itself or abab.

As a novice priest, you must learn how to quickly find the string that maximizes the effectiveness of your prayers from the given string $ S $.

Given some information about the string $ S $ and the replacement of characters. Create a program that finds the length of the string that maximizes the effectiveness of prayer for the resulting string each time you swap characters.



input

The input is given in the following format.


$ N $ $ Q $
$ S $
$ p_1 $ $ c_1 $
$ p_2 $ $ c_2 $
::
$ p_Q $ $ c_Q $


The length of the string $ N $ ($ 2 \ leq N \ leq 10 ^ 5 $) and the number of character swaps $ Q $ ($ 1 \ leq Q \ leq 10 ^ 5 $) are given on the first line. The second line is given a string $ S $ of length $ N $ consisting of lowercase letters. The following $ Q $ line is given the position of the character to be replaced at the $ i $ th position $ p_i $ ($ 1 \ leq p_i \ leq N $) and the character $ c_i $ after the replacement. However, $ p_i $ is represented by the number from the left end of the character string. Also, $ c_i $ is lowercase.

output

Each time the characters are replaced, the length of the character string that maximizes the effect of prayer for the obtained character string is output on one line.

Examples

Input

6 5
ababac
6 b
3 c
4 a
5 b
6 c


Output

2
6
6
6
3


Input

None


Output

None

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

template <typename T>
struct SegmentTree{
  using F = function<T(T,T)>;
  int n;
  F f;
  T ti;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(F f,T ti):f(f),ti(ti){}
  void init(int n_){
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
  }
  void build(const vector<T> &v){
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  void set_val(int k,T x){
    dat[k+=n]=x;
    while(k>>=1)
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
  }
  T query(int a,int b){
    T vl=ti,vr=ti;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[l++]);
      if(r&1) vr=f(dat[--r],vr);
    }
    return f(vl,vr);
  }
};


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;


template<typename T>
map<T, int> factorize(T x){
  map<T, int> res;
  for(int i=2;i*i<=x;i++){
    while(x%i==0){
      x/=i;
      res[i]++;
    }
  }
  if(x!=1) res[x]++;
  return res;
}


template<typename T,T MOD = 1000000007>
struct Mint{
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(int k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }

  Mint inv(){return pow(MOD-2);}

  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}

  Mint operator+(Mint a){return Mint(v)+=a;};
  Mint operator-(Mint a){return Mint(v)-=a;};
  Mint operator*(Mint a){return Mint(v)*=a;};
  Mint operator/(Mint a){return Mint(v)/=a;};

  Mint operator-(){return v?MOD-v:v;}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}

  bool operator<(const Mint a)const{return v<a.v;}

  static vector<Mint> po,op;

  static void init(size_t n, T BASE){
    if(n+1<=po.size()) return;
    po.assign(n+1,1);
    op.assign(n+1,1);

    Mint x(BASE);
    Mint y=Mint(1)/x;
    for(int i=1;i<=(int)n;i++) po[i]=po[i-1]*x;
    for(int i=1;i<=(int)n;i++) op[i]=op[i-1]*y;
  }
};
template<typename T,T MOD>
vector<Mint<T, MOD> > Mint<T, MOD>::po = vector<Mint<T, MOD> >();
template<typename T,T MOD>
vector<Mint<T, MOD> > Mint<T, MOD>::op = vector<Mint<T, MOD> >();

template<typename T,typename M1,typename M2,typename M3>
struct PolynomialHash{
  using V = tuple<M1, M2, M3>;
  static constexpr T BASE = 1777771;

  PolynomialHash(size_t n){
    M1::init(n, BASE);
    M2::init(n, BASE);
    M3::init(n, BASE);
  }

  V build(const vector<T> &v){
    int n=v.size();
    M1 r1;M2 r2;M3 r3;
    for(int i=0;i<n;i++){
      r1+=M1(v[i])*M1::po[i];
      r2+=M2(v[i])*M2::po[i];
      r3+=M3(v[i])*M3::po[i];
    }
    return V(r1,r2,r3);
  }

  V add(const V &a,const V &b){
    M1 a1=get<0>(a),b1=get<0>(b);
    M2 a2=get<1>(a),b2=get<1>(b);
    M3 a3=get<2>(a),b3=get<2>(b);
    return V(a1+b1,a2+b2,a3+b3);
  }

  V sub(const V &a,const V &b){
    M1 a1=get<0>(a),b1=get<0>(b);
    M2 a2=get<1>(a),b2=get<1>(b);
    M3 a3=get<2>(a),b3=get<2>(b);
    return V(a1-b1,a2-b2,a3-b3);
  }

  V mul(const V &a,const V &b){
    M1 a1=get<0>(a),b1=get<0>(b);
    M2 a2=get<1>(a),b2=get<1>(b);
    M3 a3=get<2>(a),b3=get<2>(b);
    return V(a1*b1,a2*b2,a3*b3);
  }

  V inv(const V &a){
    M1 a1;M2 a2;M3 a3;
    tie(a1,a2,a3)=a;
    return V(a1.inv(),a2.inv(),a3.inv());
  }

  V term(size_t x,T k){
    M1 a1=M1::po[x]*M1((long long)k);
    M2 a2=M2::po[x]*M2((long long)k);
    M3 a3=M3::po[x]*M3((long long)k);
    return V(a1,a2,a3);
  }

};
template<typename T,typename M1,typename M2,typename M3>
constexpr T PolynomialHash<T, M1, M2, M3>::BASE;

//INSERT ABOVE HERE
signed main(){
  int n,q;
  cin>>n>>q;
  string s;
  cin>>s;

  using M1 = Mint<int, int(1e9+7)>;
  using M2 = Mint<int, int(1e9+9)>;
  using M3 = Mint<int, int(998244353)>;
  using V = PolynomialHash<int, M1, M2, M3>::V;
  PolynomialHash<int, M1, M2, M3> ph(1e6);

  using P = pair<V, int>;
  auto f=
    [&](P a,P b){return P(ph.add(ph.mul(a.first,ph.term(b.second,1)),b.first)
                          ,a.second+b.second);};

  P ti(ph.term(1,0),0);
  SegmentTree<P> seg(f,ti);
  vector<P> vp;
  for(int i=0;i<n;i++) vp.emplace_back(ph.term(0,(int)s[i]),1);
  seg.build(vp);

  auto check=
    [&](int len){
      return seg.query(0,n-len)==seg.query(len,n);
    };

  auto fs=factorize(n);
  vector<int> ps;
  for(auto p:fs) ps.emplace_back(p.first);
  auto query=
    [&]()->int{
      int res=n;
      for(auto p:ps)
        while(res%p==0&&check(res/p)) res/=p;
      return res;
    };

  for(int i=0;i<q;i++){
    int p;
    char c;
    cin>>p>>c;
    p--;
    seg.set_val(p,P(ph.term(0,(int)c),1));
    cout<<query()<<"\n";
  }
  cout<<flush;
  return 0;
}