Menji is playing a casual simulation game.

In this game, there are $n$ employees standing in order at positions $1, 2, 3, \dots, n$ on a number line. The $i$-th employee faces a direction $d_i$, which is either left or right.

Each employee has a weapon called a "Magic Bullet." Players take turns according to a permutation $p$. When it is the turn of player $x$: If the employee has already fallen, they do not perform any action. Otherwise, they fire a bullet in the direction they are facing. The bullet hits all not-yet-fallen players in that direction (if there are no players in that direction, no one is hit). Any employee hit by a bullet falls immediately.

Due to the chaotic situation, in the actual game, $p$ is chosen uniformly at random from all $n!$ possible permutations.

Menji wants to know, for each $1 \le k \le n$, how many permutations result in employee $k$ not falling by the end of the game.

Since the answer can be very large, you only need to output the answer modulo $998244353$.

Input

The first line contains an integer $n$ ($2 \le n \le 10^5$).

The next line contains a string $s$ of length $n$. Here $s_i \in \{\text{L}, \text{R}\}$. If $s_i = \text{L}$, the $i$-th employee faces left (the direction of employee $1$). If $s_i = \text{R}$, the $i$-th employee faces right (the direction of employee $n$).

Output

Output a single line containing $n$ integers, where the $k$-th number represents the number of permutations such that employee $k$ does not fall by the end of the game.

Examples

Input 1

2
RL

Output 1

1 1

Input 2

4
LLRR

Output 2

0 24 24 0

Input 3

4
RLRL

Output 3

9 6 6 9