Description

One day, little d found a classic mini‑game: frog jumping.

The game is played on a board with 5 cells. At the beginning, there is one frog facing right on each of the two leftmost cells, and one frog facing left on each of the two rightmost cells.

In each move, you can choose a frog and either move it one cell forward into an empty cell, or jump over one frog in front of it that faces the opposite direction and land in an empty cell.

To help you better understand the game, we provide a demo as a reference (note: the board size in the demo is not the same as in the problem).

This game itself is of course easy for little d, and he quickly solved it. But playing alone is too lonely, so little d asked little m to play together. They agreed that little d can only control frogs facing right, and little m can only control frogs facing left.

Little d soon found that if the two players strictly alternate turns, then it is impossible to reach the end state where all frogs swap sides. So, little d opened m parallel games and stipulated that the two players alternate turns; on each turn they must choose exactly one of the games and move one of their own frogs in that game (they cannot pass). Little d found that with this setup, in most of the games the frogs can eventually swap sides.

Since little d is good at trolling teammates, after a while they started trying to trap each other, both hoping to make the other unable to move. They agreed that when it is a player's turn, if none of that player's frogs in any remaining game can move, then the opponent wins the match. Just as the game theory master little d was calculating who would be the final winner, the computer froze. Little d realized he had to kill some games to let the rest proceed. Since the computer had already frozen, he could not freely choose which games to kill, and could only run the system’s built‑in random kill program. Specifically, after running this random kill program, each game is killed independently with probability 1/2 and survives with probability 1/2.

After thinking for a while, little d decided that if his winning probability after running the program was too low, he would just reboot the computer. At this moment, little d suddenly realized he no longer remembered whose turn it was, so he decided to consider both the first‑move and second‑move winning probabilities.

Little d is not good at probability, and he wants you to tell him, after running the program, the probabilities that the remaining overall position is: d must win, m must win, first player must win, or second player must win. This will help him decide whether to reboot.

To avoid precision issues, output each probability multiplied by $2^m$ and then taken modulo $998244353$.

Note: The problem does not guarantee that the total number of moves previously made by little m and little d across all m games differs by at most 1, but it guarantees that no state that is unreachable from the initial state appears.

Input Format

Read from standard input.

We use a string of length 5 to represent a state. L denotes a frog facing right, R denotes a frog facing left, and _ (underscore) denotes an empty cell. For example, the initial state is LL_RR.

This problem contains multiple datasets. The first line contains two integers $T, C$ ($1 \leq C \leq 100$), denoting the testset ID and the number of datasets, respectively.

For each dataset, the first line contains an integer $n$ ($1 \leq n \leq 23$) denoting the number of distinct board states. Then follow $n$ lines, each containing a length‑5 string $s_i$ and a positive integer $a_i$ ($1 \leq a_i \leq 10^6$), representing a state and the number of boards in that state.

All input strings are valid and pairwise distinct.

Output Format

Output to standard output.

Let $m = \sum a_i$.

For each dataset, output one line with four integers, denoting the probabilities that little d must win (i.e., the controller of L must win), little m must win (i.e., the controller of R must win), the first player must win, and the second player must win, respectively, each multiplied by $2^m$ and then taken modulo $998244353$.

0 1
1
LL_RR 1

0 0 1 1

0 1
3
LRRL_ 1
LRR_L 1
LLR_R 1

4 2 0 2

0 1
1
LRRL_ 1000000

421273116 0 0 1

Hint

Sample 1 explanation: For Sample 1, if that game is not killed, the only possible move sequence is LL_RR -> L_LRR -> LRL_R -> LR_LR -> LRRL_ -> LRR_L -> L wins; similarly when little m moves first, so in this case the first player must win. If that game is killed, neither player has a legal move, and the second player must win.

Sample 2 explanation: For Sample 2, let the three board states from top to bottom be A, B, C. Then $\{A,B,C\}, \{A,B\}, \{A,C\}, \{A\}$ are d‑must‑win; $\{C\}, \{B,C\}$ are m‑must‑win; $\{B\}, \{\}$ are second‑player‑must‑win.

It is guaranteed that no state that is unreachable from LL_RR (such as RLLR_) appears in the data, so there are 23 legal states in total.

Define a k‑unreachable state as a legal state that is still unreachable after making $k$ moves in total from LL_RR (the two players together make $k$ moves in any order). For example, the 1‑unreachable set is the universal set excluding {LL_RR, L_LRR, LLR_R}, which has 20 states; the 5‑unreachable set is {RLR_L, RRL_L, RR_LL, R_LRL, R_RLL}.

For 100% of the testdata, $1 \leq n \leq 23$, $1 \leq m \leq 10^6$, $1 \leq C \leq 100$, and all states that may appear in that testset are equally likely (that is, you may assume that in the last testset the sum of $a_i$ over each state is about $10^8 / 23$).

Translated by ChatGPT 5