CF1835A.k-th equality

Consider all equalities of form $a + b = c$, where $a$ has $A$ digits, $b$ has $B$ digits, and $c$ has $C$ digits. All the numbers are positive integers and are written without leading zeroes. Find the $k$-th lexicographically smallest equality when written as a string like above or determine that it does not exist.

For example, the first three equalities satisfying $A = 1$, $B = 1$, $C = 2$ are

• $1 + 9 = 10$,
• $2 + 8 = 10$,
• $2 + 9 = 11$.

An equality $s$ is lexicographically smaller than an equality $t$ with the same lengths of the numbers if and only if the following holds:

• in the first position where $s$ and $t$ differ, the equality $s$ has a smaller digit than the corresponding digit in $t$.

考虑所有形如 $a + b = c$ 的等式，其中 $a$ 有 $A$ 位数字，$b$ 有 $B$ 位数字，$c$ 有 $C$ 位数字。所有数字均为正整数，且均不带前导零。请找出按字典序排列的第 $k$ 小的等式（将等式视为形如上述的字符串），若不存在则说明之。

例如，满足 $A = 1$、$B = 1$、$C = 2$ 的前三个等式为：

• $1 + 9 = 10$，
• $2 + 8 = 10$，
• $2 + 9 = 11$。

当两个等式所含各数的位数相同时，等式 $s$ 字典序小于等式 $t$ 当且仅当满足以下条件：

• 在 $s$ 与 $t$ 首次出现差异的位置上，$s$ 中对应位置的数字小于 $t$ 中对应位置的数字。

Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases. The description of test cases follows.

The first line of each test case contains integers $A$, $B$, $C$, $k$ ($1 \leq A, B, C \leq 6$, $1 \leq k \leq 10^{12}$).

Each input file has at most $5$ test cases which do not satisfy $A, B, C \leq 3$.

每个测试包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^3$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含整数 $A$、$B$、$C$、$k$（$1 \leq A, B, C \leq 6$，$1 \leq k \leq 10^{12}$）。

每个输入文件中，最多有 $5$ 个测试用例不满足 $A, B, C \leq 3$。

For each test case, if there are strictly less than $k$ valid equalities, output $-1$.

Otherwise, output the $k$-th equality as a string of form $a + b = c$.

对于每个测试用例，如果有效等式的数量严格少于 $k$，则输出 $-1$。

否则，输出第 $k$ 个等式，格式为字符串 $a + b = c$。

In the first test case, the first $9$ solutions are: $\langle 1, 1, 2 \rangle, \langle 1, 2, 3 \rangle, \langle 1, 3, 4 \rangle, \langle 1, 4, 5 \rangle, \langle 1, 5, 6 \rangle, \langle 1, 6, 7 \rangle, \langle 1, 7, 8 \rangle, \langle 1, 8, 9 \rangle, \langle 2, 1, 3 \rangle$.

Int the third test case, there are no solutions as the smallest possible values for $a$ and $b$ are larger than the maximal possible value of $c$ — $10 + 10 = 20 \gt 9$.

Please note that whitespaces in the output matter.

在第一个测试用例中，前 $9$ 个解为：$\langle 1, 1, 2 \rangle, \langle 1, 2, 3 \rangle, \langle 1, 3, 4 \rangle, \langle 1, 4, 5 \rangle, \langle 1, 5, 6 \rangle, \langle 1, 6, 7 \rangle, \langle 1, 7, 8 \rangle, \langle 1, 8, 9 \rangle, \langle 2, 1, 3 \rangle$。

在第三个测试用例中，不存在解，因为 $a$ 和 $b$ 的最小可能取值之和已超过 $c$ 的最大可能取值——$10 + 10 = 20 \gt 9$。

请注意，输出中的空白字符（空格）是重要的。