403533: GYM101191 F A trick

Memory Limit:0 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. A tricktime limit per test1 secondmemory limit per test64 MBinputstandard inputoutputstandard output

«Sad clown», the new season at the circus, decided to entertain the audience with a mathematical trick. Magician George is the most experienced employee of the circus. So he was given the honor to show this trick.

A person chosen at random from the audience by George is asked to call a random number N. After that the magician thinks for exactly 5,674 seconds and says some number M different from N. The feature of the trick is that these two numbers have the same sum of digits.

How does George manage to do this?

Input

There is one non-negative integer N called by spectator(0 ≤ N ≤ 109). It is guaranteed that a record of the number N doesn't contain leading zeros.

Output

The only line with a non-negative integer M (the number, called by a magician). If there are a lot of suitable numbers, you can print any of them.

The number M can not contain leading zeros and at the same time should not exceed 109.

If the magician can not call the number, you should print -1.

ExamplesInput
24
Output
42

加入题单

上一题 下一题 算法标签: