{"problem":{"name":"Takahashi The Strongest","description":{"content":"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. *   Ea","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc132_f"},"statements":[{"statement_type":"Markdown","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).\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]\n\n## Notes\n\nIn 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.","is_translate":false,"language":"English"}],"meta":{"iden":"arc132_f","tags":[],"sample_group":[["2 1 3\nRS\nRP\nRR\nRS","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$."],["3 5 4\nRRP\nSSS\nRSR\nPPP\nRSS\nPPS\nSRP\nSSP\nRRS","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"]],"created_at":"2026-03-03 11:01:14"}}