Mały Z samodzielnie uczy się o komputerach kwantowych. Ostatnio, studiując rozdział o komunikacji kwantowej, natrafił na ciekawe zadanie. Alice i Bob prowadzą w nim komunikację kwantową. Ich językiem komunikacji jest słownik $S$ rozmiaru $n$, w którym każde słowo $s_i$ ($1\le i\le n$) można przedstawić jako 256-bitowy ciąg zer i jedynek. W tym zadaniu $s_i$ można wygenerować przez wywołanie funkcji gen, dostępnej w pliku gen.cpp w katalogu zadania. Parametry tej funkcji $n,a_1,a_2$ zostaną podane na wejściu.

Alice i Bob przeprowadzą następnie $m$ transmisji. Podczas każdej z nich Alice przesyła Bobowi dokładnie jedno słowo ze słownika. Ich kanał komunikacyjny jest jednak zawodny i podatny na szum. Dokładniej, niech $x_i$ oznacza oryginalne słowo wysłane przez Alice w transmisji $i$. Szum może odwrócić najwyżej $k_i$ bitów tego ciągu. Innymi słowy, jeśli $y_i$ oznacza ciąg odebrany przez Boba, może on różnić się od $x_i$ na najwyżej $k_i$ pozycjach, a ponadto nie musi występować w słowniku $S$.

Tymczasem Bob dowiedział się, że złoczyńca Eve również wniknął do ich kanału komunikacyjnego i zamierza zakłócać komunikację. Robi to, zastępując ciąg odebrany przez Boba dowolnym 256-bitowym ciągiem zer i jedynek, który także może nie występować w słowniku $S$. Eve jest bardzo przebiegły i nie musi ingerować w każdą transmisję.

Teraz Bob poprosił Cię o pomoc. Dla każdej kolejnej transmisji, na podstawie ostatecznie odebranego przez Boba ciągu i progu zakłóceń $k_i$ ($0\le k_i\le 15$), ustal, czy możliwe jest, że Eve nie ingerował w tę transmisję. Oznacza to, że odebrany ciąg można uzyskać ze słowa ze słownika przez odwrócenie najwyżej $k_i$ bitów. Jeśli taka możliwość istnieje, wypisz 1; w przeciwnym razie wypisz 0. Bob bardzo ufa Twoim umiejętnościom, dlatego musisz odpowiadać na bieżąco; szczegółowe wymagania opisano w sekcji wejścia.

Aby skrócić czas wczytywania, ciąg odebrany przez Boba zostanie podany jako łańcuch szesnastkowy długości 64, zawierający cyfry 0–9 oraz wielkie litery A–F. Litery A–F oznaczają kolejno wartości 10–15.

Każdą cyfrę szesnastkową można osobno przekształcić na ciąg bitów, na przykład: 5 odpowiada 0101, A odpowiada 1010, a C odpowiada 1100.

Wejście

Dane należy odczytać z pliku qi.in.

Pierwszy wiersz wejścia zawiera cztery nieujemne liczby całkowite $n,m,a_1,a_2$, oznaczające odpowiednio rozmiar słownika, liczbę transmisji oraz początkowe wartości parametrów a1 i a2 funkcji gen.

W swoim programie należy wywołać wspomnianą w treści zadania funkcję gen, aby wygenerować słownik. Można skopiować i wykorzystać kod z gen.cpp. Tablica wartości logicznych s[N+1][256] w tym programie zawiera wszystkie słowa.

Każdy z kolejnych $m$ wierszy zawiera łańcuch szesnastkowy długości 64 oraz nieujemną liczbę całkowitą $k_i$, oznaczające odpowiednio ciąg ostatecznie odebrany przez Boba w transmisji $i$ i próg zakłóceń.

Aby wymusić udzielanie odpowiedzi na bieżąco, po odtworzeniu 256-bitowego ciągu z łańcucha szesnastkowego należy wykonać XOR każdego bitu z $lastans$, otrzymując rzeczywisty ciąg odebrany przez Boba w tej transmisji. Wartość $lastans\in\{0,1\}$ jest odpowiedzią na poprzednie zapytanie; przed pierwszym zapytaniem wynosi 0.

Uwaga: przy wczytywaniu lub wypisywaniu zmiennych typu unsigned long long za pomocą funkcji scanf i printf odpowiedni specyfikator formatu to llu.

Wyjście

Wynik należy zapisać do pliku qi.out.

Wypisz $m$ wierszy, każdy zawierający liczbę całkowitą 0 lub 1, będącą odpowiedzią na bieżące zapytanie.

Przykładowe zapytania

Aby ułatwić wyjaśnienie zadania, rozważymy uproszczony przykład: słowa ze słownika są podane bezpośrednio, ich długość jest zmniejszona do 4, a na zapytania można odpowiadać offline.

Rozważmy słownik rozmiaru $n=2$, zawierający słowa 1010 i 0111.

Dla zapytania B = 1011 oraz $k_1=1$ odpowiedź wynosi 1: ciąg można uzyskać przez odwrócenie czwartego bitu słowa 1010 (pozycje liczymy od najbardziej do najmniej znaczącego bitu, również poniżej).

Dla zapytania 1 = 0001 oraz $k_2=2$ odpowiedź wynosi 1: wystarczy odwrócić drugi i trzeci bit słowa 0111.

Dla zapytania 1 = 0001 oraz $k_3=1$ odpowiedź wynosi 0.

• Odwracając najwyżej 1 bit słowa 1010, można uzyskać 1010, 0010, 1110, 1000 i 1011.
• Odwracając najwyżej 1 bit słowa 0111, można uzyskać 0111, 1111, 0011, 0101 i 0110.
• Nie można uzyskać 1 = 0001, więc ten ciąg musiał powstać wskutek ingerencji Eve.

Przykład

Przykład 1

Zobacz pliki qi/qi1.in i qi/qi1.ans w katalogu zawodnika.

Przykład 2

Zobacz pliki qi/qi2.in i qi/qi2.ans w katalogu zawodnika.

Przykład 3

Zobacz pliki qi/qi3.in i qi/qi3.ans w katalogu zawodnika.

Ograniczenia

Dla wszystkich testów: $1\le n\le 4\times10^5$, $1\le m\le 1.2\times10^5$, $0\le k\le 15$. Wartości $a_1$ i $a_2$ są losowane jednostajnie z przedziału $[0,2^{64}-1]$.