Рассмотрим все равенства вида \(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\).
Выходные данные
Для каждого набора входных данных, если подходящих равенств строго меньше \(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\).
Обратите внимание, что пробелы в выводе имеют значение.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
2 + 1 = 3
10 + 90 = 100
-1
9 + 99996 = 100005
-1
78506 + 28543 = 107049
-1
|