Lexicographic Enumeration of Bit Strings

Problem Description

Given an integer $n$, you need to output, in a certain order, all $n$-bit strings made of characters 0 and 1.

The $k$-th line contains all strings with exactly $k-1$ ones. The strings on each line are sorted in lexicographic order and separated by a single space. See the sample for details.

Input Format

One line with an integer $n$.

Output Format

Output $n$ lines, each containing several strings separated by spaces.

Sample Input

3

Sample Output

000
001 010 100
011 101 110
111

Constraints

For all data: $2 \leq n \leq 18$.