MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 12px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

Problem Statement

Password authentication is used in a lot of facilities. The office of JAG also uses password authentication. A password is required to enter their office. A password is a string of $N$ digits '0'-'9'. This password is changed on a regular basis. Taro, a staff of the security division of JAG, decided to use the following rules to generate a new password from an old one.

1. The new password consists of the same number $N$ of digits to the original one and each digit appears at most once in the new password. It can have a leading zero. (Note that an old password may contain same digits twice or more.)
2. The new password maximizes the difference from the old password within constraints described above. (Definition of the difference between two passwords is described below.)
3. If there are two or more candidates, the one which has the minimum value when it is read as an integer will be selected.

The difference between two passwords is defined by $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.

Taro would like to use a computer to calculate a new password correctly, but he is not good at programming. Therefore, he asked you to write a program. Your task is to write a program that generates a new password from an old password.

Input

The input consists of a single test case. The first line of the input contains a string $S$ which denotes the old password. You can assume that the length of $S$ is no less than $1$ and no greater than $10$. Note that old password $S$ may contain same digits twice or more, and may have leading zeros.

Output

Print the new password in a line.

Sample Input 1

201```

### Output for the Sample Input 1

```plain
701```

* * *

### Sample Input 2

```plain
512```

### Output for the Sample Input 2

```plain
012```

* * *

### Sample Input 3

```plain
99999```

### Output for the Sample Input 3

```plain
49876```

* * *

### Sample Input 4

```plain
765876346```

### Output for the Sample Input 4

```plain
265874931```

* * *