题目描述

Takahashi、Aoki 和 Snuke 将进行 $k$ 轮剪刀石头布的游戏。

我们将长度为 $k$ 的字符串，由 P、R 和 S 组成的字符串称为 策略。游戏过程如下：

• 每个参与者选择一种策略。
• 进行 $k$ 轮剪刀石头布。在第 $i$ 轮中，每个参与者出示一个手势，手势对应于所选策略中的第 $i$ 个字符：P 表示纸，R 表示石头，S 表示剪刀。

Aoki 以相等的概率随机选择 $n$ 种策略 $a_1,\\dots,a_n$ 中的一种。Snuke 以相等的概率随机选择 $m$ 种策略 $b_1,\\dots,b_m$ 中的一种。他们的选择相互独立。

如果 Takahashi 在至少一轮中是唯一的获胜者，他将感到高兴。对于所有 $3^k$ 种可能的策略，找到他选择该策略时变得高兴的概率，并将其乘以 $nm$ 打印为整数（可以证明该值为整数）。

注意事项

在三人剪刀石头布游戏中，以下三种情况使得 Takahashi 是唯一的获胜者：

• Takahashi 出示纸，而 Aoki 和 Snuke 出示石头。
• Takahashi 出示石头，而 Aoki 和 Snuke 出示剪刀。
• Takahashi 出示剪刀，而 Aoki 和 Snuke 出示纸。

约束条件

• $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$ 个值应该是当 Takahashi 选择字典序最小的第 $i$ 种策略时的答案。

示例输入1

2 1 3
RS
RP
RR
RS

示例输出1

3
3
3
0
1
0
0
1
0

Aoki 选择了策略 RS。

如果 Snuke 选择了策略 RP，则满足 Takahashi 的条件的策略有 PP、PR、PS。

如果 Snuke 选择了策略 RR，则满足 Takahashi 的条件的策略有 PP、PR、PS。

如果 Snuke 选择了策略 RS，则满足 Takahashi 的条件的策略有 PP、PR、PS、RR、SR。

因此，当 Takahashi 选择了策略 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