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

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

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