Binary String Ordering

Nikola would not stop asking questions in math class, so his teacher gave the whole class this task.

There are $2^N$ binary strings of length $N$. Print all $2^N$ of them, one per line, each string exactly once, so that the distance between every two neighboring lines is 1.

The distance between two binary strings is the number of positions where the corresponding digits differ. For example:

• distance(111, 000) = 3 (the strings differ in the first, second and third positions)
• distance(111100, 101010) = 3 (the strings differ in the second, fourth and fifth positions)
• distance(110011, 110011) = 0

Many orderings satisfy the condition, so this problem accepts only one of them. Counting lines from 0, line $i$ holds $i \oplus \lfloor i/2 \rfloor$ written as an $N$ digit binary number, where $\oplus$ is bitwise exclusive or and the number is padded on the left with '0'. That ordering is the binary reflected Gray code, and every two neighboring lines differ in exactly one digit.

The first and only line contains $N$, the length of the binary strings. ($1 \le N \le 16$)

Print $2^N$ lines. Line $i$ ($0 \le i < 2^N$) holds the $N$ digit binary representation of $i \oplus \lfloor i/2 \rfloor$. Every line must consist of exactly $N$ digits, each '0' or '1'.

You may assume that at least one solution always exists.