Table of Contents

Prelude 1 to Backtracking -- Subsets

For this prelude, you are to use your skeleton file for doing backtracking and compute the subsets of N.

Input

Input consists of a sequence of non-negative integers, N (0 < N < 10), one per line.

Output

For each input value, N, generate the subsets of the numbers 1..N. Each subset should be on a line by itself, surrounded by { }, in the order shown below (which is the “natural” order when following the strategy outlined in class). A single blank line should separate each test case.

Sample Input

3
4

Sample Output

{ 1 2 3 }
{ 1 2 }
{ 1 3 }
{ 1 }
{ 2 3 }
{ 2 }
{ 3 }
{ }

{ 1 2 3 4 }
{ 1 2 3 }
{ 1 2 4 }
{ 1 2 }
{ 1 3 4 }
{ 1 3 }
{ 1 4 }
{ 1 }
{ 2 3 4 }
{ 2 3 }
{ 2 4 }
{ 2 }
{ 3 4 }
{ 3 }
{ 4 }
{ }