/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
高橋くん、青木くん、すぬけくんの 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 倍を整数として出力してください（この値は整数となることが証明できます）。
注意
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 は相異なる
入力
入力は以下の形式で標準入力から与えられる。
k n m a_1 \vdots a_n b_1 \vdots b_m
出力
3^k 個の値を出力せよ。i 個目には、ありうる作戦のうち辞書順で i 番目のものを高橋くんが選んだときの答えを出力せよ。
入力例 1
2 1 3 RS RP RR RS
出力例 1
3 3 3 0 1 0 0 1 0
青木くんが選ぶ作戦は 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 倍した値を出力してください。
入力例 2
3 5 4 RRP SSS RSR PPP RSS PPS SRP SSP RRS
出力例 2
4 7 7 6 9 10 4 7 8 4 8 7 4 8 8 3 7 7 3 7 6 4 8 8 1 5 5
Score : 900 points
Problem Statement
Takahashi, Aoki, and Snuke will play a game with k rounds of rock-paper-scissors.
Let us call a string of length k consisting of P, R, S a strategy. The game proceeds as follows.
- Each participant chooses a strategy.
- Play k rounds of rock-paper-scissors. In the i-th round, each participant plays the hand corresponding to the i-th character in the chosen strategy: paper for
P, rock forR, and scissors forS.
Aoki will randomly choose one strategy from the n strategies a_1,\dots,a_n with equal probability. Snuke will randomly choose one strategy from the m strategies b_1,\dots,b_m with equal probability. Their choices are independent of each other.
Takahashi will be happy if he is the only winner in at least one of the k rounds. For each of the 3^k possible strategies, find the probability that he becomes happy when choosing that strategy and print it multiplied by nm as an integer (it can be proved that this value is an integer).
Notes
In the game of rock-paper-scissors with three players, the following three scenarios make Takahashi the only winner.
- Takahashi plays paper, while Aoki and Snuke play rock.
- Takahashi plays rock, while Aoki and Snuke play scissors.
- Takahashi plays scissors, while Aoki and Snuke play paper.
Constraints
- 1 \leq k \leq 12
- 1 \leq n,m \leq 3^k
- Each of a_i and b_i is a string of length k consisting of
P,R,S. - a_1,\dots,a_n are distinct.
- b_1,\dots,b_m are distinct.
Input
Input is given from Standard Input in the following format:
k n m a_1 \vdots a_n b_1 \vdots b_m
Output
Print 3^k values. The i-th value should be the answer when Takahashi chooses the i-th lexicographically smallest possible strategy.
Sample Input 1
2 1 3 RS RP RR RS
Sample Output 1
3 3 3 0 1 0 0 1 0
Aoki chooses the strategy RS.
If Snuke chooses the strategy RP, the strategies that can meet Takahashi's objective are PP, PR, PS.
If Snuke chooses the strategy RR, the strategies that can meet Takahashi's objective are PP, PR, PS.
If Snuke chooses the strategy RS, the strategies that can meet Takahashi's objective are PP, PR, PS, RR, SR.
Therefore, the probabilities when Takahashi chooses PP, PR, PS, RP, RR, RS, SP, SR, SS are 1, 1, 1, 0, \frac 13, 0, 0, \frac 13, 0, respectively.
Print them multiplied by 3.
Sample Input 2
3 5 4 RRP SSS RSR PPP RSS PPS SRP SSP RRS
Sample Output 2
4 7 7 6 9 10 4 7 8 4 8 7 4 8 8 3 7 7 3 7 6 4 8 8 1 5 5