All Palindromic Permutations

medium

1. You are given a string of length n.
2. You have to print all the palindromic permutations of the given string.
3. If no palindromic permutation exists for the given string, print "-1".

Note -&gt; Check out the question video and write the recursive code as it is intended without 
               changing signature. The judge can't force you but intends you to teach a concept.

Input Format

A String of length n

Output Format

Check the sample ouput and question video.

Constraints

1 &lt;= length of string &lt;= 15

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

aaabb

Output

ababa
baaab

K-partitions

All Palindromic Partitions