“Lyuboyn” チーム（小柄な Askhat、中柄な Sanzhar、大柄な Nurbakyt）は、知識を広げるために電子工学を少し学ぶことにしました。彼らは、受け取ったアナログ信号を特殊な方法で変換する奇妙な電気機械式スイッチを考案しました。彼らはこの発明を気に入り、「Lyuboyn スイッチ」と名付けました。

正確には、信号は $N$ ビットの列として表現でき、「Lyuboyn スイッチ」は、生成する出力信号が入力信号とちょうど $K$ ビット異なり、かつどの2つの入力信号も同じ出力信号を生成しないようなスイッチです。彼らは発明をさらに素晴らしいものにするため、最後の機能を追加しました。バイナリパラメータ $T$ が 1 に設定されている場合、出力の連結シーケンスはループします。つまり、ある信号から始めて、スイッチからの出力に置き換える操作を十分な回数繰り返すと、いつか最初に開始した信号に戻ります。ただし、パラメータ $T$ が 0 に設定されている場合、これは成り立ちません。

この課題では、チームの成果を再現し、「Lyuboyn コード」を生成する必要があります。これは、スイッチが生成する出力信号と入力信号の対応関係です。簡単にするために、信号 $S$ から始まる、前述の出力の連結シーケンスのみを出力してください。

形式的には、長さ $N$ のバイナリ数（先行ゼロを含む）からなる長さ $2^N$ のシーケンス $f$ を見つける必要があります。ここで、以下の条件を満たす必要があります。

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$ 桁異なっていなければなりません。

入力

入力の最初の行には、3つの整数 $N, K, T$ ($2 \leq N \leq 18, 1 \leq K < N, 0 \leq T \leq 1$) が含まれます。 2行目には、開始番号 $S$ のバイナリ表現が含まれます。

出力

そのようなシーケンスが存在しない場合は、-1 を含む単一行を出力してください。 それ以外の場合、出力の最初の行には、連結シーケンス内の値の数である $2^N$ を出力してください。 続く $2$ 行目から $2^N + 2$ 行目までには、それぞれ $f_{i-2}$ の値を表す単一のバイナリ数を出力してください。 複数の有効な解が存在する場合は、そのうちのいずれかを出力しても構いません。

小課題

この課題には8つの小課題があります。

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

出力 1

4
10
11
01
00