题目描述

系统维护 $n$ 个固定的模式串 $s_1,s_2,\ldots,s_n$。模式串只包含小写英文字母，第 $i$ 个模式串当前有一个权值 $w_i$。

接下来有 $q$ 次操作：

• 1 i x：把模式串 $s_i$ 的权值修改为 $x$；
• 2 t：给出一个文本串 $t$，计算所有模式串在 $t$ 中的所有出现所贡献的权值总和。

如果模式串 $s_i$ 在文本串 $t$ 中出现了 $c_i$ 次，那么它对本次询问贡献 $c_i\times w_i$。

不同模式串独立计数；同一个模式串的不同出现可以重叠。例如模式串 aa 在文本 aaa 中出现 $2$ 次。

输入格式

第一行两个整数 $n,q$。

接下来 $n$ 行，每行一个字符串 $s_i$ 和一个整数 $w_i$。

接下来 $q$ 行，每行是一条操作，格式如题目描述。

输出格式

对于每个 2 类操作，输出一行一个整数表示答案。

样例

3 3
a 2
ab 3
b -1
2 ab
1 3 5
2 abab

4
20

数据范围

• $1\le n,q\le2\times10^5$；
• 模式串和文本串均只包含 a--z，且长度至少为 $1$；
• 所有模式串长度之和，加上所有 2 类操作中文本串长度之和，不超过 $4\times10^5$；
• $|w_i|,|x|\le10^6$。

保证答案在 64 位有符号整数范围内。