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 for R, and scissors for S.

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).

Note

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.