3.5 Equality

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.

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.

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.

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)

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.

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.