{"problem":{"name":"Minimize Even Palindrome","description":{"content":"For a string $s$ consisting of lowercase English letters, let $f(s)$ denote the number of substrings of $s$ that are palindromes of even length. More precisely, $f(s)$ is the number of pairs of intege","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc209_b"},"statements":[{"statement_type":"Markdown","content":"For a string $s$ consisting of lowercase English letters, let $f(s)$ denote the number of substrings of $s$ that are palindromes of even length. More precisely, $f(s)$ is the number of pairs of integers $l, r$ that satisfy all of the following conditions:\n\n*   $1 \\leq l \\leq r \\leq |s|$.\n*   $r - l + 1$ is even.\n*   $s_l s_{l+1} \\cdots s_{r}$ is a palindrome.\n\nGiven a string $S$ consisting of lowercase English letters, output one string $S'$ obtained by rearranging the characters of $S$ such that $f(S')$ is minimized.\nYou are given $T$ test cases. Solve each of them.\n\n## Constraints\n\n*   $1 \\le T \\le 10^5$\n*   $2 \\le |S| \\le 2 \\times 10^5$\n*   $S$ consists of lowercase English letters.\n*   The sum of $|S|$ over all test cases is at most $2 \\times 10^5$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nEach test case is given in the following format:\n\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc209_b","tags":[],"sample_group":[["3\nsee\nxxxxxy\nabracadabra","ese\nxxxyxx\nabracadabra\n\nFor the first test case, the strings $S'$ obtained by rearranging the characters of $S$ are `see`, `ese`, and `ees`. Among these, only `ese` minimizes $f(S')$, so output it.\nFor the second test case, for example, outputting `xxyxxx` will also be considered correct."]],"created_at":"2026-03-03 11:01:14"}}