Cho số nguyên dương ~N~ (~N <= ~ ~10^9~). Hãy tìm tất cả các hoán vị của các chữ số của ~N~. Lưu ý, chữ số 0 đứng đầu không có nghĩa.

Dữ liệu vào: chỉ ghi số nguyên ~N~.

Kết quả: ghi các hoán vị của các chữ số của ~N~ theo thứ tự tăng dần. Mỗi hoán vị được ghi trên một dòng.

Ví dụ

INPUT

1223

OUTPUT

1223
1232
1322
2123
2132
2213
2231
2312
2321
3122
3212
3221