License plates

Cossack Vus and Lady enjoy playing a game while driving. They look at the number on the car's license plate and aim to make it divisible by 9 using the fewest operations possible.

An operation consists of adding or subtracting one from any digit. However, digits must remain between 0 and 9; you cannot subtract from 0 or add to 9.

To make the game more challenging, they added a rule: among all possible solutions, they must find the lexicographically smallest one.

In Potokoland, car license plates are quite large, making this game difficult. Therefore, they need you to write a program to play for them.

Input Format

A single line contains a numeric string s (1 ≤ |s| ≤ 1,000,000), where |s| is the length of the string. Note that the string can start with "0".

Output Format

Output the solution to the problem on a single line.

Examples

Note

In the first example, you can transform 23 into 00 using 5 operations, or into 27 using 4 operations, which is more efficient.

In the second example, you can change 228 to 279 with 6 operations, or to 018 with 3 operations, which is more efficient.

In the third example, 0234 is already divisible by 9, so it is the solution.

String a is lexicographically smaller than string b if one of the following conditions is met:

• a is a prefix of b, but a ≠ b;

• at the first position where a and b differ, the character in a comes earlier in the alphabet than the corresponding character in b.