409309: GYM103483 C How Many Strings Are Less
Description
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:
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|$$$).
OutputThe 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.
ExamplesInput4 3 anatoly boris anatooo anbbbbu anba 5 o 3 b 7 xOutput
0 0 2 3Input
5 5 abcde buz ababa build a aba 1 b 3 z 2 u 4 z 1 aOutput
3 3 3 4 4 1Note
In the first sample test, the string changes as follows:
- 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$$$.