Команда «Lyuboyn» — маленький Асхат, средний Санжар и большой Нурбакыт — решили расширить свои знания и немного изучить электронику. Они придумали странный электромеханический переключатель, который особым образом изменяет аналоговый сигнал, поступающий на него. Довольные своим изобретением, они с гордостью назвали его «переключателем Lyuboyn».

Если говорить точнее, сигнал можно представить как последовательность из $N$ бит, а «переключатель Lyuboyn» устроен так, что выходной сигнал отличается от входного ровно на $K$ бит, при этом никакие два различных входных сигнала не дают одинаковый выходной сигнал. Чтобы сделать свое изобретение еще более впечатляющим, ребята добавили финальную особенность: если бинарный параметр $T$ установлен в 1, то связанная последовательность выходов будет циклической, то есть если вы начнете с некоторого сигнала, замените его на выходной сигнал переключателя и будете повторять эту процедуру достаточное количество раз, то в какой-то момент вы вернетесь к сигналу, с которого начали. Однако это не будет выполняться, если параметр $T$ установлен в 0.

В этой задаче вам требуется повторить достижение команды и сгенерировать «код Lyuboyn» — отображение выходных сигналов для заданных входных сигналов, которое производит переключатель. Для упрощения вам нужно вывести только связанную последовательность выходов, как описано выше, начиная с сигнала $S$.

Формально вам нужно найти последовательность $f$ длины $2^N$, состоящую из двоичных чисел длины $N$ (включая ведущие нули), такую что:

1. $f_0 = S$
2. Для любых $i$ и $j$ ($i \neq j$), $f_i \neq f_j$
3. Для любого $i$ ($0 \le i < 2^N - 1$), $f_i$ отличается от $f_{i+1}$ ровно в $K$ разрядах в двоичном представлении. Также, если параметр $T$ равен 1, то последовательность должна быть циклической, т.е. $f_{2^N - 1}$ также должно отличаться от $f_0$ ровно в $K$ разрядах в двоичном представлении.

Входные данные

Первая строка входных данных содержит три целых числа $N$, $K$ и $T$ ($2 \le N \le 18$, $1 \le K < N$, $0 \le T \le 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 \le N \le 18$, $K$ четное, $T \le 1$, $S < 2^N$. 3 балла.
4. $2 \le N \le 18$, $K = 1, T = 1, S = 0$. 11 баллов.
5. $2 \le N \le 18$, $K = 3, T = 0, S = 0$. 15 баллов.
6. $2 \le N \le 18$, $K \cdot 2 < N, T = 0, S < 2^N$. 18 баллов.
7. $2 \le N \le 18$, $K < N, T = 0, S < 2^N$. 31 балл.
8. $2 \le N \le 18$, $K < N, T = 1, S < 2^N$. Исходные ограничения. 17 баллов.

Примеры

Входные данные 1

2 1 1
10

Выходные данные 1

4
10
11
01
00