Cho một số nguyên dương \(n\). Hãy in ra các cách phân tích \(n\) thành tổng của các số nguyên dương.

Cụ thể, phân tích \(n\) thành \(a_1 + a_2 + \dots + a_k\) sao cho:

• \(a_i > 0\) với mọi \(1 \le i \le k\).
• \(a_1 \ge a_2 \ge \dots \ge a_k\).

Input

• Một số nguyên dương \(n\).

Output

• Tất cả các cách phân tích \(n\) thỏa mãn yêu cầu đề bài, mỗi cách trên một dòng.

Giới hạn

• \(1 \le n \le 12\).

Example

3

3
2 + 1
1 + 1 + 1