You are given a string as an input.Rearrange the characters

of the string such that no character appears in its original position.

If the rearrangement is possible, print the rearranged string

else print 'Not possible'.

Input

The Input consist of string

Output

Output any possible rearrangement of the string.

If not possible print 'Not possible'.

Example

Input:
aabccbadd

Output:
dcaabcdab