Unique Permutations

Given a string s, find all unique permutations of the characters in s and print them in lexicographical order. Note that the input string may contain duplicate characters, so your program must avoid printing duplicate permutations. If the input string is empty, print an empty line.

Mathematical Formulation:

Let \(S\) be a string of length \(n\). The goal is to generate the set \(P(S)\) defined as: \[ P(S) = \{ p \mid p \text{ is a permutation of } S \} \] with the constraint that each permutation is unique even if \(S\) has repeating characters.

inputFormat

The input is provided from stdin and consists of a single line containing the string s. The string may be empty.

outputFormat

Output the unique permutations of the input string sorted in lexicographical order. Each permutation should be printed on its own line to stdout. If the input string is empty, output an empty line.

## sample

abc

abc
acb
bac
bca
cab
cba

</p>