ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1406. Next Number

Time limit: 1.0 second
Memory limit: 64 MB
Frank Tarantini is the main weapons specialist in the gang of Vito Maretti. He buys stolen weapons and forges the gun numbers. After that the weapons is given to the other gangsters.
Recently Vito has charged Frank with the assignment to procure 20 new tommy-guns. Frank has fulfilled the assignment the same night. Now he is to change the guns numbers. In order not to arouse suspicion Frank uses as a new gun number the minimal next one with the same sum of digits. It takes 30 minutes to find such number because Frank is a gangster, not mathematician. But today he is short of time. So you are under the threat of one of his new tommy-guns. He wants you to write a program that would find the suitable number.

Input

The only line contains the K-digit number N that is the old number of a tommy-gun (1 ≤ K ≤ 2000; 0 ≤ N ≤ 101000).

Output

Output the new K-digit number that Frank needs or -1 if there is no such number.

Samples

inputoutput
113
122
0050
0104
Problem Author: Alexander Ipatov
Problem Source: The 12th High School Pupils Collegiate Programming Contest of the Sverdlovsk Region (October 15, 2005)