You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

小明喜欢玩游戏！

小明喜欢出题！

题目描述

小明已经很久没有游戏玩了，但是小明又需要从游戏里找 idea，所以他只能回忆一下自己曾经玩过的一款游戏，叫做“云顶之弈“。

今天小明想把这个游戏简化成一个收集卡牌类的游戏，规则是这样的：

给你一个长度为 $n$ 的牌的序列，第 $i$ 张牌要么是 A，要么是 a。

小明可以做如下三种操作之一无数次：

（1）从序列中删除一张卡牌；

（2）选取三个连续的一级牌合成一张二级牌，或选取两个连续的二级牌合成一张三级牌。

具体地：三个 A 可以合成一个 B，两个 B 可以合成一个 C，C 就不能继续合成了，因为最高只有 $3$ 级的牌。

同理，三个 a 可以合成一个 b，两个 b 可以合成一个 c，c 以上不能继续合成。

合成之后，之前的牌从序列里消失，合成后的牌出现在序列这个位置。

例如你一开始有 AAaAAAAaaaAa，你可以删除第一个 a 以及最后一个 A，得到 AAAAAAaaaa，然后合成 Cab。

每一张卡牌都有一个价值，卡牌 ABCabc 的价值分别是 $A,B,C,a,b,c$。

已知小明一开始有 $n$ 个序列，每个序列初始从左到右有哪些卡牌是已知的。

你需要完成如下操作 $Q$ 次，每次操作可能是：

1 u c，在第$u$个序列的末尾添加一张字符为 $c$ 的卡牌，此处 $c$ 是 a 或 A。

2 u，从第 $u$ 个序列的末尾删除最后一张牌，如果 $u$ 本来是空的，则无任何影响。

3 u v，把第 $v$ 个序列合并到第 $u$ 个序列的末尾，然后清空第 $v$ 个序列。

4 u，查询如果拿第 $u$ 个序列来玩游戏的话，操作的方案数与所有情况下的卡牌价值总和是多少。输出答案对 $998244353$ 取模的结果。

我们称两个操作方案不同，当且仅当删除掉的牌编号不同，或存在一个 $i$，使得最后两个操作结果从左到右第 $i$ 张牌种类不同。

输入格式

第一行输入 $n,Q,A,B,C,a,b,c$。

接下来 $n$ 行，第 $i$ 行首先输入 $k_i$，表示第 $i$ 个序列的长度，然后输入一个长度为 $k_i$ 的字符串，每个位置是 a 或者 A。

接下来 $Q$ 行，输入格式如上述格式。

输出格式

对于每个操作 $4$，输出一行两个数字表示答案。

输入输出样例

1 9 1 1 1 1 1 1
1 a
4 1
1 1 a
4 1
1 1 a
4 1
1 1 a
4 1
1 1 a
4 1

2 1
4 4
9 13
22 40
55 119

大样例

数据规模与约定

对于 $100\%$ 的数据，满足 $n\le 10^5$，$Q,\sum k_i\le 3\times 10^5$，$0\le A,B,C,a,b,c<998244353$。