Олимпиадный тренинг

Задача . D. Мультимножество Василия

Задача

Темы: Бинарный поиск битмаски Деревья Структуры данных *1800

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

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

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

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

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

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

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

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

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

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

Примечание

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

Ответом на шестой запрос будет число $\text{[math]}$ — максимальное из чисел $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ и $\text{[math]}$ .