Different arrangements of letters

Problem

A word may have repeated letters. Print every different arrangement of its letters, one per line, in dictionary order.

Example

Input

aab

Output

aab
aba
baa

Three arrangements.

Try the problem first. Open one hint at a time.

Hint 1

Count the letters with a Counter. At each position try every distinct letter that still has a count above zero.

Hint 2

Take one from its count while you explore it, and add it back afterwards.

Write your Python code, run it on the examples and submit it to hidden tests.