Permutation (2)

Given a string consisting of M (2 ≤ M ≤ 8) characters (letters and numbers). Withdraw all the permutations of the symbols of this string.

Specifications

Input

In the first line of the file is the source string.

Output

Bring in each line of the file for one permutation. Permutation can be displayed in any order. Repetitions and lines that are not permutations of the original, should not be.

Problem information

Time Limit: 1 seconds
Memory Limit: 64 MB
Balls for the passed test: 16.6667
Complexity: 17% 82/99

Example

Example input

Sample 1
AB

Sample 2
122

Example output

Sample 1
AB
BA

Sample 2
122
212
221

← The prime factors

Problems

Moneybox →