AT_abc430_f [ABC430F] Back and Forth Filling

You are given an integer $ N $ and a string $ S $ of length $ N-1 $ consisting of `L` and `R`. Consider writing integers into $ N $ cells arranged in a row so that the following conditions are satisfied: - Every cell has one integer written on it. - Every integer $ 1,2,\dots,N $ appears in exactly one cell. - When the $ i $ -th character of $ S $ is `L`, $ i+1 $ is written to the left of $ i $ . - When the $ i $ -th character of $ S $ is `R`, $ i+1 $ is written to the right of $ i $ . Let $ C_i $ be the number of integers that can be written in the $ i $ -th cell from the left. Find $ C_1,C_2,\dots,C_N $ . You are given $ T $ test cases; find the answer for each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ S $

Print $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case in the following format: > $ C_1 $ $ C_2 $ $ \dots $ $ C_N $

### Sample Explanation 1 This input contains five test cases. - For the first test case, there are $ 11 $ possible ways to fill the cells as follows: - $ (1,4,3,2,5) $ - $ (1,4,3,5,2) $ - $ (1,4,5,3,2) $ - $ (4,1,3,2,5) $ - $ (4,1,3,5,2) $ - $ (4,1,5,3,2) $ - $ (4,3,1,2,5) $ - $ (4,3,1,5,2) $ - $ (4,3,5,1,2) $ - $ (4,5,1,3,2) $ - $ (4,5,3,1,2) $ - From this, each value of $ C_i $ is determined as follows: - The integers that can be written in the $ 1 $ -st cell from the left are $ 1,4 $ , which is two integers. - The integers that can be written in the $ 2 $ -nd cell from the left are $ 1,3,4,5 $ , which is four integers. - The integers that can be written in the $ 3 $ -rd cell from the left are $ 1,3,5 $ , which is three integers. - The integers that can be written in the $ 4 $ -th cell from the left are $ 1,2,3,5 $ , which is four integers. - The integers that can be written in the $ 5 $ -th cell from the left are $ 2,5 $ , which is two integers. - For the second test case, there are two possible ways to fill the cells as follows: - $ (1,3,2) $ - $ (3,1,2) $ - For the third test case, there is one possible way to fill the cells as follows: - $ (2,1) $ - For the fourth test case, there is one possible way to fill the cells as follows: - $ (1,2,3) $ ### Constraints - $ 1 \le T \le 20000 $ - $ 2 \le N \le 3 \times 10^5 $ - $ S $ is a string of length $ N-1 $ consisting of `L` and `R`. - For a single input, the sum of $ N $ does not exceed $ 3 \times 10^5 $ .