Change a Password

Time limit5sMemory limit512 MB

Summary

Given an old N-digit password, find the length-N permutation of distinct digits that maximizes the cyclic distance from the old value, breaking ties by smallest number.

Level: Medium5 of 10
Topics: Brute force, Sorting, Math, Implementation
Solved: No attempts yet

Problem

Many facilities use password authentication, and the JAG office is one of them. You need a password to enter the office. A password is a string of $N$ digits from '0' to '9', and it is changed on a regular basis. Taro, a staff member of the JAG security division, decided to build a new password from the old one with the following rules.

The new password has the same length $N$ as the old one, and each digit appears at most once in it. It can have a leading zero. (The old password may contain the same digit twice or more.)
Subject to the rule above, the new password maximizes the difference from the old password. The difference is defined below.
If two or more candidates remain, the one with the smallest value when read as an integer is selected.

The difference between two passwords is $\min(|a-b|,\ 10^N-|a-b|)$ , where $a$ and $b$ are the integers represented by the two passwords. For example, the difference between "11" and "42" is 31, and the difference between "987" and "012" is 25.

Given the old password, write a program that computes the new password.

Input

The first line contains the string $S$ that denotes the old password. The length of $S$ is between 1 and 10, and that length is $N$ . $S$ may contain the same digit twice or more, and it may have leading zeros.

Output

Print the new password on one line. Keep leading zeros so that the printed string has length $N$ .

Examples4

Example 1
Input
```
201
```
Expected output
```
701
```
Example 2
Input
```
512
```
Expected output
```
012
```
Example 3
Input
```
99999
```
Expected output
```
49876
```
Example 4
Input
```
765876346
```
Expected output
```
265874931
```