The set s of cardinality n is given. It contains all the elements in the range [1 .. n]. Generate all its subsets.

Input

One positive integer n (1 ≤ n ≤ 8).

Output

Print all subsets of a given set. Each subset must be printed in a separate line. A subset is given by the list of its elements in ascending order. Print the subset elements together, without spaces. Each subset must be printed no more than once. Subsets must be listed in ascending order (see example). Do not output the empty subset.