406422: GYM102399 F XOR шифрование

F. XOR шифрованиеограничение по времени на тест2 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Алиса и Боб в очередной раз решают важные криптографические вопросы. На этот раз они хотят научиться передавать информацию, вызывая как можно меньше подозрений о её зашифрованности.

Канал, по которому Алиса и Боб обмениваются информацией, прослушивает Ева. Алиса может прислать Бобу некоторое множество $$$A$$$ целых неотрицательных чисел. Если для некоторого достаточно большого $$$t \geq 0$$$ все числа $$$0, 1, 2, \ldots, t$$$ лежат в множестве $$$A$$$, то это повышает подозрения Евы о том, что переданная информация была зашифрована перед отправкой. Поэтому передавая некоторое множество $$$A$$$ целых чисел, Алиса хочет минимизировать минимальное целое неотрицательное число, которое не принадлежит множеству $$$A$$$, назовем это число тревожностью Евы.

Для того, чтобы шифровать информацию, Алиса с Бобом придумали такую простую схему: пусть Алиса хочет передать Бобу множество $$$A = \{a_1, a_2, \ldots, a_n\}$$$ целых неотрицательных чисел. Алиса может выбрать некоторое целое число $$$x$$$ ($$$0 \leq x \leq k$$$) и передать Бобу множество $$$\{a_1 \oplus x, a_2 \oplus x, \ldots, a_n \oplus x\}$$$, где значок $$$\oplus$$$ обозначает операцию взятия побитового исключающего ИЛИ двух чисел. При этом о значении числа $$$k$$$ они договорились заранее. Таким образом, Алиса хочет сделать свой выбор так, чтобы тревожность Евы, а именно минимальное целое неотрицательное число, не принадлежащее множеству $$$\{a_1 \oplus x, a_2 \oplus x, \ldots, a_n \oplus x\}$$$, было как можно меньше.

Алиса еще не выбрала, какое конкретно множество $$$A$$$ она хочет передать Бобу. Изначально она хочет передать Бобу пустое множество $$$A = \varnothing$$$. После этого Алиса $$$q$$$ раз принимает решение о том, что хочет добавить или удалить из текущего множества $$$A$$$ некоторое число. И после каждой такой операции она хотела бы знать минимальную возможную тревожность Евы, которой Алиса может добиться, если она захочет передать Бобу текущее множество. Помогите ей и напишите программу, которая будет вычислять это значение.

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

В первой строке находятся два целых числа $$$q$$$ и $$$k$$$ ($$$1 \leq q \leq 200\,000, 0 \leq k < 2^{20}$$$) — количество изменений множества Алисы и верхнее ограничение на $$$x$$$, которое может выбирать Алиса.

В следующих $$$q$$$ строках находится по два целых числа, разделенных пробелом, в $$$i$$$-й строке находятся $$$type_i$$$, $$$x_i$$$ ($$$type_i \in \{1, 2\}, 0 \leq x_i < 2^{20}$$$). Если $$$type_i = 1$$$, это означает, что в $$$i$$$-м изменении Алиса хочет добавить $$$x_i$$$ в множество $$$A$$$, которое она сейчас собирается отправлять Бобу, если $$$type_i = 2$$$, это означает, что в $$$i$$$-м изменении Алиса хочет удалить $$$x_i$$$ из множества $$$A$$$, которое она сейчас собирается отправлять Бобу. Гарантируется, что если $$$type_i = 1$$$, то числа $$$x_i$$$ нет в текущем множестве $$$A$$$, если $$$type_i = 2$$$, то число $$$x_i$$$ есть в текущем множестве $$$A$$$.

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

Выведите $$$q$$$ строк, в $$$i$$$-й строке ($$$1 \leq i \leq q$$$) выведите минимально возможное значение тревожности Евы, которого может добиться Алиса, когда будет пересылать множество $$$A$$$, которое получается у нее после первых $$$i$$$ изменений.

ПримерыВходные данные

8 2
1 1
1 0
1 2
2 1
1 3
1 1
1 4
2 3

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

0
0
1
0
0
4
4
1

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

5 1
1 2
1 1
1 3
2 2
1 0

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

0
0
0
0
2

Примечание

Рассмотрим первый пример.

После первого запроса $$$A = \{1\}$$$. Тогда, выбрав $$$x = 0$$$, можно получить множество $$$\{1 \oplus 0\} = \{1\}$$$. Минимальное неотрицательное целое число, не лежащее в этом множестве, равно $$$0$$$.

После второго запроса $$$A = \{0, 1\}$$$. Тогда, выбрав $$$x = 2$$$, можно получить множество $$$\{0 \oplus 2, 1 \oplus 2\} = \{2, 3\}$$$. Минимальное неотрицательное целое число, не лежащее в этом множестве, равно $$$0$$$.

После третьего запроса $$$A = \{0, 1, 2\}$$$. Тогда, выбрав $$$x = 2$$$, можно получить множество $$$\{0 \oplus 2, 1 \oplus 2, 2 \oplus 2\} = \{0, 2, 3\}$$$. Минимальное неотрицательное целое число, не лежащее в этом множестве, равно $$$1$$$.

После четвёртого запроса $$$A = \{0, 2\}$$$. Тогда, выбрав $$$x = 1$$$, можно получить множество $$$\{0 \oplus 1, 2 \oplus 1\} = \{1, 3\}$$$. Минимальное неотрицательное целое число, не лежащее в этом множестве, равно $$$0$$$.

После пятого запроса $$$A = \{0, 2, 3\}$$$. Тогда, выбрав $$$x = 1$$$, можно получить множество $$$\{0 \oplus 1, 2 \oplus 1, 3 \oplus 1\} = \{1, 2, 3\}$$$. Минимальное неотрицательное целое число, не лежащее в этом множестве, равно $$$0$$$.

После шестого запроса $$$A = \{0, 1, 2, 3\}$$$. Тогда, выбрав $$$x = 0$$$, можно получить множество $$$\{0 \oplus 0, 1 \oplus 0, 2 \oplus 0, 3 \oplus 0\} = \{0, 1, 2, 3\}$$$. Минимальное неотрицательное целое число, не лежащее в этом множестве, равно $$$4$$$.

После седьмого запроса $$$A = \{0, 1, 2, 3, 4\}$$$. Тогда, выбрав $$$x = 1$$$, можно получить множество $$$\{0 \oplus 1, 1 \oplus 1, 2 \oplus 1, 3 \oplus 1, 4 \oplus 1\} = \{0, 1, 2, 3, 5\}$$$. Минимальное неотрицательное целое число, не лежащее в этом множестве, равно $$$4$$$.

После восьмого запроса $$$A = \{0, 1, 2, 4\}$$$. Тогда, выбрав $$$x = 2$$$, можно получить множество $$$\{0 \oplus 2, 1 \oplus 2, 2 \oplus 2, 4 \oplus 2\} = \{0, 2, 3, 6\}$$$. Минимальное неотрицательное целое число, не лежащее в этом множестве, равно $$$1$$$.