A Gray code is a list of all ~2^n~ bit strings of length ~n~, 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 ~n~.

Input

• The only input line has an integer ~n~.

Output

• Print ~2^n~ lines that describe the Gray code. You can print any valid solution.

Constraints

• ~1 \le n \le 16~

Example Input

2

Example Output

00
01
11
10