Jumping Frog Conundrum

Two friends, Xiao d and Xiao m, are playing a variant of the classic jumping frog puzzle on a board with 5 cells. Initially the board is arranged as follows: the leftmost two cells contain frogs facing right (controlled by Xiao d), the rightmost two cells contain frogs facing left (controlled by Xiao m), and the middle cell is empty. In each move a frog may either slide into the adjacent empty cell in its forward direction or jump over a frog of the opposite direction (provided that the cell immediately beyond is empty).

Because in a single game the moves are forced and it turns out that if played to completion the final outcome is always a win for Xiao d, they decide to play not one but m independent games concurrently. The players take turns — on each turn a player chooses one of the m games (which has not ended yet) and makes one legal move with one of his frogs. However, they add one more twist: if a player, when it is his turn in a game, finds that none of his frogs can move, then the opponent is declared the winner of that game immediately.

When all m games are in progress, the computer crashes so that a system program randomly kills each game with probability 1/2 (independently). Only the games that are not killed will continue. (Note that the probability of a game surviving is 1/2 and the events are independent.)

Let the resulting collection of games be considered together as a disjunctive sum. It turns out that in every game the eventual outcome (if the game is allowed to continue) is a win for Xiao d – irrespective of whether the game’s current turn is for Xiao d or Xiao m. (In other words, if a game survives the random kill then Xiao d is destined to win that game under perfect play.) However, if a game is killed then it becomes an empty game; by definition the disjunctive sum of zero games is a win for the second mover.

Considering all m games, define the following four outcomes for the combined (random) position:

1. Xiao d forced win: The surviving games form a position which is a win for Xiao d (i.e. Xiao d wins whether he starts or not).
2. Xiao m forced win: The surviving games form a position which is a win for Xiao m regardless of the turn order.
3. First mover win: If the player whose turn it is (when the m games are combined) wins, the position is called first-mover‐winning.
4. Second mover win: Otherwise the position is second-mover‐winning.

Because the random kill program eliminates each game with probability 1/2 independently, if we let S be the set of games surviving, then:

• If S is nonempty, then each surviving game (being a continued game) is destined for Xiao d. Hence the combined outcome is a win for Xiao d – no matter who moves first.
• If S is empty (which happens with probability (1/2)^m), then the overall position is the disjunctive sum of zero games. By convention the zero game is a second-mover win.

Your task is: Given the integer m followed by m game states (each a 5–character string representing a reachable board state in the jumping frog puzzle – note that the states are guaranteed to be reachable from the standard initial arrangement), compute the following four numbers modulo 998244353 after multiplying the probability (expressed as a rational number) by 2^m:

• The number for which the combined position is a forced win for Xiao d. • The number for which the combined position is a forced win for Xiao m. • The number for which the combined position is winning for the first mover. • The number for which the combined position is winning for the second mover.

It turns out that because every game (if it survives) is destined for Xiao d, the answers can be derived as follows. If we let P be the number of surviving games, then P > 0 guarantees a win for Xiao d, while P = 0 gives a win for the second mover. In other words, if we denote 2^m by T then the answer is:

• Xiao d forced win: T - 1
• Xiao m forced win: 0
• First mover win: T - 1 (since if Xiao d is first then his win occurs only when at least one game survives)
• Second mover win: T (since if Xiao d is second then he wins regardless, and when no game survives the second mover wins by definition)

Output these four numbers modulo 998244353.

Note: To avoid floating–point precision issues, the answer must be given after multiplying by 2^m and then taken modulo 998244353.

Input Format: The first line contains an integer m (1 ≤ m ≤ 10^5), the number of games. Each of the following m lines contains a 5–character string representing a game state. The characters will be either 'R' (a right–facing frog), 'L' (a left–facing frog) or '_' (an empty cell). It is guaranteed that the input state is reachable from the standard starting state: RR_LL (without quotes).

Output Format: Output four space–separated integers – the answers (i.e. the values for Xiao d forced win, Xiao m forced win, first mover win, and second mover win) after multiplying by 2^m, all taken modulo 998244353.

Example: Input:

1
RR_LL

Output:

1 0 1 2

In the sample, when m=1, the game is either continued (with probability 1/2) so that Xiao d wins or killed (with probability 1/2) so that the overall outcome (zero game) is a win for the second mover. Multiplying by 2 gives the above answers.

Explanation: For m games, the only losing case for Xiao d is when all games are killed (which happens in exactly 1 of the 2^m cases). In all other cases Xiao d wins. Thus, after scaling by 2^m, the count for Xiao d–win (and for first mover win when Xiao d is first) is 2^m - 1, while the second mover wins in the killed–games case when Xiao d is first, but always wins when Xiao d is second.

Note: The board states provided in the input might not be in the usual alternating–move order; however, they are guaranteed to be reachable from the starting configuration.

inputFormat

The first line contains an integer m (1 ≤ m ≤ 10^5). Each of the next m lines contains a string of exactly 5 characters. Each character is either 'R', 'L' or '_', representing the state of a cell on the board. It is guaranteed that each board state is reachable from the initial state "RR_LL".

outputFormat

Output four space–separated integers:

1. The value (multiplied by 2^m) for which the combined position is a forced win for Xiao d.
2. The value (multiplied by 2^m) for which the combined position is a forced win for Xiao m.
3. The value (multiplied by 2^m) for which the combined position is a win for the first mover.
4. The value (multiplied by 2^m) for which the combined position is a win for the second mover. All results must be given modulo 998244353.

sample

1
RR_LL

1 0 1 2

</p>