字符串游戏

给定 $N$ 个仅由小写英文字母 a 到 z 组成的字符串 $a_i$，每个字符串都有一个权值 $v_i$。接下来进行 $M$ 次操作，操作分为以下三种：

• Cv x v'：将第 $x$ 个字符串的权值修改为 $v'$；
• Cs x a'：将第 $x$ 个字符串修改为 $a'$；
• Q：从当前字符串中选择一个集合，并将集合中的字符串重新排列，使得除最后一个字符串外，每个字符串都是后一个字符串的前缀。两个相同的字符串也满足前缀关系，也可以不选择任何字符串。求所有合法集合中的最大权值和。

前 $50\%$ 的测试数据可以使用离线算法，后 $50\%$ 的测试数据要求使用在线算法。

输入格式

第一行包含一个正整数 $Test$，表示当前的数据类型。

第二行包含两个正整数 $N,M$，分别表示字符串数量和操作数量。

接下来 $N$ 行，每行包含一个字符串 $a_i$。

第 $N+3$ 行包含 $N$ 个整数 $v_i$，依次表示每个字符串的初始权值。

接下来 $M$ 行，每行表示一次操作，格式为 Cv x v'、Cs x a' 或 Q。

当 $Test=1$ 时，修改操作中的参数无需解码，直接按输入内容执行。

当 $Test=2$ 时，设最近一次询问操作的答案为 $ans$；如果此前还没有询问操作，则令 $ans=0$。修改操作的参数需要按以下规则解码：

• 对于 Cv x v' 操作，将 $v'$ 解码为 $\min(1000,v'+(ans\bmod 1000))$；
• 对于 Cs x a' 操作，将字符串 $a'$ 中的每个字符循环后移 $ans\bmod 26$ 位，其中字母 a 到 z 首尾循环。

输出格式

对于每次 Q 操作，输出一行一个整数，表示当前合法字符串集合的最大权值和。

样例输入

1
5 5
aba
ab
babb
abaa
abab
-2 1 4 2 3
Q
Cv 1 2
Q
Cs 3 abaab
Q

样例输出

4
6
9

数据范围

• $Test\in\{1,2\}$；
• $1\le N\le 5\times 10^4$；
• $1\le M\le 10^5$；
• 所有修改操作均满足 $1\le x\le N$；
• 初始权值 $v_i$ 以及输入中 Cv 操作解码前的参数 $v'$ 均满足 $-1000\le v_i,v'\le 1000$；
• 令 $Len$ 表示所有初始字符串及所有 Cs 操作中输入字符串的长度总和，则 $Len\le 10^6$；
• 前 $50\%$ 的测试数据允许使用离线算法，后 $50\%$ 的测试数据要求使用在线算法。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

1
5 5
aba
ab
babb
abaa
abab
-2 1 4 2 3
Q
Cv 1 2
Q
Cs 3 abaab
Q

输出

4
6
9