Mã Gray theo phép phản chiếu

Bối cảnh và bài toán

Một bộ mã hóa cần sinh dãy nhị phân sao cho hai mã liên tiếp chỉ khác đúng một bit. Hệ thống sử dụng quy tắc phản chiếu chuẩn: từ danh sách của n-1 bit, ghép 0 vào trước theo thứ tự cũ, sau đó ghép 1 vào trước theo thứ tự đảo ngược.

Yêu cầu

Sinh toàn bộ dãy mã Gray n bit theo đúng quy tắc phản chiếu trên.

Input

• Một dòng chứa n.

Output

In 2^n dòng, mỗi dòng là một mã nhị phân n bit theo thứ tự chuẩn.

Ràng buộc

• 1 <= n <= 16

Chấm điểm

Ví dụ 1

Input

2

Output

00
01
11
10

Giải thích. Từ [0,1] của 1 bit, ghép 0 phía trước theo chiều xuôi và 1 phía trước theo chiều ngược.

Ví dụ 2

Input

1

Output

0
1

Giải thích. Đây là trường hợp cơ sở của quy tắc phản chiếu.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Gray Code (Task 2205).

Tham khảo: https://cses.fi/problemset/task/2205/