Zmęczony obliczaniem odpowiedzi na rozmaite dziwaczne pytania modulo $998244353$ lub $10^9+7$, mały E zaprojektował zagadkę związaną z liczbą $2$:

Dana jest siatka mająca $2$ wiersze i $2^k$ kolumn. Należy wpisać liczby od $1$ do $2^{k+1}$ w jej $2^{k+1}$ komórek, każdą dokładnie raz, tak aby relacje wielkości między sąsiednimi komórkami spełniały poniższe ograniczenia.

Dokładniej, dane są trzy ciągi binarne $a,b,c$ o długościach odpowiednio $2^k-1,2^k,2^k-1$. Macierz $A$ o wymiarach $2\times2^k$ jest rozwiązaniem zagadki wtedy i tylko wtedy, gdy spełnia jednocześnie cztery warunki:

1. Macierz $A$ zawiera każdą z liczb całkowitych $1,2,\ldots,2^{k+1}$ dokładnie raz.
2. Dla każdego $1\le i<2^k$ zachodzi $a_i=[A_{1,i}<A_{1,i+1}]$.
3. Dla każdego $1\le i\le2^k$ zachodzi $b_i=[A_{1,i}<A_{2,i}]$.
4. Dla każdego $1\le i<2^k$ zachodzi $c_i=[A_{2,i}<A_{2,i+1}]$.

Zapis $[P]$ ma wartość $1$, jeśli warunek $P$ jest prawdziwy, i $0$ w przeciwnym razie.

Znalezienie dowolnego rozwiązania lub stwierdzenie jego braku byłoby dla ciebie zbyt proste. Ponieważ zagadka dotyczy liczby $2$, mały E wymaga obliczenia liczby rozwiązań modulo $2$.

Mały E przygotował $t$ zagadek o tym samym rozmiarze siatki i połączył je za pomocą wydajnej kompresji. Dla każdej z nich oblicz liczbę rozwiązań modulo $2$.

Szczegóły implementacji

Nie musisz i nie powinieneś implementować funkcji main.

Zgłoszony program musi dołączać plik nagłówkowy puzzle.h, czyli na jego początku należy umieścić:

#include "puzzle.h"

W zgłaszanym pliku źródłowym należy zaimplementować funkcję:

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

• $t,k$ oznaczają odpowiednio liczbę zagadek i rozmiar siatki.
• Dla $0\le i<2^k-1$ bit numer $j\ (0\le j<t)$ w zapisie binarnym $a_i$ określa ograniczenie relacji wielkości między $A_{1,i+1}$ i $A_{1,i+2}$ w zagadce numer $j+1$.
• Dla $0\le i<2^k$ bit numer $j\ (0\le j<t)$ w zapisie binarnym $b_i$ określa ograniczenie relacji wielkości między $A_{1,i+1}$ i $A_{2,i+1}$ w zagadce numer $j+1$.
• Dla $0\le i<2^k-1$ bit numer $j\ (0\le j<t)$ w zapisie binarnym $c_i$ określa ograniczenie relacji wielkości między $A_{2,i+1}$ i $A_{2,i+2}$ w zagadce numer $j+1$.
• Funkcja musi zwrócić nieujemną liczbę całkowitą, której bit numer $j\ (0\le j<t)$ w zapisie binarnym jest liczbą rozwiązań zagadki numer $j+1$ modulo $2$.
• Dla każdego testu biblioteka sprawdzająca wywoła tę funkcję dokładnie raz.

Uwaga: w każdych okolicznościach czas działania biblioteki sprawdzającej nie przekracza $0.1$ sekundy, a wykorzystywana przez nią pamięć ma stały rozmiar nieprzekraczający $64$ MiB.

Testowanie programu

Plik grader.cpp w katalogu zadania jest referencyjną implementacją biblioteki sprawdzającej. Implementacja używana w ostatecznym sprawdzaniu będzie inna, więc rozwiązanie nie powinno zależeć od szczegółów tej implementacji.

W katalogu zadania można skompilować program następującym poleceniem:

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

Skompilowany program działa następująco:

• Wczytuje ze standardowego wejścia dane w poniższym formacie:

  • Pierwszy wiersz zawiera dwie dodatnie liczby całkowite $t,k$, oznaczające odpowiednio liczbę zagadek i rozmiar siatki.
  • Wiersz $3i-1\ (1\le i\le t)$ zawiera ciąg binarny $a_1\ldots a_{2^k-1}$ długości $2^k-1$.
  • Wiersz $3i\ (1\le i\le t)$ zawiera ciąg binarny $b_1\ldots b_{2^k}$ długości $2^k$.
  • Wiersz $3i+1\ (1\le i\le t)$ zawiera ciąg binarny $c_1\ldots c_{2^k-1}$ długości $2^k-1$.

• Wypisuje na standardowe wyjście dane w poniższym formacie:

  • Wyjście składa się z $t$ wierszy. Wiersz $i\ (1\le i\le t)$ zawiera nieujemną liczbę całkowitą oznaczającą liczbę rozwiązań zagadki numer $i$ modulo $2$.

Przykład

Wejście 1

2 1
1
01
1
1
00
1

Wyjście 1

1
0

Wejście 2

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

Wyjście 2

1
1
0
0

Opis plików dodatkowych

Wśród plików dodatkowych:

1. grader.cpp to dostarczona referencyjna implementacja biblioteki sprawdzającej.
2. puzzle.h to plik nagłówkowy, którego szczegółową zawartością nie trzeba się zajmować.
3. template_puzzle.cpp to dostarczony przykładowy kod, na którym można się wzorować przy implementacji własnego rozwiązania.

Podzadania

Dla wszystkich danych testowych:

• $1\le t\le32$, $1\le k\le18$;
• dla każdego $1\le i<2^k$ zachodzi $a_i\in\{0,1\}$;
• dla każdego $1\le i\le2^k$ zachodzi $b_i\in\{0,1\}$;
• dla każdego $1\le i<2^k$ zachodzi $c_i\in\{0,1\}$.

Szczególna własność A: $t\le4$.

Szczególna własność B: dla każdego $1\le i<2^k$ zachodzi $b_i\ne b_{i+1}$.

Podzadania

Uwaga:

• Nie należy pozyskiwać wewnętrznych informacji biblioteki w niedozwolony sposób, na przykład przez bezpośrednią interakcję ze standardowymi strumieniami wejścia i wyjścia. Takie zachowanie zostanie uznane za oszustwo.
• Implementacja biblioteki używana w ostatecznym sprawdzaniu różni się od przykładowej.

Zadanie podlega najpierw takim samym ograniczeniom jak zwykłe zadania. Na przykład błąd kompilacji skutkuje wynikiem $0$ za całe zadanie, a błąd wykonania, przekroczenie limitu czasu lub pamięci itp. skutkują wynikiem $0$ za odpowiedni test. W programie można odwoływać się tylko do zmiennych zdefiniowanych samodzielnie lub udostępnionych przez bibliotekę. Próba dostępu do innych obszarów pamięci może spowodować błąd kompilacji lub wykonania.

Poza powyższymi warunkami:

• W każdym teście program otrzymuje pełną liczbę punktów wtedy i tylko wtedy, gdy odpowiedź zwrócona podczas wywołania funkcji puzzle jest poprawna.