CF1835A k-th equality

考虑所有形如 $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$。

在第一个测试用例中，前 $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$。 请注意，输出中的空格也很重要。 由 ChatGPT 4.1 翻译