Aidos wymyślił łamigłówkę i rzucił wyzwanie Temirulanowi, aby ją rozwiązał. Wybrał ciąg $a$ składający się z $n$ różnych nieujemnych liczb całkowitych ponumerowanych od $1$ do $n$: $a_1, a_2, \dots, a_n$.

Temirulan może zadawać dwa rodzaje pytań:

• ask — ujawnia liczbę na pozycji $i$ danego ciągu.
• get_pairwise_xor — dla podanego ciągu różnych liczb całkowitych $i_1, i_2, \dots, i_k$, zwraca zbiór wartości operacji XOR dla elementów ciągu $a$ na indeksach $i_1, i_2, \dots, i_k$, czyli $\{a_{i_x} \oplus a_{i_y} \mid 1 \le x, y \le k\}$.

Na przykład, załóżmy, że Aidos wybrał ciąg $[1, 5, 6, 3]$. Wtedy dla pytania ask(2), Aidos odpowie liczbą $5$, a dla pytania get_pairwise_xor({3, 4}), Aidos odpowie ciągiem $[0, 0, 5, 5]$, ponieważ:

• $a_3 \oplus a_4 = 6 \oplus 3 = 5$
• $a_4 \oplus a_3 = 3 \oplus 6 = 5$
• $a_3 \oplus a_3 = 6 \oplus 6 = 0$
• $a_4 \oplus a_4 = 3 \oplus 3 = 0$

Temirulan nie poradził sobie z łamigłówką, a Twoim zadaniem jest mu pomóc. Znajdź ukryty ciąg, używając opisanych powyżej pytań.

Wejście

TWOJE ROZWIĄZANIA NIE MOGĄ CZYTAĆ ZE STANDARDOWEGO WEJŚCIA, PISAĆ NA STANDARDOWE WYJŚCIE ANI INTERAGOWAĆ Z ŻADNYM INNYM PLIKIEM.

Twoim zadaniem jest zaimplementowanie następującej funkcji: int[] guess(int n)

• $n$: długość ukrytego ciągu.
• Funkcja jest wywoływana dokładnie raz dla każdego testu.
• Funkcja musi zwrócić ukryty ciąg w tej samej kolejności.

Twoja funkcja może wywoływać następujące funkcje:

1. int ask(int i)

   • $i$: indeks liczby w ciągu, $1 \le i \le n$.
   • Funkcja zwraca $i$-tą liczbę ukrytego ciągu.

2. int[] get_pairwise_xor(int[] pos)

   • pos: niepusta lista indeksów ciągu.
   • Wszystkie elementy w pos muszą być różnymi liczbami całkowitymi.
   • Niech $k$ będzie liczbą elementów w pos. Wtedy $1 \le pos_i \le n$ dla każdego $1 \le i \le k$.
   • Funkcja zwraca posortowaną listę $k^2$ elementów: zbiór wartości XOR, $\{a_{pos_x} \oplus a_{pos_y} \mid 1 \le x, y \le k\}$.

Możesz wywołać obie funkcje łącznie nie więcej niż $200$ razy dla każdego testu. Jeśli którykolwiek z powyższych warunków zostanie naruszony, Twój program otrzyma werdykt Błędna Odpowiedź (Wrong Answer). W przeciwnym razie Twój program otrzyma werdykt Zaakceptowano (Accepted), a Twój wynik zostanie obliczony na podstawie całkowitej liczby wywołań funkcji ask oraz get_pairwise_xor (patrz sekcja „Punktacja”).

Podzadania

• $2 \le n \le 100$
• $0 \le a_i \le 10^9$ dla każdego $1 \le i \le n$.

W tym zadaniu sprawdzarka NIE jest adaptacyjna. Oznacza to, że ciąg $a$ jest ustalony na początku działania sprawdzarki i nie zależy od wywołań z Twojego programu.

1. (6 punktów) $n \le 4$
2. (94 punkty) Brak dodatkowych ograniczeń. Dla tego podzadania Twój wynik jest obliczany w następujący sposób. Niech $q$ będzie całkowitą liczbą wywołań funkcji ask oraz get_pairwise_xor.
   • Jeśli $q \le 15$, Twój wynik wynosi $94$.
   • Jeśli $15 < q \le 40$, Twój wynik wynosi $84 - 2(q - 16)$.
   • Jeśli $40 < q \le 50$, Twój wynik wynosi $35$.
   • W przeciwnym razie Twój wynik wynosi $0$.

Zauważ, że Twój wynik dla każdego podzadania jest minimalnym wynikiem spośród wszystkich rezultatów testów w danym podzadaniu.

Uwagi

Operacja xor to bitowa alternatywa wykluczająca (XOR).

Niech ukryty ciąg $a$ będzie równy $[1, 5, 6, 3]$. Sprawdzarka wywołuje funkcję. Przykład interakcji znajduje się poniżej:

Przykładowa sprawdzarka odczytuje wejście w następującym formacie: Linia 1: $n$ Linia 2: $a_1, a_2, \dots, a_n$

MOŻESZ POBRAĆ xoractive.zip z systemu, który zawiera przykłady dla języków Java, C++11, FPC, Python 2.

Wszystkie przykłady wywoływania funkcji znajdują się powyżej. Dla języka Python 2 musisz zaimplementować funkcję def guess(n, interactor), gdzie interactor jest instancją testowanej klasy. Funkcje ask oraz get_pairwise_xor są metodami tej klasy.

Plik xoractive.zip zawiera przykładowe rozwiązania dla każdego języka.

Dla rozwiązań w języku Java, plik i klasa muszą nazywać się odpowiednio Xoractive.java oraz Xoractive.

Dla rozwiązań w języku Pascal, plik musi nazywać się xoractive.pas.