题目描述

小 d 是 4xx9 小游戏高手。

有一天，小 d 发现了一个很经典的小游戏：跳青蛙。

游戏在一个 $5$ 个格子的棋盘上进行。在游戏的一开始，最左边的两个格子上各有一个向右的青蛙，最右边的两个格子上各有一个向左的青蛙。

每次移动可以选取一个青蛙，向这只青蛙的前方移动一格到空格子中或跳过前方的一个不同朝向的青蛙并移动到空格子中。

为了使你更好地理解这个游戏，我们下发了一个游戏 demo 作为参考（注意：这个 demo 中的棋盘大小和题目中并不相同）。

这个游戏本身当然难不倒小 d，小 d 轻松地就解决了这个游戏。但是一个人玩游戏实在是太寂寞了，于是小 d 找到了小 m 和他一起玩耍。小 d 规定，自己只能操控向右的青蛙，小 m 只能操控向左的青蛙。

小 d 很快发现，这个游戏想要做到双方轮流行动，就无法达到交换所有青蛙的游戏结局。于是，小 d 打开了 m 个游戏，并规定双方轮流行动，每次选择其中一个游戏并控制自己的青蛙行动一步（不能不动）。小 d 发现，这么做的话就能够使大部分的游戏最终都交换所有的青蛙了。

由于小 d 是坑队友高手，所以他们玩了一会之后，就开始互相坑害对方，都希望使对方无法行动。他们约定，当轮到一方行动时，若其所有的青蛙都无法行动，则对方获得游戏的胜利。正当博弈论大师小 d 计算着谁会成为最后的胜者时，电脑卡死了。小 d 发现，只能 kill 掉一些游戏才能使剩下的游戏进行下去了。由于电脑已经卡死了，小 d 无法自由选择 kill 掉哪些游戏，只能运行系统自带的随机 kill 小程序。具体来说，小 d 运行这个随机 kill 小程序之后，每个游戏有 $1/2$ ​​的概率被 kill 掉，有 $1/2$ ​​的概率能够继续下去。游戏之间被 kill 掉的概率是独立的。

小 d 思考了一番，决定如果运行小程序之后他的胜率过低，就直接重启电脑。这时，小 d 突然发现自己已经不记得刚才轮到谁行动了，于是他决定综合考虑自己先手和后手的胜率。

小 d 并不擅长概率论，他想让你告诉他运行小程序后，剩下的局面为小 d 必胜、小 m 必胜、先手必胜、后手必胜的概率各为多少，这样他才能更好地决定是否重启电脑。

为了避免精度问题，输出答案乘 $2^m$ ​​之后对 $998244353$ 取模的结果。

注意：题目并不保证输入的所有 $m$ 个状态中小 m 和小 d 之前的总行动步数相差不超过 $1$，但是保证不会出现起始状态无法到达的状态。

输入格式

从标准输入读入数据。

我们使用一个长度为 $5$ 的字符串来表示一个状态，其中，$\tt L$ 表示面朝右的青蛙，$\tt R$ 表示面朝左的青蛙，$\tt \_$（下划线）表示空格子。例如，初始状态为 $\tt LL\_RR$。

本题含有多组数据，第一行两个整数 $T,C$（$1\leq C\leq 100$）分别表示测试点编号和数据组数。

对于每组数据，第一行一个整数 $n$（$1\leq n\leq 23$）表示不同状态的棋盘个数，接下来 $n$ 行每行一个长度为 $5$ 的字符串 $s_i$ ​​和一个正整数 $a_i$（$1\leq a_i\leq 10^6$​​），分别表示棋盘的状态和在该状态下的棋盘的个数。

保证输入的字符串合法且不重复。

输出格式

输出到标准输出。

定义 $m=\sum a_i$​​。

对于每组数据，输出一行四个整数，分别表示小 d 必胜（即 $\tt L$ 的控制方必胜）、小 m 必胜（即 $\tt R$ 的控制方必胜）、先手必胜、后手必胜的概率乘 $2^m$ ​​之后对 $998244353$ 取模的结果。

0 1
1
LL_RR 1

0 0 1 1

对于样例 $1$，若该游戏没有被 kill，双方唯一可能的操作序列为 $\tt LL\_RR \to L\_LRR \to LRL\_R \to LR\_LR \to LRRL\_ \to LRR\_L \to L$ 胜，小 m 先手时同理，故该情况为先手必胜。若该游戏被 kill 了，双方都没有合法行动，后手必胜。

0 1
3
LRRL_ 1
LRR_L 1
LLR_R 1

4 2 0 2

对于样例 $2$，令这三个棋盘的状态从上到下为 $A,B,C$，则 $\{A,B,C\},\{A,B\},\{A,C\},\{A\}$ 为小 d 必胜，$\{C\},\{B,C\}$ 为小 m 必胜，$\{B\},\{\}$ 为后手必胜。

0 1
1
LRRL_ 1000000

421273116 0 0 1

提示

保证数据中不会出现从 $\tt LL\_RR$ 状态无法到达的状态（如 $\tt RLLR\_$），故合法的状态共有 $23$ 种。

定义 $k-$ 不可达点 为从 $\tt LL\_RR$ 操作 $k$ 次（双方加起来一共操作 $k$ 次，顺序任意）后依然无法到达的合法状态，如 $1-$ 不可达点为：全集 $\tt \{LL\_RR,L\_LRR,LLR\_R\}$ 共 $20$ 个，$5-$ 不可达点为 $\tt \{RLR\_L,RRL\_L,RR\_LL,R\_LRL,R\_RLL\}$。

对于 $100\%$ 的数据，$1\leq n\leq 23,1\leq m\leq 10^6,1\leq C\leq 100$，所有可能出现在该数据点的状态均为等概率出现（也就是说你可以认为最后一个点中每种状态的 $a_i$ 之和大约为 $10^8/23$。

测试点编号 $T$	$C$	$m$	其他
$1$	$=100$	$=1$	无限制
$2$		$\le 5$
$3$		$\le 8$	$n=m$
$4$		$\le 10$
$5 \sim 6$		无限制	$n=1$
$7$		$\le 500$	只含 $5-$ 不可达点
$8$		$\le 6 \times 10^5$
$9$		$\le 100$	只含 $2-$ 不可达点
$10$		$\le 7 \times 10^5$
$11$		$\le 16$	只含 $1-$ 不可达点
$12$		$\le 8 \times 10^5$
$13$		$\le 14$	只含 $0-$ 不可达点
$14$		$\le 9 \times 10^5$
$15$		$\le 15$	无限制
$16$		$\le 5000$
$17$		$\le 10^5$
$18$		$\le 2 \times 10^5$
$19 \sim 20$		无限制