Lexicographical Permutations

Given a string s, your task is to generate all unique permutations of s in lexicographical order. A permutation is a rearrangement of the characters. For example, for s = "abc", the unique permutations in order are:

You need to read the input from standard input and output the results to standard output, printing each permutation on a new line.

inputFormat

The input consists of a single line containing the string s. The string s will consist of lowercase English letters. For example:

abc

outputFormat

Output all unique permutations of s in lexicographical order. Each permutation should be printed on a separate line. For example, for the input above, the output should be:

abc acb bac bca cab cba## sample

a

a