许多设施都使用密码验证。JAG 办公室也使用密码验证，进入办公室需要密码。密码是一个由 $N$ 个数字 '0'-'9' 组成的字符串。

该密码会定期更换。JAG 安全部门的员工 Taro 决定使用以下规则从旧密码生成新密码：

1. 新密码的长度与原密码相同，均为 $N$，且新密码中的每个数字最多出现一次。新密码可以包含前导零。（注意：旧密码可能包含重复的数字。）
2. 在满足上述约束的前提下，新密码应最大化与旧密码的差异。（两个密码之间的差异定义如下。）
3. 如果存在两个或多个候选密码，则选择作为整数读取时数值最小的那一个。

两个密码之间的差异定义为 $\min(|a - b|, 10^N - |a - b|)$，其中 $a$ 和 $b$ 是两个密码所表示的整数。例如，“11”和“42”之间的差异是 31，“987”和“012”之间的差异是 25。

Taro 想用计算机正确计算出新密码，但他不擅长编程。因此，他请求你编写一个程序。你的任务是编写一个程序，根据旧密码生成新密码。

输入格式

输入包含单个测试用例。输入的第一行包含一个字符串 $S$，表示旧密码。你可以假设 $S$ 的长度不小于 1 且不大于 10。注意，旧密码 $S$ 可能包含重复的数字，也可能包含前导零。

输出格式

在一行中输出新密码。

样例

样例输入 1

201

样例输出 1

701

样例输入 2

512

样例输出 2

012

样例输入 3

99999

样例输出 3

49876

样例输入 4

765876346

样例输出 4

265874931