AT_abc430_f [ABC430F] Back and Forth Filling

整数 $ N $ と長さ $ N-1 $ の `L`, `R` からなる文字列 $ S $ が与えられます。 横一列に並んだ $ N $ 個のマス目に、以下の条件を全て満たすように整数を書き込むことを考えます。 - 全てのマスに整数が $ 1 $ つ書かれている。 - 整数 $ 1,2,\dots,N $ が書かれているマスが $ 1 $ つずつ存在する。 - $ S $ の $ i $ 文字目 が `L` であるとき、 $ i+1 $ は $ i $ より左に書き込まれている。 - $ S $ の $ i $ 文字目 が `R` であるとき、 $ i+1 $ は $ i $ より右に書き込まれている。 $ C_i $ を「左から $ i $ マス目に書き込まれる整数としてありうるものの個数」とします。 $ C_1,C_2,\dots,C_N $ を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ S $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースについて、答えを以下の形式で出力せよ。 > $ C_1 $ $ C_2 $ $ \dots $ $ C_N $

### Sample Explanation 1 この入力には $ 5 $ 個のテストケースが含まれます。 - $ 1 $ 番目のテストケースにおいて、マス目の埋め方として考えられるものは以下の $ 11 $ 個です。 - $ (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) $ - ここから、 $ C_i $ の各値は次の通りに求まります。 - 左から $ 1 $ マス目に書き込まれる整数としてありうるものは $ 1,4 $ の $ 2 $ 個です。 - 左から $ 2 $ マス目に書き込まれる整数としてありうるものは $ 1,3,4,5 $ の $ 4 $ 個です。 - 左から $ 3 $ マス目に書き込まれる整数としてありうるものは $ 1,3,5 $ の $ 3 $ 個です。 - 左から $ 4 $ マス目に書き込まれる整数としてありうるものは $ 1,2,3,5 $ の $ 4 $ 個です。 - 左から $ 5 $ マス目に書き込まれる整数としてありうるものは $ 2,5 $ の $ 2 $ 個です。 - $ 2 $ 番目のテストケースにおいて、マス目の埋め方として考えられるものは以下の $ 2 $ 通りです。 - $ (1,3,2) $ - $ (3,1,2) $ - $ 3 $ 番目のテストケースにおいて、マス目の埋め方として考えられるものは以下の $ 1 $ 通りです。 - $ (2,1) $ - $ 4 $ 番目のテストケースにおいて、マス目の埋め方として考えられるものは以下の $ 1 $ 通りです。 - $ (1,2,3) $ ### Constraints - $ 1 \le T \le 20000 $ - $ 2 \le N \le 3 \times 10^5 $ - $ S $ は長さ $ N-1 $ の `L`, `R` からなる文字列 - ひとつの入力について、 $ N $ の総和は $ 3 \times 10^5 $ を超えない