AT_arc132_f [ARC132F] Takahashi The Strongest

[problemUrl]: https://atcoder.jp/contests/arc132/tasks/arc132_f 高橋くん、青木くん、すぬけくんの $ 3 $ 人が、じゃんけんを $ k $ 回するゲームで対戦します。 `P`, `R`, `S` からなる長さ $ k $ の文字列を **作戦** と呼びます。ゲームは次のような流れで進行します。 - 参加者がそれぞれ作戦を選ぶ。 - じゃんけんを $ k $ 回行う。$ i $ 回目では、それぞれの参加者は、選んだ作戦の $ i $ 文字目に応じた手を出す。具体的には、`P` であればパーを、`R` であればグーを、`S` であればチョキを出す。 青木くんは $ n $ 個の作戦 $ a_1,\dots,a_n $ のうち $ 1 $ つを等確率でランダムに選びます。 すぬけくんは $ m $ 個の作戦 $ b_1,\dots,b_m $ のうち $ 1 $ つを等確率でランダムに選びます。 ただし、$ 2 $ 人の選び方は独立であるとします。 $ k $ 回のじゃんけんのうち、高橋くん**だけ**が勝った回が $ 1 $ 回でもあった場合、高橋くんは喜びます。 ありうる $ 3^k $ 通りの作戦それぞれについて、高橋くんがその作戦を選んだときに喜ぶ確率を求め、その $ nm $ 倍を整数として出力してください（この値は整数となることが証明できます）。

入力は以下の形式で標準入力から与えられる。 > $ k $ $ n $ $ m $ $ a_1 $ $ \vdots $ $ a_n $ $ b_1 $ $ \vdots $ $ b_m $

$ 3^k $ 個の値を出力せよ。$ i $ 個目には、ありうる作戦のうち辞書順で $ i $ 番目のものを高橋くんが選んだときの答えを出力せよ。

### 注意 $ 3 $ 人でじゃんけんをしたとき、高橋くんだけが勝つ場合は次の $ 3 $ 通りです。 - 高橋くんがパーを出し、青木くんとすぬけくんがグーを出す - 高橋くんがグーを出し、青木くんとすぬけくんがチョキを出す - 高橋くんがチョキを出し、青木くんとすぬけくんがパーを出す ### 制約 - $ 1\ \leq\ k\ \leq\ 12 $ - $ 1\ \leq\ n,m\ \leq\ 3^k $ - $ a_i,b_i $ は `P`, `R`, `S` からなる長さ $ k $ の文字列 - $ a_1,\dots,a_n $ は相異なる - $ b_1,\dots,b_m $ は相異なる ### Sample Explanation 1 青木くんが選ぶ作戦は `RS` です。 すぬけくんが作戦として `RP` を選んだ場合、条件を満たす高橋くんの作戦は `PP`, `PR`, `PS` です。 すぬけくんが作戦として `RR` を選んだ場合、条件を満たす高橋くんの作戦は `PP`, `PR`, `PS` です。 すぬけくんが作戦として `RS` を選んだ場合、条件を満たす高橋くんの作戦は `PP`, `PR`, `PS`, `RR`, `SR` です。 以上より、高橋くんの作戦が `PP`, `PR`, `PS`, `RP`, `RR`, `RS`, `SP`, `SR`, `SS` であるときの確率はそれぞれ $ 1,1,1,0,\frac\ 13,0,0,\frac\ 13,0 $ です。 これらを $ 3 $ 倍した値を出力してください。