AT_arc132_f.[ARC132F] Takahashi The Strongest

高桥君、青木君和すぬけ君三个人进行 $k$ 次猜拳游戏。

由 P、R、S 组成的长度为 $k$ 的字符串称为作战方案。游戏流程如下：

• 每位参与者各自选择一个作战方案。
• 进行 $k$ 次猜拳。在第 $i$ 次时，每位参与者根据所选作战方案的第 $i$ 个字符出拳。具体来说，P 表示出“布”，R 表示出“石头”，S 表示出“剪刀”。

青木君会从 $n$ 个作战方案 $a_1,\dots,a_n$ 中等概率随机选择一个。すぬけ君会从 $m$ 个作战方案 $b_1,\dots,b_m$ 中等概率随机选择一个。两人的选择是独立的。

如果在 $k$ 次猜拳中，有至少一次只有高桥君获胜，则高桥君会感到高兴。对于所有可能的 $3^k$ 种作战方案，求出当高桥君选择该作战方案时他感到高兴的概率，并输出该概率乘以 $nm$ 后的整数值（可以证明该值一定为整数）。

输入按以下格式从标准输入读入。

$k$ $n$ $m$
$a_1$
$\vdots$
$a_n$
$b_1$
$\vdots$
$b_m$

请输出 $3^k$ 个值。第 $i$ 个值表示当高桥君选择按字典序排列的第 $i$ 个作战方案时的答案。

注意

当三个人猜拳时，只有高桥君获胜的情况有以下三种：

• 高桥君出“布”，青木君和すぬけ君都出“石头”；
• 高桥君出“石头”，青木君和すぬけ君都出“剪刀”；
• 高桥君出“剪刀”，青木君和すぬけ君都出“布”。

约束条件

• $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$ 互不相同

样例解释 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{1}{3},0,0,\frac{1}{3},0$。输出时请将这些概率乘以 $3$ 后的值输出。

由 ChatGPT 4.1 翻译