132. Добавить минусы

Не решаласьСложная

В десятичную запись числа n n нужно добавить несколько знаков минус (возможно ноль), чтобы в получившемся выражении все числа были различны. При этом количество чисел, на которые будет разбита запись числа n n , должно быть наибольшим.

Напомним, что использовать числа с незначащими нулями не разрешается.

Формат ввода

В единственной строке входных данных задано число n n ( 0 ≤ n 0 \le n < 1 0 19 10^{19} ).

Формат вывода

Выведите разбиение числа n n на части. Между частями поставьте знак '-'. Если есть несколько возможных разбиений с наибольшим число различных элементов, выведите любое.

Ограничения

Ограничение времени
2 с
Ограничение памяти
64 МБ

Примеры

Пример 1

Ввод
0
Вывод
0

Пример 2

Ввод
101
Вывод
10-1

Пример 3

Ввод
102
Вывод
1-0-2

Пример 4

Ввод
11
Вывод
11

Пример 5

Ввод
111
Вывод
1-11

Пример 6

Ввод
1000000
Вывод
100000-0

Теги

18.1.8
Нужно войти, чтобы отправить решение.Войти