イワシロの祈り

古代国家イワシロでは、災害が起きたときにそれを鎮めるために、神官が祈りをささげます。

神官は古文書から文字列Sを選び、以下を繰り返すことで儀式を進めていきます。

• 文字列$S$の中の場所を一つ選び、そこに書かれた文字を他の文字に入れ替えて、$S$を更新する。
• $S$がどのような文字列の繰り返しで表せるかを見つけて、見つけた文字列を唱える。ただし、$S$が文字列の繰り返しで表せないときは$S$を唱える。

祈りの効力が最大になるのは、最も短い文字列の繰り返しで元の文字列を表すものを唱えたときです。たとえば、ababababという文字列に対して、この文字列そのものやababではなく、abと唱えたときに祈りの効力が最大になります。

新米神官のあなたは、与えられた文字列$S$から祈りの効力を最大にする文字列を素早く見つける方法を会得しなければなりません。

入力

入力は以下の形式で与えられる。

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

１行目に文字列の長さ$N$ ($2 \leq N \leq 10^5$)と文字を入れ替える回数$Q$ ($1 \leq Q \leq 10^5$)が与えられる。２行目に英小文字からなる長さ$N$の文字列$S$が与えられる。続く$Q$行に、$i$番目に入れ替える文字の位置$p_i$ ($1 \leq p_i \leq N$)と入れ替えた後の文字$c_i$が与えられる。ただし、$p_i$は文字列の左端から数えて何番目かで表される。また、$c_i$は英小文字である。

出力

文字を入れ替えるたびに、得られる文字列について祈りの効力を最大にする文字列の長さを１行に出力する。

入出力例

入力例

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

出力例

2
6
6
6
3