Mã Gray

Mã Gray là một danh sách gồm tất cả $2^n$ chuỗi bit có độ dài $n$, trong đó bất kỳ hai chuỗi liên tiếp nào cũng chỉ khác nhau đúng một bit.

Cho số nguyên $n$, hãy in ra một mã Gray hợp lệ.

Dữ liệu vào

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

Dữ liệu ra

In ra $2^n$ dòng, mỗi dòng là một chuỗi bit độ dài $n$ theo thứ tự mã Gray.

Ràng buộc

• $1\le n\le 16$

Ví dụ