Unique Permutations Generator

You are given a string s. Your task is to generate all unique permutations of the characters in the string.

If the string contains duplicate characters, the output should only contain distinct permutations. All permutations must be printed in lexicographical (dictionary) order.

Note: When s is an empty string, output a single empty line.

For example:

• Input: ABC
  Output:
  ABC
  ACB
  BAC
  BCA
  CAB
  CBA
• Input: AAB
  Output:
  AAB
  ABA
  BAA

inputFormat

Input consists of a single line containing the string s.

outputFormat

Output all unique permutations of the string on separate lines, in lexicographical order.## sample

ABC

ABC
ACB
BAC
BCA
CAB
CBA