题目描述

给定一个由 $n$ 个字符串组成的集合 $D$，以及一个字符串 $s$。你需要求出集合 $D$ 中有多少个字符串按字典序严格小于 $s$。

字符串 $s$ 会被修改 $q$ 次。每次修改由一个整数 $k_i$ 和一个字符 $c_i$ 描述，表示把字符串 $s$ 中从位置 $k_i$ 到末尾的所有字符都替换成字符 $c_i$。

例如初始字符串为 anatoly，依次执行修改 $(5,o),(3,b),(7,x)$ 后，字符串变化如下：

anatoly -> anatooo -> anbbbbb -> anbbbbx

你需要输出初始状态以及每次修改后的答案。

字典序定义如下：字符串 $a$ 小于字符串 $b$，当且仅当 $a \ne b$，并且满足以下条件之一：

• $a$ 是 $b$ 的前缀；
• 存在某个位置，使得此前所有字符相同，而在该位置上 $a$ 的字符小于 $b$ 的字符。

输入格式

第一行包含两个整数 $n,q$，表示集合 $D$ 中字符串数量与修改次数。

第二行包含初始字符串 $s$，只含小写英文字母，长度不超过 $10^6$。

接下来 $n$ 行，每行一个集合 $D$ 中的字符串，只含小写英文字母。集合中所有字符串总长度不超过 $10^6$。

接下来 $q$ 行，每行包含一个整数 $k_i$ 和一个小写英文字母 $c_i$，表示一次修改。

输出格式

第一行输出初始字符串 $s$ 对应的答案。

随后输出 $q$ 行，第 $i$ 行输出第 $i$ 次修改后的答案。

数据范围

$1 \le n,q \le 10^6$，$1 \le k_i \le |s|$。

样例 1

输入：
4 3
anatoly
boris
anatooo
anbbbbu
anba
5 o
3 b
7 x

输出：
0
0
2
3

样例 2

输入：
5 5
abcde
buz
ababa
build
a
aba
1 b
3 z
2 u
4 z
1 a

输出：
3
3
3
4
4
1