### Problem Statement

A String p is called anti-palindrome if p[i] doesn't equal to p[n - i - 1] for each 0 <= i < (n-1)/2, where n is the length of p. It means that each character (except the middle in the case of a string of odd length) must be different from its symmetric character. For example, "c", "cpp", "java" are anti-palindrome, but "test", "pp" and "weather" are not.

You are given a String s. Rearrange its letters in such a way that the resulting string is anti-palindrome. If there are several solutions, return the one that comes earliest alphabetically. If it is impossible to do it, return the empty string.

### Definition

 Class: AntiPalindrome Method: rearrange Parameters: String Returns: String Method signature: String rearrange(String s) (be sure your method is public)

### Constraints

-s will contain between 1 and 50 characters, inclusive.
-s will contain only lowercase letters ('a'-'z').

### Examples

0)

 `"test"`
`Returns: "estt"`
1)

 `"aabbcc"`
`Returns: "aabcbc"`
2)

 `"reflectionnoitcelfer"`
`Returns: "cceeeeffiillnnoorrtt"`
3)

 `"hello"`
`Returns: "ehllo"`
4)

 `"www"`
`Returns: ""`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7671

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10742&pm=7671

Mike Mirzayanov

#### Testers:

PabloGilberto , brett1479 , legakis , Olexiy

#### Problem categories:

Simple Math, Simple Search, Iteration, String Manipulation