Автомобильные номера

Казак Вус и Леди, путешествуя на автомобиле, любят играть в игру с номерами машин. Они смотрят на число на номере и стремятся сделать его кратным 9 с минимальным количеством операций.

Операция заключается в увеличении или уменьшении любой цифры на единицу. Цифры должны оставаться в диапазоне от 0 до 9, то есть нельзя уменьшать 0 или увеличивать 9.

Игра быстро наскучила друзьям, поэтому они решили добавить новое правило: среди всех возможных решений нужно выбрать лексикографически минимальное.

В Потоколяндии номера автомобилей очень длинные, что усложняет игру, поэтому они просят вас написать программу, которая будет играть за них.

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

Входные данные состоят из одной строки, содержащей цифровую строку s (1 ≤ |s| ≤ 1 000 000), где |s| — это длина строки. Обратите внимание, что строка может начинаться с «0».

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

Выведите в единственной строке ответ на задачу.

Примеры

Примечание

В первом примере из 23 можно получить 00 за 5 операций или 27 за 4 операции, что более выгодно.

Во втором примере из 228 можно получить 279 за 6 операций или 018 за 3 операции, что более выгодно.

В третьем примере 0234 уже делится на 9, поэтому это и есть ответ.

Строка a лексикографически меньше строки b, если выполняется одно из двух условий:

• a — это префикс b, но a ≠ b;

• в первой позиции, где a и b различаются, в строке a находится символ, который встречается в алфавите раньше, чем соответствующий символ в b.