考虑 $$$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$$$ 形式的字符串。
示例
输入 #1
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
输出 #1
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$$$。
请注意输出中的空格很重要。