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.

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

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