{"problem":{"name":"[ICPC 2018 Qingdao R] Magic Multiplication","description":{"content":"BaoBao is now learning a new binary operation between two positive integers, represented by $\\otimes$, in his magic book. The book tells him that the result of such operation is calculated by concaten","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9888"},"statements":[{"statement_type":"Markdown","content":"BaoBao is now learning a new binary operation between two positive integers, represented by $\\otimes$, in his magic book. The book tells him that the result of such operation is calculated by concatenating all multiple results of each digit in the two integers.\n\nFormally speaking, let the first integer be $A = a_1a_2 \\dots a_n$, where $a_i$ indicates the $i$-th digit in $A$, and the second integer be $B = b_1b_2 \\dots b_m$, where $b_i$ indicates the $i$-th digit in $B$. We have \n\n$$A \\otimes B = \\sum\\limits_{i=1}^n\\sum\\limits_{j=1}^m a_ib_j = a_1b_1 + a_1b_2 + \\dots + a_1b_m + a_2b_1 + \\dots + a_nb_m$$ \n\nNote that the result of $a_ib_j$ is considered to be a $\\textbf{string}$ (without leading zeros if $a_ib_j > 0$, or contains exactly one `0` if $a_ib_j = 0$), NOT a normal integer. Also, the sum here means $\\textbf{string concatenation}$, NOT the normal addition operation.\n\nFor example, $23 \\otimes 45 = 8101215$. Because $8=2 \\times 4$, $10=2 \\times 5$, $12=3 \\times 4$ and $15=3 \\times 5$.\n\nBaoBao is very smart and soon knows how to do the inverse operation of $\\otimes$. Now he gives you the result of a $\\otimes$ operation and the numbers of digits in the two original integers. Please help him to restore the two original integers $A$ and $B$.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\n\nThe first line contains two positive integers $n$ and $m$ ($1 \\le n, m \\le 2 \\times 10^5$), where $n$ indicates the length of $A$ and $m$ indicates the length of $B$. Here length of an integer means the length of the string when writing the number in decimal notation without leading zeros.\n\nThe second line contains only one positive integer $C$ without leading zeros, indicating the result of $A \\otimes B$. The length of $C$ is no more than $2 \\times 10^5$.\n\nIt's guaranteed that the sum of lengths of $C$ over all test cases will not exceed $2 \\times 10^6$.\n\n## Output\n\nFor each test case output one line.\n\nIf there exist such $A$ and $B$ that $A \\otimes B = C$, output one line containing two integers $A$ and $B$ separated by one space. Note that $A$ and $B$ should be positive integers without leading zeros, the length of $A$ should be exactly $n$, and the length of $B$ should be exactly $m$.\n\nIf there are multiple valid answers, output the answer with the smallest $A$; If there are still more than one answer, output one of them with the smallest $B$.\n\nIf such $A$ and $B$ do not exist, print ``Impossible`` (without quotes) on a single line.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9888","tags":["模拟","2018","O2优化","枚举","ICPC","青岛"],"sample_group":[["4\n2 2\n8101215\n3 4\n100000001000\n2 2\n80101215\n3 4\n1000000010000","23 45\n101 1000\nImpossible\nImpossible"]],"created_at":"2026-03-03 11:09:25"}}