Codeforces Round 367 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

bitmasks

data structures

trees

*1800

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Vasiliy's Multiset

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAuthor has gone out of the stories about Vasiliy, so here is just a formal task description.

You are given *q* queries and a multiset *A*, initially containing only integer 0. There are three types of queries:

- "+ x" — add integer
*x*to multiset*A*. - "- x" — erase one occurrence of integer
*x*from multiset*A*. It's guaranteed that at least one*x*is present in the multiset*A*before this query. - "? x" — you are given integer
*x*and need to compute the value , i.e. the maximum value of bitwise exclusive OR (also know as XOR) of integer*x*and some integer*y*from the multiset*A*.

Multiset is a set, where equal elements are allowed.

Input

The first line of the input contains a single integer *q* (1 ≤ *q* ≤ 200 000) — the number of queries Vasiliy has to perform.

Each of the following *q* lines of the input contains one of three characters '+', '-' or '?' and an integer *x*_{i} (1 ≤ *x*_{i} ≤ 10^{9}). It's guaranteed that there is at least one query of the third type.

Note, that the integer 0 will always be present in the set *A*.

Output

For each query of the type '?' print one integer — the maximum value of bitwise exclusive OR (XOR) of integer *x*_{i} and some integer from the multiset *A*.

Example

Input

10

+ 8

+ 9

+ 11

+ 6

+ 1

? 3

- 8

? 3

? 8

? 11

Output

11

10

14

13

Note

After first five operations multiset *A* contains integers 0, 8, 9, 11, 6 and 1.

The answer for the sixth query is integer — maximum among integers , , , and .

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/09/2023 01:13:26 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|