Unique Permutations Generator

Given a string s, your task is to generate all unique permutations of its characters.

If the input string is empty, output an empty line. Otherwise, generate all unique arrangements of the characters in lexicographical order and print each permutation on a new line.

Note: Duplicates in the input should be handled so that the output contains no duplicate permutations. Mathematically, if n is the length of s and there are repeated characters, the number of unique permutations is given by \(\frac{n!}{\prod_{i} k_i!}\), where \(k_i\) is the frequency of each distinct character.

inputFormat

A single line containing the string s.

outputFormat

Print each unique permutation of s in lexicographical order on a new line. If s is empty, print an empty line.## sample