Zespół „Lyuboyn” — mały chłopiec Askhat, średni chłopiec Sanzhar i duży chłopiec Nurbakyt — postanowili poszerzyć swoją wiedzę i zgłębić tajniki elektroniki. Wymyślili dziwny przełącznik elektromechaniczny, który w specjalny sposób modyfikuje otrzymywany sygnał analogowy. Zadowoleni ze swojego wynalazku, dumnie nazwali go „przełącznikiem Lyuboyn”.

Mówiąc precyzyjnie, sygnał można przedstawić jako ciąg $N$ bitów, a „przełącznik Lyuboyn” działa tak, że sygnał wyjściowy różni się od wejściowego dokładnie na $K$ bitach, przy czym żadne dwa sygnały wejściowe nie dają tego samego sygnału wyjściowego. Aby uczynić swój wynalazek jeszcze bardziej imponującym, chłopcy dodali ostatnią funkcję: jeśli parametr binarny $T$ jest ustawiony na 1, ciąg wyjść będzie zapętlony, tzn. jeśli zaczniesz od sygnału, zastąpisz go wyjściem z przełącznika i będziesz powtarzać tę procedurę wystarczająco wiele razy, w pewnym momencie wrócisz do sygnału, od którego zacząłeś. Nie będzie to jednak prawdą, jeśli parametr $T$ jest ustawiony na 0.

W tym zadaniu musisz powtórzyć osiągnięcie zespołu i wygenerować „kod Lyuboyn” — odwzorowanie sygnałów wyjściowych dla danych sygnałów wejściowych, które wytwarza przełącznik. Dla ułatwienia wystarczy wypisać ciąg wyjść opisany powyżej, zaczynając od sygnału $S$.

Formalnie należy znaleźć ciąg $f$ o długości $2^N$ składający się z liczb binarnych o długości $N$ (wliczając wiodące zera), taki że:

1. $f_0 = S$
2. Dla każdego $i$ oraz $j$ ($i \neq j$), $f_i \neq f_j$
3. Dla każdego $i$ ($0 \le i < 2^N - 1$), $f_i$ różni się od $f_{i+1}$ dokładnie na $K$ pozycjach w reprezentacji binarnej. Ponadto, jeśli parametr $T$ jest równy 1, to ciąg musi być zapętlony, tzn. $f_{2^N - 1}$ również powinno różnić się od $f_0$ dokładnie na $K$ pozycjach w reprezentacji binarnej.

Wejście

Pierwsza linia wejścia zawiera trzy liczby całkowite $N$, $K$ oraz $T$ ($2 \le N \le 18$, $1 \le K < N$, $0 \le T \le 1$). Druga linia zawiera reprezentację binarną liczby początkowej $S$.

Wyjście

Jeśli taki ciąg nie istnieje, wypisz w jednej linii -1. W przeciwnym razie pierwsza linia wyjścia powinna zawierać liczbę wartości w ciągu — $2^N$. Kolejne linie od 2 do $2^N + 2$ powinny zawierać po jednej liczbie binarnej — wartość $f_{i-2}$. Jeśli istnieje wiele poprawnych rozwiązań, możesz wyprowadzić dowolne z nich.

Podzadania

Zadanie zawiera osiem podzadań:

1. Test przykładowy. 0 punktów.
2. $N = 4, K = 3, T = 1, S = 0$. 5 punktów.
3. $2 \le N \le 18, K$ jest parzyste, $T \le 1, S < 2^N$. 3 punkty.
4. $2 \le N \le 18, K = 1, T = 1, S = 0$. 11 punktów.
5. $2 \le N \le 18, K = 3, T = 0, S = 0$. 15 punktów.
6. $2 \le N \le 18, K \cdot 2 < N, T = 0, S < 2^N$. 18 punktów.
7. $2 \le N \le 18, K < N, T = 0, S < 2^N$. 31 punktów.
8. $2 \le N \le 18, K < N, T = 1, S < 2^N$. Oryginalne ograniczenia. 17 punktów.

Przykład

Wejście 1

2 1 1
10

Wyjście 1

4
10
11
01
00