Background

Xiao d is a master at 4xx9 mini-games.

Problem Description

One day, Xiao d discovered a classic mini-game: Frog Jumping.

The game is played on a board with 5 squares. At the beginning, the two leftmost squares each have a frog facing right, and the two rightmost squares each have a frog facing left.

Each move involves selecting a frog and moving it one square forward to an empty square or jumping over a frog facing the opposite direction and moving to an empty square.

To help you better understand the game, we have provided a game demo as a reference (note: the board size in the demo is different from the one in the problem).

This game is no challenge for Xiao d, who easily solved it. However, playing alone is too lonely, so Xiao d found Xiao m to play with him. Xiao d stipulated that he could only control the frogs facing right, and Xiao m could only control the frogs facing left.

Xiao d quickly realized that to achieve the goal of swapping all frogs while taking turns, they could not play a single game. Therefore, Xiao d opened m games and agreed to take turns, each selecting one game and moving their frog one step (not staying still). Xiao d found that this way, most games could eventually swap all frogs.

Since Xiao d is a master at tricking teammates, they soon started to sabotage each other, hoping to make the other unable to move. They agreed that when it's one's turn and all their frogs cannot move, the other wins. Just as the game theory expert Xiao d was calculating who would be the ultimate winner, the computer froze. Xiao d found that he could only continue the games by randomly killing some of them using a system-provided random kill program. Specifically, after running this program, each game has a 1/2 probability of being killed and a 1/2 probability of continuing. The probabilities of games being killed are independent.

Xiao d thought for a while and decided to restart the computer if his win rate after running the program was too low. At this moment, Xiao d suddenly forgot whose turn it was, so he decided to consider both the win rates when he goes first and second.

Xiao d is not good at probability theory, and he wants you to tell him the probabilities of the remaining games being a win for Xiao d, Xiao m, the first player, and the second player after running the program. This way, he can better decide whether to restart the computer.

To avoid precision issues, output the answer multiplied by $2^m$ and modulo $998244353$.

Note: The problem does not guarantee that the total number of moves made by Xiao m and Xiao d in all m states differs by no more than 1, but it guarantees that no unreachable starting states will appear.

Input Format

Read data from standard input.

A state is represented by a string of length 5, where L denotes a frog facing right, R denotes a frog facing left, and _ (underscore) denotes an empty square. For example, the initial state is LL_RR.

The input contains multiple sets of data. The first line contains two integers $T, C$ ($1 \leq C \leq 100$), representing the test point number and the number of data sets, respectively.

For each set of data, the first line contains an integer $n$ ($1 \leq n \leq 23$), representing the number of different board states. The next n lines each contain a string $s_i$ of length 5 and an integer $a_i$ ($1 \leq a_i \leq 10^6$), representing the board state and the number of boards in that state, respectively.

The input strings are guaranteed to be valid and unique.

Output Format

Output to standard output.

Define $m = \sum a_i$.

For each set of data, output one line containing four integers, representing the probabilities of Xiao d (the controller of L) winning, Xiao m (the controller of R) winning, the first player winning, and the second player winning, respectively, multiplied by $2^m$ and modulo $998244353$.

Sample Input and Output

Sample Input #1

0 1
1
LL_RR 1

Sample Output #1

0 0 1 1

Sample Input #2

0 1
3
LRRL_ 1
LRR_L 1
LLR_R 1

Sample Output #2

4 2 0 2

Sample Input #3

0 1
1
LRRL_ 1000000

Sample Output #3

421273116 0 0 1

Notes/Hints

Sample 1 Explanation
For Sample 1, if the game is not killed, the only possible sequence of moves is LL_RR -> L_LRR -> LRL_R -> LR_LR -> LRRL_ -> LRR_L -> L wins, and the same applies when Xiao m goes first, making it a first-player win. If the game is killed, neither player has a valid move, resulting in a second-player win.

Sample 2 Explanation
For Sample 2, label the three board states from top to bottom as A, B, C. Then, {A, B, C}, {A, B}, {A, C}, {A}, {A} are wins for Xiao d, {C}, {B, C} are wins for Xiao m, {B}, {} are second-player wins.

The data guarantees that no states unreachable from LL_RR will appear (e.g., RLLR_), so there are 23 valid states in total.

Define a $k$-unreachable state as a valid state that cannot be reached from LL_RR after $k$ moves (combined moves by both players in any order), such as 1-unreachable states: the set {LL_RR, L_LRR, LLR_R} with 20 states, and 5-unreachable states: {RLR_L, RRL_L, RR_LL, R_LRL, R_RLL}.

For 100% of the data, $1 \leq n \leq 23, 1 \leq m \leq 10^6, 1 \leq C \leq 100$, and all possible states in the data appear with equal probability (meaning you can assume the sum of $a_i$ for each state in the last data point is approximately $10^8/23$).

见题面 Input 部分

见题面 Output 部分