| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 72 | 20 | 13 | 56.522% |
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:
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.
4 3 anatoly boris anatooo anbbbbu anba 5 o 3 b 7 x
0 0 2 3
5 5 abcde buz ababa build a aba 1 b 3 z 2 u 4 z 1 a
3 3 3 4 4 1
In the first sample test, the string changes as follows:
"anatoly" $\to$ "anatooo" $\to$ "anbbbbb" $\to$ "anbbbbx".
anatoly" is lexicographically less than all the strings of the set, so the answer to the problem is $0$.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.anbbbbb", which is lexicographically greater than "anatooo" and "anba", but less than "anbbbbu" and "boris", so the answer is $2$.anbbbbx", which is lexicographically greater than "anatooo", "anba" and "anbbbbu", the answer is $3$.