问题描述

从 $1\sim n$ 中任选若干个整数（可以为 $0$)，输出所有可能的方案 。

注：因暂时不支持 SPJ，因此你的输出需要遵守以下格式：

将 $1\sim n$ 看做 $[1,2,\dots,n-1,n]$，对应一个 $n$ 位二进制整数，用 $0$ 代表不选，$1$ 代表选，你需要依次输出 $0\sim (2^n-1)$ 的全部方案。

输入格式

输入一个正整数 $n$。$(1\le n\le 15)$。

输出格式

按照题目要求输出 $2^n$ 种方案。

样例输入1

3

样例输出1

3
2
2 3
1
1 3
1 2
1 2 3

样例输入2

4

样例输出2

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