Автомобільні номери#9090

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

1 секунда

64 мегабайти

Легка

Козак Вус та Леді, їдучи автомобілем, обожнюють грати в одну гру. Вони дивляться на число, записане на номері автомобіля, та хочуть зробити, щоб воно ділилося націло на $9$ за мінімальну кількість операцій.

Операція — це додати або відняти одиницю до будь-якої цифри. Звичайно, цифри завжди мають бути від $0$ до $9$ . Тобто не можна віднімати від $0$ та додавати до $9$ .

Друзям ця гра швидко набридла, тому вони вирішили ускладнити її, доповнивши її ще одним правилом — серед усіх можливих рішень потрібно знайти лексикографічно мінімальний.

У Потоколяндії автомобільні номери досить великі, тому грати в цю гру складно, тому вони просять вас написати програму, яка буде грати за них.

Вхідні дані

Єдиний рядок містить цифровий рядок $s$ ( $1 \leq ∣ s ∣ \leq 1000000$ 1 \leq |s| \leq 1\,000\,000), де $∣ s ∣$ — довжина рядка. Зверніть увагу, що рядок може починатись з $0$ .

Вихідні дані

В єдиному рядку виведіть відповідь на задачу.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

У першому прикладі з $23$ можна зробити $00$ за $5$ операцій, або $27$ за $4$ операції, що є вигіднішим.

У другому прикладі з $228$ можна зробити $279$ за $6$ операцій, або $018$ за $3$ операції, що є вигіднішим.

У третьому прикладі $0234$ одразу націло ділиться на $9$ , тому і є відповіддю.

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

• $a$ — префікс $b$ , але $a \neq = b$ a \neq b;

• у першій позиції, де $a$ та $b$ різні, у рядку $a$ знаходиться буква, яка зустрічається в алфавіті раніше, ніж відповідна буква у $b$ .