k-th equality
Contest: Codeforces Round 880 (Div. 1)
Difficulty rating: 1700
Tags: brute force, implementation, math

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
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

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

Editorial:
The largest possible value for $$$a$$$ is $$$10^6 - 1$$$, so we can iterate over each possibility. When we fix $$$a$$$, we can find the range of values for $$$b$$$ such that $$$10^{C - 1} \leq a + b < 10^C$$$, and $$$10^{B - 1} \leq b < 10^B$$$. For each such value, we have a correct equality.
We can easily find this range. We get that $$$\max \{ 10^{C - 1} - a, 10^{B - 1} \} \leq b < \min \{ 10^C - a, 10^B \}$$$ and from this inequality, we know how many equations for the given $$$a$$$ we have. As we start by minimizing $$$a$$$, we can find its value for the $$$k$$$-th equation if we iterate from the smallest possible values of $$$a$$$.
When we have fixed $$$a$$$ (or find out that there is no such equation), we iterate over all possible values of $$$b$$$ and check if the resulting $$$c$$$ has $$$C$$$ digits. The complexity is $$$\mathcal{O}(10^A + 10^B)$$$.