Автомобiльнi номери
Козак Вус та Ледi, їдучи автомобiлем, обожнюють грати в одну гру. Вони дивляться на число, записане на номерi автомобiля, та хочуть зробити, щоб воно дiлилося нацiло на 9 за мiнiмальну кiлькiсть операцiй.
Операцiя — це додати або вiдняти одиницю до будь-якої цифри. Звичайно цифри завжди мають бути вiд 0 до 9. Тобто, не можна вiднiмати вiд 0 та додати до 9.
Друзям ця гра швидко набридла, тому вони вирiшили ускладнити її, доповнивши її ще одним правилом — серед усiх можливих рiшень, потрiбно знайти лексикографiчно мiнiмальний.
В Потоколяндiї автомобiльнi номери досить великi, тому грати в цю гру складно, тому компанiяпросить вас написати програму, яка буде грати за них.
Вхідні дані
Єдиний рядок мiстить цифровий рядок s (1 ≤ |s| ≤ 1 000 000), де |s| — довжина рядка. Звернiть увагу, що рядок може починатись з «0».
Вихідні дані
В єдиному рядку виведiть вiдповiдь на задачу.
####Примiтка
У першому прикладi з 23 можна зробити 00 за 5 операцiй, або 27 за 4 операцiї, що є вигiднiшим.
У другому прикладi з 228 можна зробити 279 за 6 операцiй, або 018 за 3 операцiї, що є вигiднiшим.
У третьому прикладi 0234 одразу нацiло дiлиться на 9, тому i є вiдповiддю.
Рядок a лексикографiчно менший за рядок b, якщо i лише якщо виконується один з двох пунктiв:
• a — префiкс b, але a ≠ b;
• у першiй позицiї, де a та b рiзнi, у рядку a знаходиться буква, яка зустрiчається в алфавiтi ранiше, нiж вiдповiдна буква у b.