Nhóm “Lyuboyn” — cậu bé Askhat, cậu bé Sanzhar và cậu bé Nurbakyt — đã quyết định mở rộng kiến thức và nghiên cứu một chút về điện tử. Họ đã nghĩ ra một loại công tắc cơ điện kỳ lạ có khả năng sửa đổi tín hiệu tương tự mà nó nhận được theo một cách đặc biệt. Hài lòng với phát minh của mình, họ tự hào đặt tên nó là “Công tắc Lyuboyn”.

Cụ thể, một tín hiệu có thể được biểu diễn dưới dạng một chuỗi gồm $N$ bit, và “Công tắc Lyuboyn” hoạt động sao cho tín hiệu đầu ra mà nó tạo ra khác với đầu vào đúng $K$ bit và không có hai tín hiệu đầu vào nào tạo ra cùng một tín hiệu đầu ra. Để làm cho phát minh của mình trở nên tuyệt vời hơn nữa, các cậu bé đã thêm vào tính năng cuối cùng: nếu tham số nhị phân $T$ được đặt bằng 1, chuỗi các đầu ra liên kết sẽ được lặp lại, nghĩa là nếu bạn bắt đầu với một tín hiệu, thay thế nó bằng đầu ra từ công tắc và lặp lại quy trình đủ số lần, tại một thời điểm nào đó bạn sẽ quay lại tín hiệu ban đầu. Tuy nhiên, điều này sẽ không đúng nếu tham số $T$ được đặt bằng 0.

Trong bài toán này, bạn được yêu cầu lặp lại thành tựu của nhóm và tạo ra “Mã Lyuboyn” — ánh xạ của các tín hiệu đầu ra với các tín hiệu đầu vào cho trước mà công tắc tạo ra. Để đơn giản hóa, bạn chỉ cần xuất ra chuỗi các đầu ra liên kết như đã mô tả ở trên, bắt đầu với tín hiệu $S$.

Về mặt hình thức, bạn cần tìm một chuỗi $f$ có độ dài $2^N$ bao gồm các số nhị phân có độ dài $N$ (bao gồm cả các số 0 ở đầu), sao cho:

1. $f_0 = S$
2. Với mọi $i$ và $j$ ($i \neq j$), $f_i \neq f_j$
3. Với mọi $i$ ($0 \leq i < 2^N - 1$), $f_i$ khác $f_{i+1}$ đúng $K$ chữ số trong biểu diễn nhị phân. Ngoài ra, nếu tham số $T$ bằng 1, thì chuỗi phải được lặp lại, nghĩa là $f_{2^N - 1}$ cũng phải khác $f_0$ đúng $K$ chữ số trong biểu diễn nhị phân.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa ba số nguyên $N$, $K$ và $T$ ($2 \leq N \leq 18$, $1 \leq K < N$, $0 \leq T \leq 1$).

Dòng thứ hai chứa biểu diễn nhị phân của số bắt đầu $S$.

Dữ liệu ra

Nếu không tồn tại chuỗi như vậy, hãy in ra một dòng duy nhất chứa -1.

Nếu không, dòng đầu tiên của đầu ra phải chứa số lượng giá trị trong chuỗi liên kết — $2^N$.

Các dòng được đánh số từ 2 đến $2^N + 2$ mỗi dòng phải chứa một số nhị phân duy nhất — giá trị của $f_{i-2}$.

Nếu có nhiều lời giải hợp lệ, bạn có thể xuất ra bất kỳ lời giải nào trong số đó.

Nhiệm vụ con

Bài toán này bao gồm tám nhiệm vụ con:

1. Kiểm thử mẫu. Được 0 điểm.
2. $N = 4, K = 3, T = 1, S = 0$. Được 5 điểm.
3. $2 \leq N \leq 18, K$ là số chẵn, $T \leq 1, S < 2^N$. Được 3 điểm.
4. $2 \leq N \leq 18, K = 1, T = 1, S = 0$. Được 11 điểm.
5. $2 \leq N \leq 18, K = 3, T = 0, S = 0$. Được 15 điểm.
6. $2 \leq N \leq 18, K \cdot 2 < N, T = 0, S < 2^N$. Được 18 điểm.
7. $2 \leq N \leq 18, K < N, T = 0, S < 2^N$. Được 31 điểm.
8. $2 \leq N \leq 18, K < N, T = 1, S < 2^N$. Các ràng buộc gốc. Được 17 điểm.

Ví dụ

Dữ liệu vào 1

2 1 1
10

Dữ liệu ra 1

4
10
11
01
00