Задача J. Кнопочный квест ≡

Условие

Тимофей с друзьями разрабатывает компьютерную игру "Свитки древних". Первой загадкой для игрока, очнувшегося в тюремной камере, будет автомат, который блокирует дверь. У автомата есть экран, на котором написано шестизначное число n с ведущими нулями и три кнопки. Нажатие на первую кнопку увеличивает число на 1 (если в результате получается 1000000, то на экране будет отображаться число 0 в виде 000000). Нажатие на вторую кнопку уменьшает число на 1 (если в результате получается -1, то на экране будет отображаться число 999999). Нажатие на третью кнопку упорядочивает цифры на экране в порядке возрастания. Например, если на экране было число 000618, то станет 000168, если было 500002, то станет 000025, если было 777777, то число не изменится. Дверь откроется, если на экране появится число m. При этом требуется наименьшее количество нажатий на кнопки.

Тимофей убеждает друзей, что n и m должны подбираться для каждого игрока случайным образом. Друзья возражают ему, что в этом случае требуемая последовательность нажатий кнопок для некоторых входных данных будет слишком длинной, что в конечном итоге отрицательно скажется на рейтинге игры. Помогите ребятам: составьте программу, которая по начальному числу n определит конечное число m, для которого требуемая последовательность нажатий наиболее длинная.

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

Единственная строка входного файла содержит натуральное число n (без ведущих нулей).

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

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

Ограничения

1 ≤ n ≤ 999999

Пояснение к примерам

В первом примере дано начальное n = 12. Наиболее длинная последовательность нажатий потребуется для достижения числа 949998, чтобы до него добраться потребуется 50006 нажатий на кнопки — больше, чем до любого другого числа.

Во втором примере дано начальное n = 949998. Искомых чисел оказалось сразу два.

Примеры тестов

12

949998
50006

949998

844447 844448
44461

Разбор

Поиск в глубину.