{"raw_statement":[{"iden":"problem statement","content":"Takahashi, Aoki, and Snuke will play a game with $k$ rounds of rock-paper-scissors.\nLet us call a string of length $k$ consisting of `P`, `R`, `S` a **strategy**. The game proceeds as follows.\n\n*   Each participant chooses a strategy.\n*   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`.\n\nAoki 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.\nTakahashi 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)."},{"iden":"notes","content":"In the game of rock-paper-scissors with three players, the following three scenarios make Takahashi the only winner.\n\n*   Takahashi plays paper, while Aoki and Snuke play rock.\n*   Takahashi plays rock, while Aoki and Snuke play scissors.\n*   Takahashi plays scissors, while Aoki and Snuke play paper."},{"iden":"constraints","content":"*   $1 \\leq k \\leq 12$\n*   $1 \\leq n,m \\leq 3^k$\n*   Each of $a_i$ and $b_i$ is a string of length $k$ consisting of `P`, `R`, `S`.\n*   $a_1,\\dots,a_n$ are distinct.\n*   $b_1,\\dots,b_m$ are distinct."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$k$ $n$ $m$\n$a_1$\n$\\vdots$\n$a_n$\n$b_1$\n$\\vdots$\n$b_m$"},{"iden":"sample input 1","content":"2 1 3\nRS\nRP\nRR\nRS"},{"iden":"sample output 1","content":"3\n3\n3\n0\n1\n0\n0\n1\n0\n\nAoki chooses the strategy `RS`.\nIf Snuke chooses the strategy `RP`, the strategies that can meet Takahashi's objective are `PP`, `PR`, `PS`.\nIf Snuke chooses the strategy `RR`, the strategies that can meet Takahashi's objective are `PP`, `PR`, `PS`.\nIf Snuke chooses the strategy `RS`, the strategies that can meet Takahashi's objective are `PP`, `PR`, `PS`, `RR`, `SR`.\nTherefore, the probabilities when Takahashi chooses `PP`, `PR`, `PS`, `RP`, `RR`, `RS`, `SP`, `SR`, `SS` are $1$, $1$, $1$, $0$, $\\frac 13$, $0$, $0$, $\\frac 13$, $0$, respectively. Print them multiplied by $3$."},{"iden":"sample input 2","content":"3 5 4\nRRP\nSSS\nRSR\nPPP\nRSS\nPPS\nSRP\nSSP\nRRS"},{"iden":"sample output 2","content":"4\n7\n7\n6\n9\n10\n4\n7\n8\n4\n8\n7\n4\n8\n8\n3\n7\n7\n3\n7\n6\n4\n8\n8\n1\n5\n5"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}