D. Мультимножество Василия
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У автора уже закончились истории про Василия, поэтому он просто написал формальную постановку задачи.

У вас есть q запросов и мультимножество A, изначально содержащее только число 0. Запросы бывают трёх видов:

  1. «+ x» —добавить в мультимножество A число x.
  2. «- x» —удалить одно вхождение числа x из мультимножества A. Гарантируется, что хотя бы одно число x в этот момент присутствует в мультимножестве.
  3. «? x» —вам даётся число x, требуется вычислить , то есть максимальное значение побитового исключающего ИЛИ (также известно как XOR) числа x и какого-нибудь числа y из мультимножества A.

Мультимножество — это множество, в котором разрешается несколько одинаковых элементов.

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

В первой строке входных данных содержится число q (1 ≤ q ≤ 200 000) — количество запросов, которые требуется обработать Василию.

Каждая из последующих q строк входных данных содержит один трёх символов «+», «-» или «?» и число xi (1 ≤ xi ≤ 109). Гарантируется, что во входных данных встречается хотя бы один запрос «?».

Обратите внимание, что число 0 всегда будет присутствовать в мультимножестве.

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

На каждый запрос типа «?» выведите единственное целое число — максимальное значение побитового исключающего ИЛИ для числа xi и какого-либо числа из мультимножества A.

Пример
Входные данные
10
+ 8
+ 9
+ 11
+ 6
+ 1
? 3
- 8
? 3
? 8
? 11
Выходные данные
11
10
14
13
Примечание

После первых пяти операций в мультимножестве A содержатся числа 0, 8, 9, 11, 6 и 1.

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