Given a string \(S\), output all of its permutations. It is guaranteed that all characters in \(S\) are unique lowercase letters.

Note: a permutation of a string is a unique rearragement of the string's characters. For instance, the permutations of the string "abc" are: "abc", "acb", "bac", "bca", "cab", and "cba".

Constraints

\(1 \le |S| \le 8\)

Note: \(|S|\) denotes the length of the string \(S\).

Input Specification

The first and only line of input consists of a string \(S\), representing the string to permutate.

Output specification

Output all unique permutations of \(S\) in any order.

Sample Input 1

abc

Sample Output 1

abc
acb
bac
bca
cab
cba