露露, 花花 et 萱萱 s'intéressent depuis peu aux nombres aléatoires produits par les ordinateurs. Comme chacun le sait, les suites de nombres aléatoires générées par un ordinateur ne sont pas véritablement aléatoires : ce sont des nombres pseudo-aléatoires générés suivant certaines règles.

Un jour, 露露 découvre une méthode de génération de nombres aléatoires appelée Mersenne twister. Étant donnés les paramètres initiaux $m\in\mathbb Z^+$ et $x\in\mathbb Z\cap[0,2^m)$, ainsi que la valeur initiale $M_0\in\mathbb Z\cap[0,2^m)$, elle construit la suite pseudo-aléatoire $\{M_n\}$ par la récurrence suivante :

$$ M_n=\begin{cases} 2M_{n-1},&2M_{n-1}<2^m,\\ (2M_{n-1}-2^m)\mathbin{\mathrm{xor}}x,&2M_{n-1}\ge 2^m. \end{cases} $$

Ici, $\mathrm{xor}$ désigne le ou exclusif binaire (l'opérateur ^ en C/C++). Si le choix du paramètre $x$ fait que, lorsque la longueur de la suite tend vers l'infini, ses valeurs sont approximativement équiprobables dans $\mathbb Z\cap(0,2^m)$, alors $x$ est dit « bon ». Par exemple, lorsque $m>1$, $x=0$ n'est manifestement pas bon.

Après que 露露 a présenté Mersenne twister à ses camarades, 花花 souhaite en évaluer le caractère aléatoire à l'aide de tests classiques d'aléa. À cette fin, 花花 calcule plusieurs valeurs $M_k$ sur un ordinateur.

Mais 萱萱, qui est attentive, remarque que, lors d'une saisie de $k$ en binaire, 花花 a ajouté par erreur $l$ zéros à la fin. 萱萱 s'apprête à signaler cette étourderie, mais 花花 a déjà calculé et noté la valeur erronée de $M_k$, sans conserver la valeur de $k$. Bien que cela ne constitue pas vraiment un problème fatal, lorsque 萱萱 lui signale cet oubli, 花花, perfectionniste, la supplie tout de même de l'aider à corriger la valeur de $M_k$. 萱萱 confie donc cette tâche à son intelligence artificielle : vous.

Entrée

La première ligne du fichier d'entrée random.in contient un entier strictement positif $m$. La deuxième ligne donne la représentation binaire de $x$ (soit $m$ nombres, du bit de poids faible au bit de poids fort). La troisième ligne donne la représentation binaire de $M_0$ (dans le même ordre que pour $x$). La quatrième ligne contient un entier $type$.

Deux cas sont alors possibles :

1. $type=0$ (萱萱 a noté la saisie de 花花) : la cinquième ligne contient un entier représentant la valeur correcte de $k$ notée par 萱萱.
2. $type=1$ (萱萱 n'a pas pu noter la saisie de 花花) : la cinquième ligne contient $l$ et la sixième ligne donne la représentation binaire de la valeur erronée de $M_k$ calculée par 花花.

Sortie

Le fichier de sortie random.out doit contenir une seule ligne : une chaîne de $m$ bits, composée de 0 et de 1, représentant la valeur correcte de $M_k$ que vous avez trouvée (toujours du bit de poids faible au bit de poids fort).

Exemples

Entrée 1

10
1 1 1 0 0 1 1 1 0 0
1 1 1 0 0 0 0 0 1 1
0
100

Sortie 1

0101111001

Entrée 2

10
1 1 1 0 0 1 1 1 0 0
1 1 1 0 0 0 0 0 1 1
1
3
0 1 0 1 1 1 1 1 0 1

Sortie 2

0101111001

Exemple 3

Voir random/random.in et random/random.ans dans le répertoire du candidat.

Contraintes