暂无测试数据。

G. k-th equality

时间限制：1 seconds

空间限制：256 megabytes

原题链接：https://codeforces.com/gym/451807/problem/G

题目描述

考虑所有形式为\(a + b = c\)的等式，其中\(a\)有\(A\)位，\(b\)有\(B\)位，而\(c\)有\(C\)位。所有的数字都是 正整数 ，并且不写前导零。找出写成上述字符串时的第\(k\)小的等式，或者确定它不存在。

例如，满足\(A = 1\)、\(B = 1\)、\(C = 2\)的前三个等式是

\(1 + 9 = 10\),

\(2 + 8 = 10\),

\(2 + 9 = 11\).

当且仅当以下情况成立时，一个等式\(s\)在词典上比一个数字长度相同的等式\(t\)要小：

在\(s\)和\(t\)不同的第一个位置，等式\(s\)的数字比\(t\)中的相应数字小。

输入

每个测试包含多个测试用例。第一行输入包含一个整数\(t\)（\(1 \leq t \leq 10^3\)）--测试案例的数量。测试用例的描述如下。

每个测试案例的第一行包含整数\(A\)、\(B\)、\(C\)、\(k\)（\(1 \leq A, B, C \leq 6\)、\(1 \leq k \leq 10^{12}\)）。

每个输入文件至多有\(5\)个测试案例，这些案例 不会满足 \(A, B, C \leq 3\)。

输出

对于每个测试案例，如果有严格小于\(k\)的有效等式数，则输出\(-1\)。

否则，将第\(k\)小的等式输出为\(a + b = c\)形式的字符串。

样例

输入样例

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

输出样例

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

样例解释

在第一个测试案例中，第一个\(9\)解是：\(\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\).

在第三个测试案例中，由于\(a\)和\(b\)的最小可能值大于\(c\) 的最大可能值 \(——\) \(10 + 10 = 20 > 9\)，所以没有解决方案。

请注意，输出中的空白点是 重要的 。