Yêu cầu

Có \(n\) hình vuông bằng nhau được xếp thành các cột có đáy thẳng hàng, sao cho chiều cao các cột không tăng từ trái sang phải. Một cách xếp được biểu diễn bởi dãy \((a_1,\ldots,a_s)\) với \(a_1\ge\cdots\ge a_s>0\) và tổng bằng \(n\).

Hãy liệt kê mọi cách xếp theo thứ tự từ điển giảm: dãy có phần tử khác nhau đầu tiên lớn hơn được in trước.

Dữ liệu vào

Một dòng chứa \(n\).

Dữ liệu ra

Mỗi dòng in một phân hoạch \(a_1,a_2,\ldots,a_s\), các số cách nhau bởi dấu cách.

Ràng buộc

• \(n\le30\).

Ví dụ

7

7
6 1
5 2
5 1 1
4 3
4 2 1
4 1 1 1
3 3 1
3 2 2
3 2 1 1
3 1 1 1 1
2 2 2 1
2 2 1 1 1
2 1 1 1 1 1
1 1 1 1 1 1 1