Valid Permutations

Given a string \(s\), generate all valid permutations of \(s\) such that no two adjacent characters are the same. In other words, for any valid permutation \(P\), it must hold that \(P_i \neq P_{i+1}\) for all valid indices \(i\). If no valid permutation exists, the output should be empty.

Print each valid permutation on a new line in lexicographical order.

inputFormat

The input is read from stdin and consists of a single line containing the string \(s\).

outputFormat

Output the valid permutations, each on a separate line, sorted in lexicographical order. If no valid permutation exists, output nothing.

aab

aba