비밀번호 변경

많은 시설이 비밀번호 인증을 쓴다. JAG 사무실도 마찬가지여서, 사무실에 들어가려면 비밀번호를 입력해야 한다. 비밀번호는 '0'부터 '9'까지의 숫자 $N$개로 이루어진 문자열이고 주기적으로 바뀐다. 보안팀 직원 Taro는 다음 규칙으로 옛 비밀번호에서 새 비밀번호를 만들기로 했다.

1. 새 비밀번호는 옛 비밀번호와 길이가 같은 $N$이고, 각 숫자는 많아야 한 번만 나온다. 맨 앞이 0이어도 된다. (옛 비밀번호에는 같은 숫자가 두 번 이상 나올 수 있다.)
2. 위 조건을 지키면서 옛 비밀번호와의 차이를 최대로 한다. 차이의 정의는 아래에 있다.
3. 후보가 둘 이상이면 정수로 읽었을 때 값이 가장 작은 것을 고른다.

두 비밀번호의 차이는 $\min(|a-b|,\ 10^N-|a-b|)$로 정의한다. $a$와 $b$는 두 비밀번호가 나타내는 정수다. 예를 들어 "11"과 "42"의 차이는 31이고, "987"과 "012"의 차이는 25다.

옛 비밀번호가 주어지면 새 비밀번호를 구하는 프로그램을 작성하시오.

첫째 줄에 옛 비밀번호를 나타내는 문자열 $S$가 주어진다. $S$의 길이는 1 이상 10 이하이고, 이 길이가 $N$이다. $S$에는 같은 숫자가 두 번 이상 나올 수 있고, 맨 앞이 0일 수 있다.

새 비밀번호를 한 줄에 출력한다. 길이가 $N$이 되도록 맨 앞의 0도 그대로 출력한다.