回文重排 (Task 1755)

• 链接: https://cses.fi/problemset/task/1755
• 板块: Introductory Problems
• 时限: 1.00 s ｜ 内存: 512 MB

描述

给定一个字符串，你的任务是重排它的字母，使其变成一个回文串（即正着读和倒着读都一样）。

输入

输入仅一行，包含一个由 A–Z 组成、长度为 $n$ 的字符串。

输出

打印一个由原始字符串的字符组成的回文串。你可以打印任意一个合法解。如果无解，则打印 "NO SOLUTION"。

约束

$1 \le n \le 10^6$

样例

输入：
AAAACACBA
输出：
AACABACAA