“Lyuboyn” 팀(작은 소년 Askhat, 중간 소년 Sanzhar, 큰 소년 Nurbakyt)은 지식을 넓히고 전자공학을 조금 공부하기로 했습니다. 그들은 입력받은 아날로그 신호를 특별한 방식으로 수정하는 기묘한 전기 기계식 스위치를 고안했습니다. 그들은 이 발명품을 자랑스럽게 “Lyuboyn 스위치”라고 이름 붙였습니다.

정확히 말하자면, 신호는 $N$ 비트의 시퀀스로 표현될 수 있으며, “Lyuboyn 스위치”는 출력 신호가 입력 신호와 정확히 $K$ 비트만큼 다르며, 서로 다른 두 입력 신호가 같은 출력 신호를 생성하지 않도록 설계되었습니다. 이 발명품을 더욱 멋지게 만들기 위해, 그들은 마지막 기능을 추가했습니다. 이진 매개변수 $T$가 1로 설정되면 출력 시퀀스는 루프를 형성합니다. 즉, 어떤 신호로 시작하여 스위치를 통해 출력 신호로 바꾸는 과정을 충분히 반복하면, 언젠가는 처음에 시작했던 신호로 돌아오게 됩니다. 하지만 매개변수 $T$가 0으로 설정되면 이 성질은 유지되지 않습니다.

이 문제에서 여러분은 팀의 업적을 재현하여 “Lyuboyn 코드”를 생성해야 합니다. 이는 스위치가 생성하는 출력 신호와 입력 신호 간의 매핑입니다. 문제를 단순화하기 위해, 신호 $S$에서 시작하여 위에서 설명한 출력 시퀀스만을 출력하면 됩니다.

형식적으로, 다음 조건을 만족하는 길이 $2^N$의 이진수(선행 0 포함) 시퀀스 $f$를 찾아야 합니다.

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}$의 값을 나타내는 이진수를 한 줄에 하나씩 출력합니다. 여러 개의 유효한 해가 존재할 경우, 그중 아무거나 출력해도 됩니다.

서브태스크

이 문제는 8개의 서브태스크로 구성됩니다.

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