From 1 to n, randomly select any number of integers from these n integers, and output all possible selection schemes.

Input Format
Enter an integer n.

Output Format
Each line outputs one scheme.

The numbers in the same line must be arranged in ascending order, and adjacent numbers are separated by exactly one space.

Different schemes are sorted in ascending order according to the lexicographical order.

For the scheme where no number is selected, output an empty line.

Data Range
1 ≤ n ≤ 15

Input Example:

3

Output Example:

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