题目描述

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.

Formally 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

$$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 $$

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

For example, $23 \otimes 45 = 8101215$. Because $8=2 \times 4$, $10=2 \times 5$, $12=3 \times 4$ and $15=3 \times 5$.

BaoBao 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$.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

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

The 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$.

It's guaranteed that the sum of lengths of $C$ over all test cases will not exceed $2 \times 10^6$.

输出格式

For each test case output one line.

If 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$.

If 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$.

If such $A$ and $B$ do not exist, print Impossible (without quotes) on a single line.

题目大意

BaoBao 现在正在他的魔法书中学习两个正整数之间的一种新的二进制运算，用 $\otimes$ 表示。这本书告诉他，这种运算的结果是通过将两个整数中每个数字的所有多个结果串联起来计算的。

形式上讲，让第一个整数为 $A=A_1a_2\dots A_n$，其中 $A_i$ 表示 $A$ 中的第 $i$ 位，第二个整数为 $B=B_1b_2\dots B_m$，其中 $B_i$ 表示 $B$ 中的第一位。我们有

$$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 $$

请注意，$a_ib_j$ 的结果被认为是 $\textbf{string}$（如果 $a_ib_j>0$，则不带前导零，或者如果 $a_ib_j > 0$，则仅包含一个 $0$），而不是正常整数。此外，这里的 sum 表示 $\textbf{string concatenation}$，而不是正常的加法运算。

例如，$23\otimes 45=8101215$。因为 $8=2\times 4$，$10=2\times 5$，$12=3\times 4$ 和 $15=3\times 5$。

BaoBao 很聪明，很快就知道如何做 $\otimes$ 的逆运算。现在，他给出了 $\otimes$ 运算的结果以及两个原始整数中的位数。请帮助他恢复两个原始整数 $A$ 和 $B$。

输入格式

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含两个正整数 $n$ 和 $m$（$1\le n,m\le 2\times 10^5$），其中 $n$ 表示 $A$ 的长度，$m$ 表示 $B$ 的长度。这里，整数的长度是指在不带前导零的十进制记数法中写入数字时字符串的长度。

第二行只包含一个不带前导零的正整数 $C$，表示 $A\otimes B$ 的结果。$C$ 的长度不超过 $2\times 10^5$。

保证所有测试用例的 $C$ 长度总和不会超过 $2\times 10^6$。

输出格式

对于每个测试用例输出一行。

如果存在这样的 $A$ 和 $B$，$A\otimes B=C$，则输出一行，其中包含由一个空格分隔的两个整数 $A$ 与 $B$。请注意，$A$ 和 $B$ 应该是不带前导零的正整数，$A$ 的长度应该正好是 $n$，$B$ 的长度应正好是 $m$。

如果存在多个有效答案，则输出具有最小 $A$ 的答案；如果仍然有一个以上的答案，请输出其中一个最小的 $B$。

如果不存在这样的 $A$ 和 $B$，请在单行上打印 Impossible（不带引号）。

4
2 2
8101215
3 4
100000001000
2 2
80101215
3 4
1000000010000

23 45
101 1000
Impossible
Impossible