Айдос придумал головоломку и предложил Темирулану решить её. Он выбрал последовательность $a$ из $n$ различных неотрицательных целых чисел, пронумерованных от $1$ до $n$: $a_1, a_2, \dots, a_n$.

Темирулан может задавать два типа вопросов:

• ask — узнать число на позиции $i$ в данной последовательности.
• get_pairwise_xor — для заданной последовательности различных индексов $i_1, i_2, \dots, i_k$ получить набор попарных значений исключающего ИЛИ (XOR) для элементов последовательности $a$ с индексами $i_1, i_2, \dots, i_k$, то есть $\{a_{i_x} \oplus a_{i_y} \mid 1 \le x, y \le k\}$.

Например, предположим, что Айдос выбрал последовательность $[1, 5, 6, 3]$. Тогда на вопрос ask(2) Айдос ответит числом $5$, а на вопрос get_pairwise_xor({3, 4}) Айдос ответит последовательностью $[0, 0, 5, 5]$, так как:

• $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$

Темирулан не справился с головоломкой, и ваша задача — помочь ему. Найдите скрытую последовательность, используя описанные выше вопросы.

Реализация

Ваша задача — реализовать функцию int[] guess(int n).

• $n$: длина скрытой последовательности.
• Функция вызывается ровно один раз для каждого теста.
• Функция должна вернуть скрытую последовательность в исходном порядке.

Ваша функция может вызывать следующие функции:

1. int ask(int i)

   • $i$: индекс числа в последовательности, $1 \le i \le n$.
   • Функция возвращает $i$-е число скрытой последовательности.

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

   • $pos$: непустой список индексов последовательности.
   • Все элементы в $pos$ должны быть различными целыми числами.
   • Пусть $k$ — количество элементов в $pos$. Тогда $1 \le pos_i \le n$ для каждого $1 \le i \le k$.
   • Функция возвращает отсортированный список из $k^2$ элементов: набор попарных значений XOR, $\{a_{pos_x} \oplus a_{pos_y} \mid 1 \le x, y \le k\}$.

Вы можете вызвать обе функции в сумме не более $200$ раз для каждого теста. Если любое из вышеперечисленных условий нарушено, ваша программа получит вердикт Wrong Answer. В противном случае ваша программа получит вердикт Accepted, а ваш балл будет рассчитан на основе общего количества вызовов функций ask и get_pairwise_xor (см. раздел «Подзадачи»).

Подзадачи

• $2 \le n \le 100$
• $0 \le a_i \le 10^9$ для каждого $1 \le i \le n$.

В этой задаче проверяющая система НЕ является адаптивной. Это означает, что последовательность $a$ фиксируется в начале работы проверяющей системы и не зависит от вызовов вашей программы.

1. (6 баллов) $n \le 4$

2. (94 балла) Без дополнительных ограничений. Для этой подзадачи ваш балл рассчитывается следующим образом. Пусть $q$ — общее количество вызовов функций ask и get_pairwise_xor.

   • Если $q \le 15$, ваш балл равен $94$.
   • Если $15 < q \le 40$, ваш балл равен $84 - 2(q - 16)$.
   • Если $40 < q \le 50$, ваш балл равен $35$.
   • В противном случае ваш балл равен $0$.

Обратите внимание, что ваш балл за каждую подзадачу — это минимальный балл среди всех результатов на тестах соответствующей подзадачи.

Примеры

Входные данные 1

ask(2)
get_pairwise_xor({1, 2, 3})
ask(3)
get_pairwise_xor({4, 2})
get_pairwise_xor({2})

Выходные данные 1

5
{0, 0, 0, 3, 3, 4, 4, 7, 7}
6
{0, 0, 6, 6}
{0}

Примечание

Операция $xor$ — это побитовое исключающее ИЛИ.

Пример проверяющей системы считывает входные данные в следующем формате: Строка 1: $n$ Строка 2: $a_1, a_2, \dots, a_n$

В системе можно скачать архив xoractive.zip, который содержит примеры для языков Java, C++11, FPC, Python 2.

Для Python 2 вам необходимо реализовать функцию def guess(n, interactor), где interactor — это экземпляр тестируемого класса. Функции ask и get_pairwise_xor являются методами этого класса.

Для решений на языке Java имя файла и имя класса должны быть Xoractive.java и Xoractive соответственно.

Для решений на языке Pascal файл должен называться xoractive.pas.