3.5 Equality
(RankList for this Question)
Score: 25pts
Time Limit: 5.00 sec
You are given a series of test cases, each consisting of three positive integer values: A, B, and C, representing the number of digits in three positive integers, a, b, and c, respectively. Your task is to find the k-th smallest equality of the 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.

An equality s is considered lexicographically smaller than another equality t if and only if the first position where s and t differ contains a smaller digit in s than in t.
Example:
Lets say we have “2+4=6” and “4+2=6”.
Start by comparing the first number of both expressions. In this case, 2 and 4.
Since 2 is smaller than 4, expression 1 (2 + 4 = 6) is lexicographically smaller than expression 2 (4 + 2 = 6).

Write a program to solve this problem for multiple test cases.

Constraints
1≤A,B,C≤6, 1≤k≤10^12.
Each input file has at most 5 test cases which do not satisfy A,B,C≤3.

Input Format
Each test contains multiple test cases. The first line of input contains a single integer t (1≤t≤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.

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.
note- ouput as a" "+" "b" "=" "c.(spaces matter here)

Example 1
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

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

Explanation:
In the first test case, the first 9 solutions are: ⟨1,1,2⟩,⟨1,2,3⟩,⟨1,3,4⟩,⟨1,4,5⟩,⟨1,5,6⟩,⟨1,6,7⟩,⟨1,7,8⟩,⟨1,8,9⟩,⟨2,1,3⟩
so the ans is 2+1=3
In 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.