Problem G. Gablerd Lettres

Author:A. Usmanov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Arocdnicg to rsceearch at Cmabrigde Uinervtisy, it deosn’t mttaer in waht oredr the ltteers in a wrod are, the olny iprmoatnt tihng is taht the frist and lsat ltteer are in the rghit pcale. The rset can be a toatl mses and you can sitll raed it wouthit pobelrm. Tihs is buseace the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.

Alexey decided to test whether this property will also hold for integers. He picked an integer number N and now wants to rearrange its digits so that:

Additionally for each position except the first and the last one, digits located in this position before and after rearrangement must be different.

You program must rearrange digits of a given integers according to Alexey's requirements.

Input file format

Input file contains a single integer N.

Output file format

Output file must contain a single integer — an answer to the problem. If there are several solutions, output any of them.

If there is no solution, output  − 1.

Constraints

1 ≤ N ≤ 109

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
238965
269385
2
123
-1

0.154s 0.094s 15