给定一个包含 $n$ 个字符串的集合 $D$ 和一个字符串 $s$。你需要求出集合 $D$ 中有多少个字符串在字典序上小于 $s$。

字符串 $s$ 会被修改 $q$ 次。每次修改由一个整数 $k_i$ 和一个字符 $c_i$ 定义。修改 $(k_i, c_i)$ 意味着将字符串 $s$ 从第 $k_i$ 个字符开始到末尾的所有字符都替换为字符 $c_i$。

例如，设初始字符串 $s$ 为 “anatoly”，那么查询 $(5, \text{o}), (3, \text{b}), (7, \text{x})$ 会将字符串依次改变为：

“anatoly” → “anatooo” → “anbbbbb” → “anbbbbx”

在每次修改字符串 $s$ 后，你需要输出集合 $D$ 中字典序小于 $s$ 的字符串数量。

说明

如果 $a \neq b$ 且满足以下两个条件之一，则称字符串 $a$ 在字典序上小于字符串 $b$：

• $a$ 是字符串 $b$ 的前缀；
• 存在某个 $i$，使得 $a$ 的前 $i$ 个字符与 $b$ 的前 $i$ 个字符相同，且 $a_{i+1} < b_{i+1}$。

输入格式

第一行包含两个整数 $n$ 和 $q$ —— 集合 $D$ 中字符串的数量和修改次数 ($1 \le n, q \le 10^6$)。

第二行包含一个字符串 $s$，长度不超过 $10^6$，由小写拉丁字母组成。

接下来的 $n$ 行包含集合 $D$ 中的字符串。每个字符串由小写拉丁字母组成。$D$ 中所有字符串的总长度不超过 $10^6$。

接下来的 $q$ 行包含修改的描述。每行描述包含一个整数 $k_i$ 和一个小写英文字母 $c_i$，中间用空格隔开 ($1 \le k_i \le |s|$)。

输出格式

第一行输出初始字符串 $s$ 字典序小于集合 $D$ 中字符串的数量。

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

样例

输入 1

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

输出 1

0
0
2
3

输入 2

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

输出 2

3
3
3
4
4
1

说明

在第一个样例中，字符串的变化如下：

“anatoly” → “anatooo” → “anbbbbb” → “anbbbbx”。

• 初始字符串 “anatoly” 在字典序上小于集合中所有的字符串，因此问题的答案为 0。
• 第一次修改后，字符串变为 “anatooo”，集合中存在一个相等的字符串，但答案仍然为 0，因为它不小于当前字符串。
• 随后字符串变为 “anbbbbb”，它在字典序上大于 “anatooo” 和 “anba”，但小于 “anbbbbu” 和 “boris”，因此答案为 2。
• 最后一次修改后，字符串变为 “anbbbbx”，它在字典序上大于 “anatooo”、“anba” 和 “anbbbbu”，因此答案为 3。