小 E ist es leid, die Antworten auf seltsame Aufgaben modulo $998244353$ oder $10^9+7$ zu berechnen, und hat sich ein Rätsel ausgedacht, das mit der Zahl $2$ zu tun hat:

Gegeben ist ein Gitter mit $2$ Zeilen und $2^k$ Spalten. Trage die Zahlen $1$ bis $2^{k+1}$ ohne Wiederholungen und Auslassungen in seine $2^{k+1}$ Zellen ein, sodass die Größenvergleiche zwischen benachbarten Zellen die folgenden Bedingungen erfüllen.

Genauer sind drei Folgen $a,b,c$ aus Nullen und Einsen mit Längen $2^k-1$, $2^k$ beziehungsweise $2^k-1$ gegeben. Eine Matrix $A$ der Größe $2\times2^k$ ist genau dann eine Lösung, wenn alle vier Bedingungen gelten:

1. $A$ enthält jede ganze Zahl aus $1,2,\ldots,2^{k+1}$ genau einmal.
2. Für alle $1\le i<2^k$ gilt $a_i=[A_{1,i}<A_{1,i+1}]$.
3. Für alle $1\le i\le2^k$ gilt $b_i=[A_{1,i}<A_{2,i}]$.
4. Für alle $1\le i<2^k$ gilt $c_i=[A_{2,i}<A_{2,i+1}]$.

Dabei ist $[P]$ gleich $1$, falls die Bedingung $P$ erfüllt ist, andernfalls $0$.

Eine beliebige Lösung zu finden oder festzustellen, dass keine existiert, wäre für dich zu einfach. Da dies ein Rätsel über $2$ ist, verlangt 小 E die Anzahl der Lösungen modulo $2$.

小 E hat $t$ Rätsel mit derselben Gittergröße vorbereitet und sie effizient zusammengepackt. Berechne für jedes Rätsel die Anzahl der Lösungen modulo $2$.

Implementierungsdetails

Du musst und sollst keine Funktion main implementieren.

Das eingereichte Programm muss den Header puzzle.h einbinden. Füge dazu am Anfang diese Zeile ein:

#include "puzzle.h"

Implementiere in deiner eingereichten Quelldatei diese Funktion:

unsigned puzzle(int t, int k, std::vector<unsigned> a,
    std::vector<unsigned> b, std::vector<unsigned> c);

• $t,k$ geben die Anzahl der Rätsel beziehungsweise die Gittergröße an.
• Für $0\le i<2^k-1$ gibt Bit $j$ ($0\le j<t$) der Binärdarstellung von $a_i$ im Rätsel $j+1$ die Vergleichsbedingung zwischen $A_{1,i+1}$ und $A_{1,i+2}$ an.
• Für $0\le i<2^k$ gibt Bit $j$ ($0\le j<t$) der Binärdarstellung von $b_i$ im Rätsel $j+1$ die Vergleichsbedingung zwischen $A_{1,i+1}$ und $A_{2,i+1}$ an.
• Für $0\le i<2^k-1$ gibt Bit $j$ ($0\le j<t$) der Binärdarstellung von $c_i$ im Rätsel $j+1$ die Vergleichsbedingung zwischen $A_{2,i+1}$ und $A_{2,i+2}$ an.
• Die Funktion muss eine nichtnegative ganze Zahl zurückgeben. Bit $j$ ($0\le j<t$) ihrer Binärdarstellung ist die Anzahl der Lösungen von Rätsel $j+1$ modulo $2$.
• Für jeden Testfall wird die Funktion von der Bewertungsbibliothek genau einmal aufgerufen.

Hinweis: Die Bewertungsbibliothek benötigt unter allen Umständen höchstens $0.1$ Sekunden Laufzeit. Ihr Speicherbedarf ist konstant und beträgt höchstens $64$ MiB.

Testen des Programms

Die Datei grader.cpp im Aufgabenverzeichnis ist eine Referenzimplementierung der Bewertungsbibliothek. Die endgültige Implementierung unterscheidet sich davon, daher darf deine Lösung nicht von den Implementierungsdetails der Bibliothek abhängen.

Im Aufgabenverzeichnis kannst du mit diesem Befehl ein ausführbares Programm erzeugen:

g++ grader.cpp puzzle.cpp -o puzzle -O2 -std=c++14 -static

Für das kompilierte Programm gilt:

• Es liest die folgenden Daten von der Standardeingabe:

  • Die erste Zeile enthält zwei positive ganze Zahlen $t,k$, die Anzahl der Rätsel und die Gittergröße.
  • Zeile $3i-1$ ($1\le i\le t$) enthält die Zeichenkette $a_1\ldots a_{2^k-1}$ aus Nullen und Einsen der Länge $2^k-1$.
  • Zeile $3i$ ($1\le i\le t$) enthält die Zeichenkette $b_1\ldots b_{2^k}$ aus Nullen und Einsen der Länge $2^k$.
  • Zeile $3i+1$ ($1\le i\le t$) enthält die Zeichenkette $c_1\ldots c_{2^k-1}$ aus Nullen und Einsen der Länge $2^k-1$.

• Es schreibt die folgenden Daten auf die Standardausgabe:

  • Insgesamt $t$ Zeilen. Zeile $i$ ($1\le i\le t$) enthält eine nichtnegative ganze Zahl, die Anzahl der Lösungen von Rätsel $i$ modulo $2$.

Beispiele

Eingabe 1

2 1
1
01
1
1
00
1

Ausgabe 1

1
0

Eingabe 2

4 2
100
1111
100
100
0000
110
110
1111
011
010
0000
010

Ausgabe 2

1
1
0
0

Zusätzliche Dateien

Die Anhänge enthalten:

1. grader.cpp: die bereitgestellte Referenzimplementierung der Bewertungsbibliothek.
2. puzzle.h: die Headerdatei; du brauchst dich nicht um ihren Inhalt zu kümmern.
3. template_puzzle.cpp: bereitgestellter Beispielcode, den du als Vorlage für deine Implementierung verwenden kannst.

Teilaufgaben

Für alle Testdaten gilt:

• $1\le t\le32$, $1\le k\le18$.
• Für alle $1\le i<2^k$ gilt $a_i\in\{0,1\}$.
• Für alle $1\le i\le2^k$ gilt $b_i\in\{0,1\}$.
• Für alle $1\le i<2^k$ gilt $c_i\in\{0,1\}$.

Besondere Eigenschaft A: $t\le4$.

Besondere Eigenschaft B: Für alle $1\le i<2^k$ gilt $b_i\ne b_{i+1}$.

Teilaufgaben

Beachte:

• Du darfst keine unerlaubten Mittel verwenden, um interne Informationen der Bewertungsbibliothek zu erhalten, etwa direkt mit der Standardein- oder Standardausgabe zu kommunizieren. Dies gilt als Betrug.
• Die endgültige Bewertungsbibliothek ist anders implementiert als die Beispielbibliothek.

Zunächst gelten dieselben Einschränkungen wie bei gewöhnlichen Aufgaben: Ein Kompilierungsfehler führt beispielsweise zu $0$ Punkten für die gesamte Aufgabe; Laufzeitfehler sowie Überschreitungen des Zeit- oder Speicherlimits führen zu $0$ Punkten für den jeweiligen Testfall. Du darfst im Programm nur auf selbst definierte Variablen und auf Variablen zugreifen, die die Bewertungsbibliothek bereitstellt. Zugriffe auf andere Speicherbereiche können zu Kompilierungs- oder Laufzeitfehlern führen.

Unter diesen Voraussetzungen gilt:

• Für jeden Testfall erhält das Programm genau dann die volle Punktzahl, wenn die beim Aufruf von puzzle zurückgegebene Antwort korrekt ist.