小 Z bringt sich gerade Wissen über Quantencomputer bei. Kürzlich hat er beim Studium des Kapitels über Quantenkommunikation eine interessante Aufgabe entdeckt. Darin kommunizieren Alice und Bob mittels Quantenkommunikation. Ihre Kommunikationssprache ist ein Wörterbuch $S$ der Größe $n$. Jedes Wort $s_i$ mit $1\le i\le n$ lässt sich als eine Bitfolge der Länge $256$ darstellen. In dieser Aufgabe können die Wörter $s_i$ durch Aufrufen der Funktion gen erzeugt werden, die du in gen.cpp im Aufgabenverzeichnis findest. Die Parameter n, a1 und a2 dieser Funktion werden in der Eingabe angegeben.

Alice und Bob werden nun $m$ Übertragungen durchführen. Bei jeder sendet Alice genau ein Wort aus dem Wörterbuch an Bob. Der verwendete Kommunikationskanal ist jedoch unzuverlässig und wird durch Rauschen gestört. Genauer gesagt sei $x_i$ das ursprüngliche Wort, das Alice bei der $i$-ten Übertragung sendet. Durch Rauschen können höchstens $k_i$ Bits dieser Bitfolge umgekehrt werden. Bezeichnet $y_i$ die von Bob empfangene Bitfolge, können sich also höchstens $k_i$ ihrer Bits von $x_i$ unterscheiden. Außerdem muss $y_i$ nicht im Wörterbuch $S$ vorkommen.

Zugleich hat Bob erfahren, dass der Bösewicht Eve ebenfalls in ihren Kommunikationskanal eingedrungen ist und ihre Kommunikation stören will. Er ersetzt die Bitfolge, die Bob empfängt, durch eine beliebige Bitfolge der Länge $256$, die ebenfalls nicht im Wörterbuch $S$ vorkommen muss. Eve ist sehr gerissen und greift nicht unbedingt bei jeder Übertragung ein.

Nun bittet Bob dich um Hilfe. Für jede der kommenden Übertragungen musst du anhand der endgültig von Bob empfangenen Bitfolge und des Rauschschwellwerts $k_i$ mit $0\le k_i\le 15$ feststellen, ob es möglich ist, dass Eve diese Übertragung nicht gestört hat. Das bedeutet, dass Bobs empfangene Bitfolge durch Umkehren von höchstens $k_i$ Bits eines Wortes aus dem Wörterbuch entstehen kann. Ist es möglich, dass Eve nicht eingegriffen hat, gib 1 aus, andernfalls 0. Bob vertraut auf deine Fähigkeiten; daher musst du die Anfragen online beantworten. Die genauen Anforderungen stehen im Abschnitt zur Eingabe.

Um die Einlesezeit zu verkürzen, werden die von Bob empfangenen Folgen als Hexadezimalzeichenketten der Länge $64$ angegeben. Diese enthalten die Ziffern 0 bis 9 und die Großbuchstaben A bis F, wobei A bis F der Reihe nach für die Werte $10$ bis $15$ stehen.

Eine Hexadezimalzeichenkette lässt sich Zeichen für Zeichen in eine Bitfolge umwandeln. Beispielsweise entspricht 5 der Folge 0101, A der Folge 1010 und C der Folge 1100.

Eingabe

Lies die Daten aus der Datei qi.in.

Die erste Eingabezeile enthält vier nichtnegative ganze Zahlen $n,m,a_1,a_2$: die Wörterbuchgröße, die Anzahl der Übertragungen und die Anfangswerte der Parameter a1 und a2 der Funktion gen.

Du musst in deinem Programm die in der Aufgabenstellung erwähnte Funktion gen aufrufen, um die Wortliste zu erzeugen. Du darfst den Code aus gen.cpp kopieren und verwenden. Das boolesche Array s[N+1][256] im Programm enthält sämtliche Wörter.

Es folgen $m$ Zeilen, jeweils mit einer Hexadezimalzeichenkette der Länge $64$ und einer nichtnegativen ganzen Zahl $k_i$. Diese geben die endgültig von Bob bei der $i$-ten Übertragung empfangene Bitfolge und den Rauschschwellwert an.

Damit die Anfragen zwingend online beantwortet werden, musst du nach dem Umwandeln der Hexadezimalzeichenkette in eine Bitfolge der Länge $256$ jedes Bit mit $lastans$ durch XOR verknüpfen. Erst dann erhältst du die Bitfolge, die Bob bei dieser Übertragung tatsächlich empfängt. Dabei ist $lastans\in\{0,1\}$ die Antwort auf die vorherige Anfrage; vor der ersten Anfrage gilt anfangs $lastans=0$.

Hinweis: Beim Einlesen oder Ausgeben von Variablen des Typs unsigned long long mit scanf beziehungsweise printf lautet der entsprechende Platzhalter llu.

Ausgabe

Schreibe die Ausgabe in die Datei qi.out.

Gib insgesamt $m$ Zeilen aus. Jede enthält eine ganze Zahl 0 oder 1, die Antwort auf die aktuelle Anfrage.

Beispiele für Anfragen

Um die Aufgabenstellung leichter erklären zu können, betrachten wir einen vereinfachten Fall: Die Wörter des Wörterbuchs werden direkt angegeben, ihre Länge ist auf $4$ verkürzt, und die Anfragen dürfen offline beantwortet werden.

Betrachte ein Wörterbuch der Größe $n=2$ mit den Wörtern 1010 und 0111.

Für die Anfrage B = 1011 und $k_1=1$ lautet die Antwort 1. Die Folge entsteht durch Umkehren des 4. Bits von 1010 (von der höchstwertigen zur niedrigstwertigen Stelle gezählt, ebenso im Folgenden).

Für die Anfrage 1 = 0001 und $k_2=2$ lautet die Antwort 1. Die Folge entsteht durch Umkehren des 2. und 3. Bits von 0111.

Für die Anfrage 1 = 0001 und $k_3=1$ lautet die Antwort 0.

• Durch Umkehren von höchstens einem Bit von 1010 erhält man 1010, 0010, 1110, 1000 oder 1011.
• Durch Umkehren von höchstens einem Bit von 0111 erhält man 0111, 1111, 0011, 0101 oder 0110.
• 1 = 0001 lässt sich nicht erzeugen und muss deshalb durch einen Eingriff von Eve entstanden sein.

Beispiele

Beispiel 1

Siehe qi/qi1.in und qi/qi1.ans im Teilnehmerverzeichnis.

Beispiel 2

Siehe qi/qi2.in und qi/qi2.ans im Teilnehmerverzeichnis.

Beispiel 3

Siehe qi/qi3.in und qi/qi3.ans im Teilnehmerverzeichnis.

Beschränkungen

Für alle Testfälle gilt: $1\le n\le 4\times 10^5$, $1\le m\le 1.2\times 10^5$, $0\le k\le 15$. $a_1$ und $a_2$ werden gleichverteilt zufällig aus $[0,2^{64}-1]$ erzeugt.