Một mã Gray là một danh sách gồm tất cả các xâu nhị phân có độ dài n, sao cho hai xâu liên tiếp chỉ khác nhau đúng một bit (nghĩa là khoảng cách Hamming bằng 1).

Nhiệm vụ:

Cho trước một số nguyên ~n~, hãy tạo và in ra một mã Gray có độ dài ~n~.

Đầu vào:

Dòng duy nhất chứa một số nguyên ~n~ — độ dài xâu nhị phân.

Đầu ra:

In ra ~2^𝑛~ dòng, mỗi dòng là một xâu nhị phân độ dài ~n~, thể hiện một mã Gray hợp lệ.

Bạn có thể in ra bất kỳ mã Gray hợp lệ nào.

Ràng buộc:

~1 \le n \le 16~

Ví dụ :

Input:

2

Output:

00
01
11
10