Longest Palindromic Rearrangement

Samuel is fascinated by palindromes – strings that read the same backward as forward. Given a string s of length n consisting of lowercase English letters, your task is to create the longest possible palindrome using a subset of the characters in s. You do not have to use all characters, but you must form a palindrome. If there are multiple valid answers, output any one of them.

The problem can be formulated as follows:

Given an integer \( n \) and a string \( s \) of length \( n \), construct a string \( p \) such that:

• The string \( p \) is a palindrome, i.e. \( p = p^R \) where \( p^R \) is the reverse of \( p \).
• The length of \( p \) is maximized under the condition that each character in \( p \) comes from \( s \) and no character is used more times than it appears in \( s \).

One approach is to use a greedy strategy: count the frequency of each character and then use as many pairs as possible. If some character appears an odd number of times, you may choose exactly one occurrence of one such character as the middle of the palindrome.

inputFormat

The input is read from standard input and has the following format:

The first line contains an integer \( n \) representing the length of the string.
The second line contains the string \( s \) consisting of \( n \) lowercase English letters.

outputFormat

Output the longest palindrome that can be constructed using some or all of the characters from \( s \). The output is written to standard output.

## sample

1
a

a

</p>