Mô tả bài toán:

Gray code là danh sách tất cả các chuỗi nhị phân dài ~ 2^n ~, trong đó bất kỳ hai chuỗi liên tiếp nào cũng chỉ khác nhau đúng một bit (nghĩa là, khoảng cách Hamming giữa chúng bằng 1).

Nhiệm vụ của bạn là tạo ra mã Gray cho một giá trị ~ n ~ được cho.

Input:

• Dòng đầu tiên chứa một số nguyên ~ n ~.

Output:

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

Ràng buộc:

• ~ 1 \leq n \leq 16 ~

Ví dụ:

Input:

2

Output:

00
01
11
10