All subsets

For the first ( n ) natural numbers, generate and display all possible ordered subsets.

Input

A single natural number ( n ) (( 1 \leq n \leq 10 )).

Output

Print all ordered subsets of the integers from ( 1 ) to ( n ) in lexicographical order. Each subset should be printed on a new line.

Examples