cho.sh

Change a Password

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.

Medium5Brute forceSortingMathImplementationNo attempts yetTime limit5sMemory limit512 MB

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 NN 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.

  1. The new password has the same length NN 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.)
  2. Subject to the rule above, the new password maximizes the difference from the old password. The difference is defined below.
  3. 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∣, 10N−∣a−b∣)\min(|a-b|,\ 10^N-|a-b|), where aa and bb 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 SS that denotes the old password. The length of SS is between 1 and 10, and that length is NN. SS 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 NN.