Prayers of Iwashiro

　

In the ancient nation of Iwashiro, priests offer prayers to appease disasters when they occur.

The priest selects a string $S$ from an ancient text and proceeds with the ritual by repeating the following

• Pick one place in the string $S$ and update $S$ by replacing a letter written there with another letter.
• Find out what kind of string repetition $S$ can be represented by, and chant the string you find. However, if $S$ cannot be represented by a repetition of the string, chant $S$.

The efficacy of the prayer is maximized when you chant the shortest string repetition that represents the original string. For example, for the string abababab, the efficacy of the prayer is maximized when you chant ab instead of the string itself or ababab.

As a new priest, you need to learn how to quickly find the string that maximizes the efficacy of the prayer from the given string $S$.

You will be given the string $S$ and some information about replacing the letters. Write a program that finds the length of the string that maximizes the efficacy of the prayer for the obtained string each time a letter is replaced.

Input

The input is given in the following form.

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

In the first line, the length of the string $N$ ($2 \leq N \leq 10^5$) and the number of times the characters are replaced $Q$ ($1 \leq Q \leq 10^5$) are given. In the second line, a string $S$ of length $N$ consisting of lowercase letters is given. The following $Q$ line gives the position of the $i$-th character to be replaced, $p_i$ ($1 \leq p_i \leq N$), and the character to be replaced, $c_i$. Note that $p_i$ is expressed as the number of characters counting from the left end of the string. $c_i$ is in lowercase.

Output

Each time a letter is replaced, output the length of the string that maximizes the effectiveness of the prayer for the resulting string in a line.

Sample Input and Output

Sample Input

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

Sample Output

2
6
6
6
3

---