Chuỗi Grove

Một chuỗi được gọi là chuỗi Grove nếu nó có độ dài lẻ, chỉ gồm các chữ cái thường, và có "giá trị lệch" \(X\) nhỏ nhất có thể trong số các cách sắp xếp lại các ký tự của nó. Giá trị lệch \(X\) của một xâu \(s\) độ dài \(n\) (lẻ) được tính như sau: gọi \(c = \frac{n+1}{2}\) là vị trí chính giữa xâu; mỗi ký tự \(s_i\) đóng góp \(|i - c| \times \text{ascii}(s_i)\), và \(X\) là tổng các đóng góp đó.

Ví dụ với xâu aaa: \(X = 1 \cdot 97 + 0 \cdot 97 + 1 \cdot 97 = 194\).

Cho một xâu \(S\) độ dài lẻ chỉ gồm chữ cái thường. Hãy sắp xếp lại các ký tự của \(S\) (giữ nguyên số lượng mỗi chữ cái) để thu được xâu có \(X\) nhỏ nhất. Nếu có nhiều xâu cùng đạt \(X\) nhỏ nhất, hãy in xâu có thứ tự từ điển nhỏ nhất.

Input

Một dòng duy nhất chứa xâu \(S\).

Output

In ra một dòng là xâu kết quả.

Constraints

• \(S\) chỉ gồm các chữ cái thường a-z, độ dài lẻ.
• \(1 \le |S| \le 10^6\)

Sample Input 1

mdkbz

Sample Output 1

bkzmd

Explanation

Ký tự càng ở xa trung tâm càng "đắt", nên các ký tự có mã ASCII lớn được đặt gần tâm. Ký tự lớn nhất z nằm ở chính giữa, hai ký tự lớn kế tiếp k, m ở khoảng cách \(1\), hai ký tự nhỏ nhất b, d ở khoảng cách \(2\). Trong mỗi cặp cùng khoảng cách, ký tự nhỏ hơn đặt bên trái để xâu nhỏ nhất theo thứ tự từ điển. Khi đó \(X = 2 \cdot 98 + 1 \cdot 107 + 0 + 1 \cdot 109 + 2 \cdot 100 = 612\).