Anna i Bruno są mistrzami hazardu. Zagrają z D-taro, który jest krupierem w tej grze.

W tej grze Anna i Bruno przebywają w różnych pokojach. Mogą komunikować się ze sobą wyłącznie za pomocą uszkodzonego urządzenia. D-taro przekazuje Annie liczbę całkowitą. Celem Anny i Bruna jest przesłanie tej liczby od Anny do Bruna za pomocą urządzenia.

Na początku gry Anna deklaruje liczbę całkowitą $m$ z przedziału od $1$ do $2\,000$ włącznie. Następnie rozgrywają $Q$ rund. Runda $i$ ($1 \le i \le Q$) przebiega następująco.

1. D-taro przekazuje Annie liczbę całkowitą $A_i$.
2. Anna wprowadza do urządzenia tablice $s_i,t_i$. Każdy element tablic $s_i,t_i$ musi być równy $0$ lub $1$. Tablice $s_i,t_i$ muszą mieć tę samą długość, z przedziału od $1$ do $m$ włącznie.
3. Niech $u_i$ będzie tablicą otrzymaną z tablic $s_i$ i $t_i$ przez przeplatanie (opisane poniżej). Urządzenie przesyła $u_i$ Brunowi.
4. Bruno przesyła D-taro liczbę całkowitą. Jeżeli jest ona równa liczbie $A_i$ przekazanej Annie przez D-taro, Anna i Bruno wygrywają tę rundę.

Napisz programy realizujące strategie Anny i Bruna tak, aby wygrali wszystkie $Q$ rund.

Przeplatanie

Mówimy, że tablica $Z$ jest otrzymana z tablic $X$ i $Y$ przez przeplatanie, jeżeli można podzielić elementy tablicy $Z$ na dwie grupy tak, aby spełnione były następujące dwa warunki.

• Tablica złożona z elementów pierwszej grupy, z zachowaniem ich kolejności, jest równa tablicy $X$.
• Tablica złożona z elementów drugiej grupy, z zachowaniem ich kolejności, jest równa tablicy $Y$.

Na przykład tablica $Z=[1,1,1,0,0,0]$ jest otrzymana z $X=[1,1,0]$ i $Y=[1,0,0]$ przez przeplatanie, ponieważ tablica złożona z pierwszego, drugiego i czwartego elementu $Z$, w tej kolejności, to $[1,1,0]$, a tablica złożona z trzeciego, piątego i szóstego elementu $Z$, w tej kolejności, to $[1,0,0]$.

Natomiast dla $X=[1,1,0]$, $Y=[1,0,0]$ oraz $Z=[0,0,0,1,1,1]$ tablica $Z$ nie jest otrzymana z $X$ i $Y$ przez przeplatanie.

Szczegóły implementacji

Należy przesłać dwa pliki.

Pierwszym plikiem jest Anna.cpp. Powinien on realizować strategię Anny i implementować następujące funkcje. Program powinien dołączyć Anna.h za pomocą dyrektywy preprocesora #include.

int Declare()

Ta funkcja jest wywoływana raz na początku.

• Zwracaną wartością jest liczba całkowita $m$ zadeklarowana przez Annę.
• Liczba całkowita $m$ musi należeć do przedziału od $1$ do $2\,000$ włącznie. Jeżeli ten warunek nie jest spełniony, program otrzyma werdykt Wrong Answer [1].

std::pair<std::vector<int>, std::vector<int> > Anna(long long A)

Po wywołaniu Declare ta funkcja jest wywoływana $Q$ razy. Jej $i$-te wywołanie ($1 \le i \le Q$) odpowiada krokom 1 i 2 rundy $i$.

• Parametr A to liczba całkowita $A_i$ przekazana Annie przez D-taro.
• Zwracaną wartością jest para dwóch tablic $s_i,t_i$ wprowadzonych przez Annę do urządzenia.
• Każdy element tablic $s_i,t_i$ musi być równy $0$ lub $1$. Jeżeli ten warunek nie jest spełniony, program otrzyma werdykt Wrong Answer [2].
• Długości obu tablic $s_i,t_i$ muszą należeć do przedziału od $1$ do $m$ włącznie. Jeżeli ten warunek nie jest spełniony, program otrzyma werdykt Wrong Answer [3].
• Tablice $s_i,t_i$ muszą mieć tę samą długość. Jeżeli ten warunek nie jest spełniony, program otrzyma werdykt Wrong Answer [4].

Drugim plikiem jest Bruno.cpp. Powinien on realizować strategię Bruna i implementować następującą funkcję. Program powinien dołączyć Bruno.h za pomocą dyrektywy preprocesora #include.

long long Bruno(std::vector<int> u)

Po wprowadzeniu tablic do urządzenia przez Annę ta funkcja jest wywoływana raz. Łącznie jest wywoływana $Q$ razy. Jej $i$-te wywołanie ($1 \le i \le Q$) odpowiada krokom 3 i 4 rundy $i$.

• Parametr u to tablica $u_i$ przesłana przez urządzenie Brunowi w rundzie $i$.
• Zwracaną wartością jest liczba całkowita przesłana przez Bruna do D-taro.
• Zwracana wartość musi być równa liczbie całkowitej $A_i$ przekazanej Annie przez D-taro. Jeżeli ten warunek nie jest spełniony, program otrzyma werdykt Wrong Answer [5].

Ważne uwagi

• Program może implementować inne funkcje do użytku wewnętrznego lub używać zmiennych globalnych. Przesłane pliki zostaną skompilowane razem z programem oceniającym do jednego pliku wykonywalnego. Wszystkie zmienne globalne i funkcje wewnętrzne należy zadeklarować w nienazwanej przestrzeni nazw, aby uniknąć konfliktów z innymi plikami. Podczas oceniania program zostanie uruchomiony jako dwa procesy: Anny i Bruna. Proces Anny i proces Bruna nie mogą współdzielić zmiennych globalnych.
• Program nie może korzystać ze standardowego wejścia ani standardowego wyjścia. Nie może też w żaden sposób komunikować się z innymi plikami. Może jednak wypisywać informacje diagnostyczne na standardowe wyjście błędów.

Kompilacja i uruchamianie testów

Ze strony konkursu można pobrać archiwum zawierające przykładowy program oceniający do testowania swojego programu. Archiwum zawiera również przykładowy plik źródłowy Twojego programu.

Przykładowy program oceniający znajduje się w pliku grader.cpp. Aby przetestować program, umieść grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h w tym samym katalogu i wykonaj następujące polecenie kompilacji.

g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Po pomyślnej kompilacji powstanie plik wykonywalny grader.

Pamiętaj, że właściwy program oceniający różni się od przykładowego. Przykładowy program oceniający działa jako jeden proces, który odczytuje dane ze standardowego wejścia i wypisuje wyniki na standardowe wyjście.

Wejście przykładowego programu oceniającego

Przykładowy program oceniający odczytuje ze standardowego wejścia następujące dane.

$$ \begin{gathered} Q\\ A_1\\ A_2\\ \vdots\\ A_Q \end{gathered} $$

Wyjście przykładowego programu oceniającego

Przykładowy program oceniający wypisuje na standardowe wyjście następujące informacje (cudzysłowy służą przejrzystości).

• Jeżeli program zostanie uznany za poprawny, wypisuje wartość $m$ zwróconą przez funkcję Declare w postaci „Accepted: 2000”.
• Jeżeli program otrzyma którykolwiek z werdyktów błędnej odpowiedzi, przykładowy program oceniający wypisuje jego typ w postaci „Wrong Answer [1]”.

Jeżeli program spełnia warunki kilku typów błędnej odpowiedzi, przykładowy program oceniający zgłasza tylko jeden z nich.

Podczas działania przykładowego programu oceniającego przeplatanie w każdej rundzie jest obliczane przy użyciu liczb pseudolosowych. Wyniki nie zmieniają się pomiędzy uruchomieniami. Aby zmienić ziarno generatora liczb pseudolosowych, uruchom przykładowy program oceniający w następujący sposób.

./grader 2022

Pierwszy argument musi być liczbą całkowitą.

Ograniczenia

• $1 \le Q \le 1\,000$.
• $1 \le A_i \le 1\,000\,000\,000\,000\,000\,000\ (=10^{18})$ ($1 \le i \le Q$).

Podzadania

1. (5 punktów) $A_i \le 2\,000$ ($1 \le i \le Q$).
2. (5 punktów) $A_i \le 4\,000\,000$ ($1 \le i \le Q$).
3. (3 punkty) $A_i \le 10\,000\,000\ (=10^7)$ ($1 \le i \le Q$).
4. (12 punktów) $A_i \le 100\,000\,000\ (=10^8)$ ($1 \le i \le Q$).
5. (15 punktów) $A_i \le 100\,000\,000\,000\ (=10^{11})$ ($1 \le i \le Q$).

6. (60 punktów) Brak dodatkowych ograniczeń. W tym podzadaniu wynik jest obliczany następująco.

   • Niech $m^*$ będzie największą z liczb całkowitych $m$ zadeklarowanych przez Annę we wszystkich testach tego podzadania.
   • Liczba punktów jest następująca.

Przykład komunikacji

Poniżej podano przykładowe wejście dla przykładowego programu oceniającego i odpowiadające mu wywołania funkcji.

Wejście 1

2
42
2000

Przykładowe wywołania funkcji

W tym przykładzie wejścia rozgrywane jest $Q\ (=2)$ rund. W rundzie $1$ D-taro przekazuje Annie liczbę całkowitą $A_1\ (=42)$. W rundzie $2$ D-taro przekazuje Annie liczbę całkowitą $A_2\ (=2000)$.

Ten przykład wejścia spełnia ograniczenia wszystkich podzadań.