Mã Gray là danh sách gồm tất cả \(2 ^ n\) xâu nhị phân độ dài \(n\), trong đó bất kỳ hai xâu liên tiếp nào khác nhau tại chính xác một vị trí (tức là khoảng cách Hamming của chúng là một).

Nhiệm vụ của bạn là tạo mã Gray cho một độ dài \(n\) được cho.

Input

• Dòng đầu vào duy nhất có một số nguyên \(n\).

Output

• In \(2^n\) dòng mô tả mã Gray. Bạn có thể in bất kì lời giải hợp lệ nào.

Constraints

• \(1 \le n \le 16\)

Example

Sample input

2

Sample output

00
01
11
10