A. k-е равенство
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим все равенства вида $$$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$$$.

Обратите внимание, что пробелы в выводе имеют значение.