C. How Many Strings Are Less
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a set $$$D$$$ of $$$n$$$ strings and a string $$$s$$$. You need to find the number of strings in the set $$$D$$$ that are lexicographically less than $$$s$$$.

The given string $$$s$$$ is modified $$$q$$$ times. Each modification is defined by a pair of an integer $$$k_i$$$ and a character $$$c_i$$$. Modification $$$(k_i, c_i)$$$ means that all characters of the string $$$s$$$, starting from $$$k_i$$$ and up to the end of the string, are replaced by the character $$$c_i$$$.

For example, let the initial string $$$s$$$ be "anatoly", then the queries $$$(5, \mathtt{o})$$$, $$$(3, \mathtt{b})$$$, $$$(7, \mathtt{x})$$$ change the string as follows:

"anatoly" $$$\to$$$ "anatooo" $$$\to$$$ "anbbbbb" $$$\to$$$ "anbbbbx"
After each modification of the string $$$s$$$, you need to output the number of strings of the set $$$D$$$ that are lexicographically less than $$$s$$$.
Note

String $$$a$$$ is lexicographically less than string $$$b$$$ if $$$a \ne b$$$ and one of two conditions is satisfied:

  • $$$a$$$ is a prefix of the string $$$b$$$;
  • for some $$$i$$$, the first $$$i$$$ characters of the string $$$a$$$ are equal to the corresponding characters of the string $$$b$$$, and $$$a_{i+1} \lt b_{i+1}$$$.
Input

The first line contains two integers $$$n$$$ and $$$q$$$ — the number of strings of the set $$$D$$$ and the number of modifications ($$$1 \le n, q \le 10^6$$$).

The second line contains a string $$$s$$$ consisting of no more than $$$10^6$$$ lowercase Latin letters.

The following $$$n$$$ lines contain the strings of the set $$$D$$$. Each string consists of lowercase Latin letters. The total length of the strings in $$$D$$$ does not exceed $$$10^6$$$.

The following $$$q$$$ lines contain descriptions of modifications. The description consists of the integer $$$k_i$$$ and the lowercase letter of the English alphabet $$$c_i$$$, separated by a space ($$$1 \le k_i \le |s|$$$).

Output

The first line of output must contain the number of strings of the set $$$D$$$ that are lexicographically less than the initial string $$$s$$$.

Then output $$$q$$$ lines. In the $$$i$$$-th line, print the answer after the $$$i$$$-th modification.

Examples
Input
4 3
anatoly
boris
anatooo
anbbbbu
anba
5 o
3 b
7 x
Output
0
0
2
3
Input
5 5
abcde
buz
ababa
build
a
aba
1 b
3 z
2 u
4 z
1 a
Output
3
3
3
4
4
1
Note

In the first sample test, the string changes as follows:

"anatoly" $$$\to$$$ "anatooo" $$$\to$$$ "anbbbbb" $$$\to$$$ "anbbbbx".
  • Initial string "anatoly" is lexicographically less than all the strings of the set, so the answer to the problem is $$$0$$$.
  • After the first modification, the string becomes "anatooo" and there is an equal string in the set, but the answer to the problem is still $$$0$$$, since it is not less than the current one.
  • Then the string becomes "anbbbbb", which is lexicographically greater than "anatooo" and "anba", but less than "anbbbbu" and "boris", so the answer is $$$2$$$.
  • After the last modification, the line will become "anbbbbx", which is lexicographically greater than "anatooo", "anba" and "anbbbbu", the answer is $$$3$$$.