An muốn biểu diễn số nguyên dương \(n\) thành tổng của các số nguyên dương (không kể thứ tự, các số được sắp xếp không tăng).

Ví dụ với \(n=4\):

4
3 1
2 2
2 1 1
1 1 1 1

Hãy dùng quay lui để liệt kê tất cả cách phân hoạch.

Input

Một dòng duy nhất chứa số nguyên \(n\) (\(1 \le n \le 30\)).

Output

In ra tất cả cách phân hoạch của \(n\), mỗi cách trên một dòng, các số cách nhau bởi khoảng trắng và sắp xếp không tăng.

Example

4

Output:

4
3 1
2 2
2 1 1
1 1 1 1

Ràng buộc & Subtasks