Mô tả bài toán:

Bạn được cung cấp một chuỗi ký tự, nhiệm vụ của bạn là sắp xếp lại các ký tự của chuỗi đó sao cho nó trở thành một chuỗi palindrome (tức là chuỗi đọc xuôi và ngược đều giống nhau).

Input:

• Dòng duy nhất chứa một chuỗi ký tự có độ dài ~ n ~, chỉ bao gồm các chữ cái từ ~ A ~ đến ~ Z ~.

Output:

• In ra một chuỗi palindrome được tạo từ các ký tự trong chuỗi ban đầu. Nếu có nhiều cách, bạn chỉ cần in ra một cách hợp lệ.
• Nếu không thể tạo được palindrome, in ra "NO SOLUTION".

Ràng buộc:

• ~ 1 \leq n \leq 10^6 ~

Ví dụ:

Input:

AAAACACBA

Output:

AACABACAA

Giải thích:

• Đếm ký tự:
  • ~ A: 5 ~, ~ C: 2 ~, ~ B: 1 ~.
  • ~ B ~ xuất hiện lẻ → Đặt vào giữa.
• Chuỗi nửa đầu: ~ AAC ~.
• Kết quả: ~ AACABACAA ~.