题目描述

一个大小为 n 的集合包含的元素为 0, 1, 2, ……, n-1.

请你按字典序输出该集合的所有子集，每个子集占一行，同一个子集内的元素按从小到大排列，两个元素之间以单个空格隔开。

对子集字典序的解释：将一个子集内的元素按从小到大排列后形成一个字符串，每个字符串代表一个子集。对两个字符串来说，从左到右碰到的第一个不同字符的 ASCII 码较小的，其对应的字符串字典序较小。

输入

一个整数 n（0 < n < 10）

输出

字典序输出全部子集。注：输出的第一行一定为空集，即第一行为空行。

样例输入

3

样例输出

0
0 1
0 1 2
0 2
1
1 2
2