310455: CF1836C. k-th equality

C. k-th equalitytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

Input

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

Output

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

ExampleInput

7
1 1 1 9
2 2 3 1
2 2 1 1
1 5 6 42
1 6 6 10000000
5 5 6 3031568815
6 6 6 1000000000000

Output

2 + 1 = 3
10 + 90 = 100
-1
9 + 99996 = 100005
-1
78506 + 28543 = 107049
-1

Note

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

Please note that whitespaces in the output matter.

题目大意：
本题要求解形式为 `a + b = c` 的等式，其中 `a` 有 `A` 位数字，`b` 有 `B` 位数字，`c` 有 `C` 位数字。所有数字都是正整数，并且书写时没有前导零。需要找到按字典序排列的第 `k` 个最小的等式，或者确定它不存在。

输入数据格式：
每个测试包含多个测试用例。输入的第一行包含一个整数 `t`（`1 ≤ t ≤ 10^3`），表示测试用例的数量。接下来的每一行代表一个测试用例，包含四个整数 `A`、`B`、`C`、`k`（`1 ≤ A, B, C ≤ 6`，`1 ≤ k ≤ 10^{12}`）。每个输入文件最多有 `5` 个不满足 `A, B, C ≤ 3` 的测试用例。

输出数据格式：
对于每个测试用例，如果有效的等式严格少于 `k` 个，则输出 `-1`。否则，按 `a + b = c` 的格式输出第 `k` 个等式。

请注意，输出中的空格是重要的。题目大意： 本题要求解形式为 `a + b = c` 的等式，其中 `a` 有 `A` 位数字，`b` 有 `B` 位数字，`c` 有 `C` 位数字。所有数字都是正整数，并且书写时没有前导零。需要找到按字典序排列的第 `k` 个最小的等式，或者确定它不存在。 输入数据格式： 每个测试包含多个测试用例。输入的第一行包含一个整数 `t`（`1 ≤ t ≤ 10^3`），表示测试用例的数量。接下来的每一行代表一个测试用例，包含四个整数 `A`、`B`、`C`、`k`（`1 ≤ A, B, C ≤ 6`，`1 ≤ k ≤ 10^{12}`）。每个输入文件最多有 `5` 个不满足 `A, B, C ≤ 3` 的测试用例。 输出数据格式： 对于每个测试用例，如果有效的等式严格少于 `k` 个，则输出 `-1`。否则，按 `a + b = c` 的格式输出第 `k` 个等式。 请注意，输出中的空格是重要的。