Phủ Đủ Mọi Mẫu Nhị Phân · canuc80k5009

Một mẫu nhị phân độ dài $n$ là một xâu gồm đúng $n$ ký tự, mỗi ký tự là $0$ hoặc $1$ .

Hãy tạo một xâu nhị phân ngắn nhất sao cho mọi mẫu nhị phân độ dài $n$ đều xuất hiện ít nhất một lần dưới dạng một đoạn liên tiếp. Có thể in bất kỳ xâu ngắn nhất nào thỏa mãn.

Input

Input chỉ chứa một số nguyên $n$ .

Output

In một xâu chỉ gồm $0$ và $1$ . Xâu phải có đúng $2^{n} + n - 1$ ký tự và chứa đủ $2^{n}$ mẫu nhị phân độ dài $n$ .

Constraints

$1 \leq n \leq 15$ .
Output chỉ gồm các ký tự $0$ và $1$ , không kể khoảng trắng cuối.
Độ dài bắt buộc là $2^{n} + n - 1$ ; mỗi trong $2^{n}$ mẫu $n$ bit phải xuất hiện ít nhất một lần.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 5$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

0001011100

Giải thích: Xâu có độ dài $10 = 2^{3} + 3 - 1$ . Tám cửa sổ độ dài $3$ lần lượt phủ đủ các mẫu từ $000$ đến $111$ .

Mô hình: Mỗi trạng thái gồm n-1 bit là một đỉnh. Một mẫu n bit là một cung từ tiền tố n-1 bit sang hậu tố n-1 bit, được gắn nhãn bởi bit cuối.
Thuật toán: Dựng đồ thị de Bruijn: mỗi đỉnh là trạng thái n-1 bit, mỗi cung thêm bit 0 hoặc 1. Chạy Hierholzer từ trạng thái 0 rồi ghép n-1 số 0 với nhãn cung.
Chứng minh đúng: Mỗi trong 2^n cung đại diện duy nhất cho một mẫu n bit. Chu trình Euler đi qua mỗi cung đúng một lần nên các cửa sổ của xâu phủ đủ mẫu. Mọi xâu dài L chỉ có L-n+1 cửa sổ, nên cần L≥2^n+n-1; cách dựng đạt đúng cận này.
Độ phức tạp: Thời gian: O(2^n). Bộ nhớ nằm trong cùng bậc với cấu trúc đồ thị hoặc số trạng thái được lưu.
Lỗi thường gặp: chỉ in chuỗi tuần hoàn dài 2^n mà quên nối n-1 ký tự đầu.
Lỗi thường gặp: nối tất cả 2^n xâu n bit nên output không ngắn nhất.
Lỗi thường gặp: dùng sai số bit của trạng thái và bỏ sót mẫu.