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 翻译