Cho một số nguyên dương N có không quá 16 chữ số, bạn được phép tách các chữ số của N thành các số nhỏ hơn và phải đảm bảo các số tách được đều là số thuận nghịch, bạn cũng ko được phép đảo thứ tự các chữ sổ của N. Hãy in ra mọi cách tách như vậy.

Đầu vào: Dòng duy nhất chứa N

Ràng buộc: 1<=N<=10^16

Đầu ra: In ra các cách tách N thành các số nhỏ thuận nghịch nhỏ hơn

Input:

122212

Output:

1 2 2 2 1 2 
1 2 2 212 
1 2 22 1 2 
1 22 2 1 2 
1 22 212 
1 222 1 2 
12221 2