Subsets generation

Input

One positive integer n~(1 \le n \le 8).

Output

Each subset of the set \{1, ..., n\} should be printed on a separate line. The subset should be printed as a list of its elements in ascending order. The elements of the subset must be written without spaces, i.e., as a concatenated string. Each subset should appear no more than once. The subsets should be listed in ascending order. The empty subset should not be printed.

Examples