Dãy De Bruijn

Xây dựng một xâu nhị phân có độ dài ngắn nhất chứa tất cả các xâu nhị phân độ dài $n$ làm xâu con. Xâu nhị phân chỉ gồm các ký tự 0 và 1.

Ví dụ với $n=2$, xâu "00110" chứa các xâu con: 00, 01, 11, 10 — tất cả 4 xâu nhị phân độ dài 2.

Dữ liệu vào

Một số nguyên $n$.

Dữ liệu ra

In một xâu nhị phân hợp lệ có độ dài ngắn nhất.

Ràng buộc

• $1\le n\le 15$

Ví dụ