“Lyuboyn” 團隊——小男孩 Askhat、中男孩 Sanzhar 和大男孩 Nurbakyt——決定擴展他們的知識，研究一點電子學。他們發明了一種奇特的機電開關，能以特殊方式修改接收到的類比訊號。他們對這項發明感到滿意，並自豪地將其命名為「Lyuboyn 開關」。

準確地說，一個訊號可以表示為一個長度為 $N$ 的位元序列，而「Lyuboyn 開關」的特性是：它產生的輸出訊號與輸入訊號恰好有 $K$ 個位元不同，且沒有兩個不同的輸入訊號會產生相同的輸出訊號。為了讓他們的發明更出色，男孩們增加了最後一個功能：如果二進位參數 $T$ 被設為 1，則輸出的連結序列將會形成一個迴圈，也就是說，如果你從一個訊號開始，將其替換為開關產生的輸出，並重複此過程足夠多次，在某個時刻你會回到最初開始的訊號。然而，如果參數 $T$ 被設為 0，則此特性不一定成立。

在這項任務中，你需要重現該團隊的成就並產生「Lyuboyn 代碼」——即開關產生的輸出訊號與給定輸入訊號的映射。為了簡化問題，你只需要輸出上述的連結序列，並以訊號 $S$ 作為起點。

形式上，你需要找到一個長度為 $2^N$ 的序列 $f$，由長度為 $N$ 的二進位數字（包含前導零）組成，滿足以下條件：

1. $f_0 = S$
2. 對於所有 $i$ 和 $j$ ($i \neq j$)，$f_i \neq f_j$
3. 對於任何 $i$ ($0 \leq i < 2^N - 1$)，$f_i$ 與 $f_{i+1}$ 在二進位表示中恰好有 $K$ 個位元不同。此外，如果參數 $T$ 等於 1，則該序列必須形成迴圈，即 $f_{2^N - 1}$ 與 $f_0$ 在二進位表示中也必須恰好有 $K$ 個位元不同。

輸入格式

第一行包含三個整數 $N$、$K$ 和 $T$ ($2 \leq N \leq 18, 1 \leq K < N, 0 \leq T \leq 1$)。 第二行包含起始數字 $S$ 的二進位表示。

輸出格式

如果不存在這樣的序列，請輸出單行 -1。 否則，輸出的第一行應包含連結序列中的數值個數——$2^N$。 從第 2 行到第 $2^N + 2$ 行，每行應包含一個二進位數字——即 $f_{i-2}$ 的值。 如果存在多個有效的解，你可以輸出其中任何一個。

子任務

本任務包含八個子任務：

1. 範例測試。得分 0 分。
2. $N = 4, K = 3, T = 1, S = 0$。得分 5 分。
3. $2 \leq N \leq 18, K$ 為偶數, $T \leq 1, S < 2^N$。得分 3 分。
4. $2 \leq N \leq 18, K = 1, T = 1, S = 0$。得分 11 分。
5. $2 \leq N \leq 18, K = 3, T = 0, S = 0$。得分 15 分。
6. $2 \leq N \leq 18, K \cdot 2 < N, T = 0, S < 2^N$。得分 18 分。
7. $2 \leq N \leq 18, K < N, T = 0, S < 2^N$。得分 31 分。
8. $2 \leq N \leq 18, K < N, T = 1, S < 2^N$。原始限制。得分 17 分。

範例

範例 1

2 1 1
10

4
10
11
01
00