Một xâu được gọi là xâu đối xứng nếu nó đọc giống nhau từ trái sang phải và từ phải sang trái. Ví dụ: kazak, oo, r và mikhailrubinchikkihcniburliahkim là xâu đối xứng, nhưng xâu abb và ij thì không.

Bạn được cho xâu ~s~ bao gồm các chữ cái Latinh viết thường. Mỗi lần biến đổi, bạn có thể chọn bất kỳ một vị trí nào trong xâu rồi thay đổi chữ cái ở vị trí đó thành bất kỳ chữ cái Latinh thường nào khác và độ dài của xâu là không đổi. Bạn cũng có thể hoán vị thứ tự của các chữ cái trong xâu một cách tùy ý. Chú ý rằng hoán vị không được tính là một phép biến đổi.

Hãy tính số lần biến đổi tối thiểu để xâu ~s~ trở thành một xâu đối xứng. Nếu sau số lần biến đổi tối thiểu ấy có nhiều xâu ~s~ thỏa mãn, in ra xâu có thứ tự từ điển nhỏ nhất.

Input

Dòng duy nhất chứa xâu ~s~ ~(1 \le |s| \le 2\cdot 10^5)~ gồm các chữ cái Latinh viết thường.

Output

In ra xâu đối xứng có thứ tự từ điển nhỏ nhất có thể nhận được sau số lần biến đổi tối thiểu.

Sample 1

Input

aabc

Output

abba

Sample 2

Input

aabcd

Output

abcba