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 tommyguns. 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 tommyguns. He wants you to write a program that would find the suitable number.
Input
consists of the kdigit number N – the old number of a tommygun (1 <= K <= 2000, 0 <= N <= 10^{1000}).
Output
the new Kdigit number that Frank needs or 1 if there is no such number.
Samples
input  output 

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)