Subsets

Imagine you are a teacher with N problems, and you need to organize a contest using these problems. To determine the best combination, you decide to list all possible subsets of problems. Remember, the contest must include at least one problem.

Input

You are given a single integer N (1 ≤ N ≤ 10).

Output

Output all possible subsets of the set {1, 2, ..., N}. Each line should represent one subset. Start with the number of problems in the subset, followed by the problem numbers included in that subset.

Examples