Gray Code

A Gray code is a list of all $2^{n}2^n$ bit strings of length $nn$, where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one).

Your task is to create a Gray code for a given length $nn$.

Input

The only input line has an integer $nn$.

Output

Print $2^{n}2^n$ lines that describe the Gray code. You can print any valid solution.