Sắp xếp thành xâu đối xứng

Nguồn: CSES Problem Set

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một xâu $S$. Hãy sắp xếp lại toàn bộ các ký tự của $S$ sao cho xâu thu được là một xâu đối xứng, tức là xâu đọc từ trái sang phải giống hệt khi đọc từ phải sang trái.

Mỗi ký tự của xâu ban đầu phải được sử dụng đúng số lần nó xuất hiện trong $S$.

Nếu tồn tại nhiều cách sắp xếp thỏa mãn yêu cầu, có thể đưa ra bất kỳ cách nào.

Input

Đầu vào gồm một dòng duy nhất chứa xâu $S$ gồm các ký tự chữ cái in hoa từ A đến Z.

Gọi $n=|S|$ là độ dài của xâu.

Output

Nếu có thể sắp xếp các ký tự của $S$ thành một xâu đối xứng, hãy in ra một xâu đối xứng hợp lệ sử dụng đúng toàn bộ các ký tự của $S$.

Nếu có nhiều đáp án hợp lệ, có thể in ra bất kỳ đáp án nào.

Nếu không tồn tại cách sắp xếp thỏa mãn, in ra:

NO SOLUTION

Subtask

• Subtask 1 — 60%: $1 \le n \le 2\cdot10^5$; $S$ chỉ gồm các ký tự từ A đến Z.
• Subtask 2 — 40%: $1 \le n \le 5\cdot10^6$; $S$ chỉ gồm các ký tự từ A đến Z.

Ví dụ

Input

AAAACACBA

Output

AACABACAA

Giải thích

Xâu ban đầu AAAACACBA có $6$ ký tự A, $2$ ký tự C và $1$ ký tự B.

Xâu được in ra là:

AACABACAA

Xâu này sử dụng đúng $6$ ký tự A, $2$ ký tự C và $1$ ký tự B, nên không làm mất hoặc thêm bất kỳ ký tự nào so với xâu ban đầu.

Đọc AACABACAA từ trái sang phải hoặc từ phải sang trái đều thu được cùng một xâu, vì vậy đây là một đáp án hợp lệ.

Đây chỉ là một trong các cách sắp xếp có thể được chấp nhận.