Unique Permutations

Given a string s, generate all unique permutations of its characters without using any built-in functions that directly compute permutations. Note that the expected time complexity is at most \(O(n \times n!)\), where \(n\) is the length of the string.

The output should list all the unique permutations in lexicographical order, with each permutation printed on a new line.

inputFormat

The input consists of a single line containing the string s.

outputFormat

Output all unique permutations of s in lexicographical order, each on a separate line.

abc

abc
acb
bac
bca
cab
cba