L'équipe « Lyuboyn » — le petit Askhat, le garçon moyen Sanzhar et le grand Nurbakyt — a décidé d'élargir ses connaissances et d'étudier un peu l'électronique. Ils ont inventé un étrange commutateur électromécanique qui modifie le signal analogique qu'il reçoit d'une manière particulière. Satisfaits de leur invention, ils l'ont fièrement baptisé « Le commutateur Lyuboyn ».

Pour être précis, un signal peut être représenté comme une séquence de $N$ bits, et « Le commutateur Lyuboyn » est tel que le signal de sortie qu'il produit diffère de l'entrée d'exactement $K$ bits, et aucun signal d'entrée ne produit le même signal de sortie. Pour rendre leur invention encore plus remarquable, les garçons ont ajouté une fonctionnalité finale : si le paramètre binaire $T$ est réglé sur 1, la séquence liée des sorties sera bouclée, c'est-à-dire que si vous commencez avec un signal, que vous le remplacez par sa sortie du commutateur et que vous répétez la procédure suffisamment de fois, vous finirez par revenir au signal avec lequel vous avez commencé. Cela ne sera cependant pas vrai si le paramètre $T$ est réglé sur 0.

Dans cette tâche, vous devez reproduire l'exploit de l'équipe et générer « Le code Lyuboyn » — le mappage des signaux de sortie aux signaux d'entrée donnés que le commutateur produit. Pour simplifier les choses, vous n'avez besoin que de sortir la séquence liée des sorties telle que décrite ci-dessus, en commençant par un signal $S$.

Formellement, vous devez trouver une séquence $f$ de longueur $2^N$ composée de nombres binaires de longueur $N$ (incluant les zéros non significatifs), telle que :

1. $f_0 = S$
2. Pour tout $i$ et $j$ ($i \neq j$), $f_i \neq f_j$
3. Pour tout $i$ ($0 \le i < 2^N - 1$), $f_i$ diffère de $f_{i+1}$ d'exactement $K$ chiffres dans leur représentation binaire. De plus, si le paramètre $T$ est égal à 1, alors la séquence doit être bouclée, c'est-à-dire que $f_{2^N - 1}$ doit également différer de $f_0$ d'exactement $K$ chiffres dans leur représentation binaire.

Entrée

La première ligne de l'entrée contient trois nombres entiers $N$, $K$ et $T$ ($2 \le N \le 18$, $1 \le K < N$, $0 \le T \le 1$).

La deuxième ligne contient la représentation binaire du nombre de départ $S$.

Sortie

Si aucune séquence de ce type n'existe, imprimez une seule ligne contenant -1.

Sinon, la première ligne de la sortie doit contenir le nombre de valeurs dans la séquence liée — $2^N$.

Les lignes numérotées de 2 à $2^N + 2$ doivent contenir chacune un seul nombre binaire — la valeur de $f_{i-2}$.

Si plusieurs solutions valides existent, vous pouvez en afficher n'importe laquelle.

Sous-tâches

Cette tâche contient huit sous-tâches :

1. Test d'exemple. 0 point.
2. $N = 4, K = 3, T = 1, S = 0$. 5 points.
3. $2 \le N \le 18, K$ est pair, $T \le 1, S < 2^N$. 3 points.
4. $2 \le N \le 18, K = 1, T = 1, S = 0$. 11 points.
5. $2 \le N \le 18, K = 3, T = 0, S = 0$. 15 points.
6. $2 \le N \le 18, K \cdot 2 < N, T = 0, S < 2^N$. 18 points.
7. $2 \le N \le 18, K < N, T = 0, S < 2^N$. 31 points.
8. $2 \le N \le 18, K < N, T = 1, S < 2^N$. Contraintes originales. 17 points.

Exemples

Entrée 1

2 1 1
10

Sortie 1

4
10
11
01
00