题目描述

高橋くん、青木くん、すぬけくんの $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$ 番目のものを高橋くんが選んだときの答えを出力せよ。

题目大意

小 $A,B,C$ 在玩石头剪刀布，分别用 $R,S,P$ 表示。小 $A$ 有 $n$ 个策略，小 $B$ 有 $m$ 个策略，一个策略是一个长度为 $k$ 的包含 $R,S,P$ 的字符串，表示每一局会固定出什么。对于小 $C$ 的一种策略，如果在中途某一次小 $C$ 是绝对赢家，那么小 $C$ 会开心。对于小 $C$ 每种可能的策略，求出有多少种 $A,B$ 的组合策略（一共有 $nm$ 种组合）使得小 $C$ 会开心。

• $1\leq k\leq 12,1\leq n,m\leq 3^k$

2 1 3
RS
RP
RR
RS

3
3
3
0
1
0
0
1
0

3 5 4
RRP
SSS
RSR
PPP
RSS
PPS
SRP
SSP
RRS

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

提示

注意

$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$ 倍した値を出力してください。