Palindromic Permutations

Given a string \(S\), determine all unique palindromic permutations that can be formed by rearranging its letters. A string is a palindrome if it reads the same forward and backward. Note that a necessary and sufficient condition for a palindromic permutation to exist is that at most one character has an odd frequency, i.e. \(\text{odd_count} \le 1\).

If one or more palindromic permutations exist, output all of them in lexicographical order (each on a new line). If no palindromic permutation exists, output None.

inputFormat

A single line containing the string (S).

outputFormat

If palindromic permutations exist, output all unique palindromic permutations in lexicographical order, one per line. If none exist, output a single line with the word None.## sample

aabb

abba
baab