小 Z étudie seul l'informatique quantique. En lisant récemment le chapitre consacré aux communications quantiques, il a rencontré un problème intéressant. Alice et Bob communiquent à l'aide d'un dictionnaire $S$ de taille $n$, dont chaque mot $s_i$ ($1\le i\le n$) est représenté par une chaîne binaire de 256 bits. Dans ce problème, les $s_i$ peuvent être générés en appelant la fonction gen, disponible dans gen.cpp dans le répertoire du problème. Ses paramètres n, a1, a2 sont fournis dans l'entrée.

Alice et Bob vont effectuer $m$ communications. Pour chacune, Alice transmet à Bob exactement un mot du dictionnaire. Mais leur canal n'est pas fiable et subit du bruit. Plus précisément, lors de la $i$-ième transmission, si Alice envoie le mot $x_i$, le bruit peut en inverser au plus $k_i$ bits. Autrement dit, la chaîne $y_i$ reçue par Bob peut différer de $x_i$ en au plus $k_i$ positions, et peut ne pas appartenir au dictionnaire $S$.

Bob apprend également qu'Eve, un malfaiteur, s'est introduit dans leur canal pour perturber les communications. Il peut remplacer la chaîne reçue par Bob par n'importe quelle chaîne binaire de 256 bits, qui peut ne pas appartenir à $S$. Eve est très rusé : il ne perturbe pas nécessairement toutes les communications.

Bob vous demande maintenant de l'aider. Pour chaque communication à venir, connaissant la chaîne finalement reçue et le seuil de bruit $k_i$ ($0\le k_i\le15$), déterminez s'il est possible qu'Eve ne soit pas intervenu : la chaîne reçue doit pouvoir être obtenue à partir d'un mot du dictionnaire en inversant au plus $k_i$ bits. Affichez $1$ si cette absence d'intervention est possible, et $0$ sinon. Bob a confiance en vous : vous devez répondre en ligne, selon les modalités précisées dans le format d'entrée.

Pour réduire le temps de lecture, les chaînes reçues par Bob sont fournies sous forme de chaînes hexadécimales de longueur 64. Elles contiennent les chiffres 0 à 9 et les lettres majuscules A à F, ces dernières représentant respectivement les valeurs $10$ à $15$.

La conversion en binaire s'effectue chiffre par chiffre : par exemple, 5 correspond à 0101, A à 1010 et C à 1100.

Entrée

Lisez les données dans le fichier qi.in.

La première ligne contient quatre entiers non négatifs $n,m,a_1,a_2$, représentant respectivement la taille du dictionnaire, le nombre de communications et les valeurs initiales des paramètres a1, a2 de gen.

Votre programme doit appeler la fonction gen décrite dans l'énoncé pour générer le dictionnaire. Vous pouvez copier et utiliser le code de gen.cpp. Le tableau booléen s[N+1][256] contient tous les mots.

Chacune des $m$ lignes suivantes contient une chaîne hexadécimale de longueur 64 et un entier non négatif $k_i$, représentant la chaîne finalement reçue par Bob lors de la $i$-ième communication et son seuil de bruit.

Pour imposer le traitement en ligne, après avoir converti la chaîne hexadécimale en 256 bits, vous devez appliquer un OU exclusif à chacun de ses bits avec $lastans$ pour obtenir la véritable chaîne reçue par Bob. $lastans\in\{0,1\}$ est la réponse à la requête précédente ; avant la première requête, sa valeur initiale est $0$.

Attention : pour lire ou afficher des variables de type unsigned long long avec scanf et printf, le spécificateur correspondant est llu.

Sortie

Écrivez la sortie dans le fichier qi.out.

Affichez $m$ lignes, chacune contenant un entier $0$ ou $1$, la réponse à la requête correspondante.

Exemples de requêtes

Pour faciliter l'explication, nous illustrons une version simplifiée : les mots du dictionnaire sont donnés directement, leur longueur est réduite à 4 bits et les réponses peuvent être calculées hors ligne.

Considérons un dictionnaire de taille $n=2$, contenant les mots 1010 et 0111.

Pour la requête B = 1011 avec $k_1=1$, la réponse est $1$ : on inverse le quatrième bit de 1010 (en comptant des bits de poids fort vers ceux de poids faible, comme dans la suite).

Pour la requête 1 = 0001 avec $k_2=2$, la réponse est $1$ : on inverse les deuxième et troisième bits de 0111.

Pour la requête 1 = 0001 avec $k_3=1$, la réponse est $0$.

• En inversant au plus un bit de 1010, on peut obtenir 1010, 0010, 1110, 1000, 1011.
• En inversant au plus un bit de 0111, on peut obtenir 0111, 1111, 0011, 0101, 0110.
• On ne peut pas obtenir 1 = 0001, qui provient donc nécessairement d'une intervention d'Eve.

Exemples

Exemple 1

Voir les fichiers qi/qi1.in et qi/qi1.ans dans le répertoire des candidats.

Exemple 2

Voir les fichiers qi/qi2.in et qi/qi2.ans dans le répertoire des candidats.

Exemple 3

Voir les fichiers qi/qi3.in et qi/qi3.ans dans le répertoire des candidats.

Contraintes

Pour tous les tests : $1\le n\le4\times10^5$, $1\le m\le1.2\times10^5$, $0\le k\le15$. Les valeurs $a_1,a_2$ sont générées uniformément au hasard dans $[0,2^{64}-1]$.