Processing math: 100%

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

1N109

Sample tests

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

0.028s 0.005s 13