No tag edit access

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-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/24/2019 04:34:39 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|