24857번 - How Many Strings Are Less 다국어

문제

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$.

노트

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}<b_{i+1}$.

입력

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|$).

출력

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.

제한

힌트

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ドル$.