Liệt kê tập con

Trong một bài kiểm tra về Thuật toán Đệ quy (Recursion), giáo sư yêu cầu bạn sử dụng kỹ thuật Quay lui (Backtracking) để liệt kê tất cả các tập con của một tập hợp \(S\) cho trước.

Tập hợp \(S\) được định nghĩa là \(S = \{1, 2, 3, \ldots, N\}\).

Nhiệm vụ của bạn là viết một chương trình liệt kê tất cả \(2^N\) tập con của tập \(S\) bằng cách mô phỏng quá trình xây dựng tập con theo từng phần tử.

Input

• Dòng đầu tiên và duy nhất chứa số nguyên \(N\) (\(1 \le N \le 15\)) --- kích thước của tập hợp \(S\).

Output

In ra tất cả các tập con của \(S\).

• Mỗi tập con được in trên một dòng riêng biệt.
• Các phần tử trong mỗi tập con được in ra theo thứ tự tăng dần, cách nhau bởi một dấu cách.
• Tập rỗng được biểu thị bằng \t\.

Example

3

{}
3
2
2 3
1
1 3
1 2
1 2 3