String Permutations

Given a string s, your task is to generate all possible permutations of the characters in s.

If all characters are distinct, there will be \(n!\) permutations where \(n\) is the length of the string. When duplicate characters exist, duplicate permutations may appear. The order of the output permutations should match the natural recursion order.

Note: For an empty string, output nothing.

inputFormat

The input contains a single line with the string s.

\(\textbf{Constraints:} \) The string can consist of any characters and may be empty.

outputFormat

Output each permutation of the string on a separate line. If the input is an empty string, do not print any output.

The permutations should be generated using recursion in a natural order.

## sample

a

a

</p>