Mã Gray (Gray Code)

Nguồn: CSES Problem Set

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một mã Gray độ dài $n$ là một danh sách gồm tất cả $2^n$ xâu nhị phân có độ dài $n$, sao cho hai xâu liên tiếp trong danh sách khác nhau tại đúng một vị trí bit. Nói cách khác, khoảng cách Hamming giữa hai xâu liên tiếp luôn bằng $1$.

Nhiệm vụ của bạn là xây dựng một mã Gray cho độ dài $n$ đã cho.

Input

Dòng duy nhất chứa một số nguyên $n$.

Output

In ra $2^n$ dòng mô tả một mã Gray hợp lệ.

Mỗi dòng phải chứa một xâu nhị phân có đúng $n$ ký tự.

Có thể in ra bất kỳ mã Gray hợp lệ nào thỏa mãn các yêu cầu trên.

Subtask

• Subtask 1 — 100%: $1 \le n \le 19$.

Ví dụ

Input

2

Output

00
01
11
10

Giải thích

Với $n=2$, có tất cả $2^2=4$ xâu nhị phân độ dài $2$.

Bốn xâu được in ra là 00, 01, 11 và 10, mỗi xâu xuất hiện đúng một lần.

Xét các cặp liên tiếp:

• 00 và 01 khác nhau ở bit thứ hai;
• 01 và 11 khác nhau ở bit thứ nhất;
• 11 và 10 khác nhau ở bit thứ hai.

Do đó, mỗi cặp xâu liên tiếp khác nhau tại đúng một vị trí, nên danh sách trên là một mã Gray hợp lệ.

Đây chỉ là một trong nhiều kết quả có thể được chấp nhận.