Longest Palindrome Formation

Problem Statement

Given a list of strings, your task is to form the longest palindrome using any combination (and reordering) of characters from these strings. A palindrome is a string that reads the same backwards as forwards, i.e. it satisfies the condition \[ P = P^R \] where \(P^R\) is the reverse of string \(P\).

If there are multiple palindromes of maximum length, you may output any one of them. If no palindrome can be formed, output an empty string. Note that you must use as many characters as possible to form the longest palindrome.

Example:

• For input ["abcba"], a valid output is abcba.
• For input ["abc", "def", "g", "cba", "fed"], one valid output is abcdefgfedcba.

Your solution must be optimized for both time and space complexity.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

1. The first line contains a single integer n representing the number of strings.
2. The following n lines each contain one string.

You should process the input accordingly.

outputFormat

The output, which should be written to standard output (stdout), is a single line containing the longest palindrome that can be formed using any combination of the characters from the input strings.

## sample

1
abcba

abcba