Little D is a master of 4xx9 mini-games.

One day, Little D discovered a classic mini-game: Jumping Frogs.

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

In each move, you can select a frog and move it one cell forward into an empty cell, or jump over one frog facing a different direction into an empty cell.

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

This game itself is certainly not difficult for Little D, and he solved it easily. However, playing alone is too lonely, so Little D found Little M to play with him. Little D stipulated that he can only control the frogs facing right, and Little M can only control the frogs facing left.

Little D soon discovered that if the game requires both sides to take turns, it is impossible to reach the game state where all frogs are swapped. Therefore, Little D opened m games and stipulated that both sides take turns, choosing one of the games each time and moving one of their own frogs one step (they cannot choose to skip a turn). Little D found that by doing this, most of the games could eventually have all frogs swapped.

Since Little D is a master at sabotaging his teammates, after playing for a while, they started to sabotage each other, both hoping to make the other unable to move. They agreed that when it is a player's turn, if all of their frogs are unable to move, the opponent wins the game. Just as the game theory master Little D was calculating who would be the final winner, the computer crashed. Little D found that he could only kill some games to allow the remaining games to continue. Since the computer had already crashed, Little D could not freely choose which games to kill and could only run the system's built-in random kill program. Specifically, after Little D runs this random kill program, each game has a $\frac{1}{2}$ probability of being killed and a $\frac{1}{2}$ probability of continuing. The probabilities of games being killed are independent.

Little D thought for a while and decided that if his win rate was too low after running the program, he would just restart the computer. At this moment, Little D suddenly realized that he didn't remember whose turn it was, so he decided to consider his win rates as both the first and second player.

Little D is not good at probability theory, and he wants you to tell him the probabilities that the remaining situation results in a win for Little D, a win for Little M, a win for the first player, and a win for the second player, so that he can better decide whether to restart the computer.

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

Note: The problem does not guarantee that the total number of moves made by Little M and Little D in all m input states differs by no more than 1, but it is guaranteed that no unreachable states from the starting state will appear.

Input

The input is read from standard input.

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

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

For each test case, 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 a positive integer $a_i$ ($1\leq a_i\leq 10^6$), representing the board state and the number of boards in that state, respectively.

It is guaranteed that the input strings are valid and unique.

Output

The output is sent to standard output.

Define $m=\sum a_i$.

For each test case, output a single line containing four integers, representing the probabilities of a win for Little D (i.e., the controller of L wins), a win for Little M (i.e., the controller of R wins), a win for the first player, and a win for the second player, each multiplied by $2^m$ and taken modulo $998244353$.

Examples

Input 1

0 1
1
LL_RR 1

Output 1

0 0 1 1

Note 1

For Example 1, if the game is not killed, the only possible sequence of moves for both sides is LL_RR -> L_LRR -> LRL_R -> LR_LR -> LRRL_ -> LRR_L -> L wins. The same applies if Little M goes first, so this case is a win for the first player. If the game is killed, neither side has a legal move, and the second player wins.

Input 2

0 1
3
LRRL_ 1
LRR_L 1
LLR_R 1

Output 2

4 2 0 2

Note 2

For Example 2, let the states of these three boards from top to bottom be A, B, C. Then $\{A, B, C\}, \{A, B\}, \{A, C\}, \{A\}$ are wins for Little D, $\{C\}, \{B, C\}$ are wins for Little M, and $\{B\}, \{\}$ are wins for the second player.

Input 3

0 1
1
LRRL_ 1000000

Output 3

421273116 0 0 1

Constraints

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

Define a $k$-unreachable point as a valid state that cannot be reached after $k$ operations from LL_RR (the total number of operations by both sides combined is $k$, in any order). For example, 1-unreachable points are: the set of all states $\setminus$ {LL_RR, L_LRR, LLR_R}, totaling 20 states. 5-unreachable points are {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$. All states that may appear in a test point are equally likely to appear (meaning you can assume that in the last point, the sum of $a_i$ for each state is approximately $10^8/23$).