Cho trước một xâu kí tự. Viết chương trình in ra tất cả các hoán vị của xâu đó (không bao gồm chính nó), theo thứ tự từ điển.

Input Specification

Gồm xâu kí tự trên một dòng duy nhất.

Output Specification

In ra kết quả mỗi hoán vị trên một dòng.

Constraints

• Xâu kí tự chỉ gồm các chữ cái in thường, đôi một khác nhau;
• Xâu kí tự ban đầu có không quá 8 kí tự.

Input Sample

dab

Output Sample

abd
adb
bad
bda
dba