У вас есть q запросов и мультимножество A, изначально содержащее только число 0. Запросы бывают трёх видов:
- + x — добавить в мультимножество A число x.
- - x — удалить одно вхождение числа x из мультимножества A. Гарантируется, что хотя бы одно число x в этот момент присутствует в мультимножестве.
- ? x — вам даётся число x, требуется вычислить максимальное значение побитового исключающего ИЛИ (также известно как XOR) числа x и какого-нибудь числа y из мультимножества A.
Мультимножество — это множество, в котором разрешается несколько одинаковых элементов.
Входные данные:
В первой строке входных данных содержится число q (1 ≤ q ≤ 200000) — количество запросов, которые требуется обработать Василию.
Каждая из последующих q строк входных данных содержит один трёх символов «+», «-» или «?» и число x
i (1 ≤ x
i ≤ 10
9). Гарантируется, что во входных данных встречается хотя бы один запрос «?».
Обратите внимание, что число 0 всегда будет присутствовать в мультимножестве.
Выходные данные:
На каждый запрос типа «?» выведите единственное целое число — максимальное значение побитового исключающего ИЛИ для числа x
i и какого-либо числа из мультимножества A.
Пример:
| Входные данные |
Выходные данные |
10
+ 8
+ 9
+ 11
+ 6
+ 1
? 3
- 8
? 3
? 8
? 11 |
11
10
14
13 |