Description

给出一个小写字母字符串，字符串不超过 200 位，按字典序输出这个字符串的所有全排列。

Format

Input

一串字符串

Output

按字典序，输出该字符串的全排列

Samples

bbdj

bbdj
bbjd
bdbj
bdjb
bjbd
bjdb
dbbj
dbjb
djbb
jbbd
jbdb
jdbb

Limitation

1s, 1024KiB for each test case.