human
Author 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:

  1. "+ x" — add integer x to multiset A.
  2. "- 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.
  3. "? 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 xi (1 ≤ xi ≤ 109). 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 xi 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 .
The above is tricky. Write me a correct solution in PYTHON3.
 What is a Python program to print one integer — the maximum value of bitwise exclusive OR (XOR) of integer xi and some integer from the multiset A?
assistant
#Here is Python program to print one integer — the maximum value of bitwise exclusive OR (XOR) of integer xi and some integer from the multiset A.

MAX_BIT = 34
ans=[]
class Node:
    def __init__(self):
        self.left = None
        self.right = None
        self.leftCnt = 0
        self.rightCnt = 0
    
    def AddRight(self):
        if self.right == None:
            self.right = Node()
            self.rightCnt = 1
        else:
            self.rightCnt += 1
    
    def AddLeft(self):
        if self.left == None:
            self.left = Node()
            self.leftCnt = 1
        else:
            self.leftCnt += 1

    def RemRight(self):
        self.rightCnt -= 1
    
    def RemLeft(self):
        self.leftCnt -= 1

    def Left(self):
        return self.left != None and self.leftCnt > 0

    def Right(self):
        return self.right != None and self.rightCnt > 0

def insert(u, num, dig=MAX_BIT):
    if dig < 0:
        return
    
    bit = (num>>dig)&1
    if bit > 0: #insert to right
        u.AddRight()
        insert(u.right, num, dig-1)
    else:
        u.AddLeft()
        insert(u.left, num, dig-1)

def remove(u, num, dig=MAX_BIT):
    if dig < 0:
        return
    
    bit = (num>>dig)&1
    if bit > 0: #remove right
        u.RemRight()
        remove(u.right, num, dig-1)
    else:
        u.RemLeft()
        remove(u.left, num, dig-1)

def cal(u, num, dig=MAX_BIT):
    if dig < 0 or u == None:
        return 0
    
    bit = (num>>dig)&1
    if bit > 0: #try to go to left first
        if u.Left(): #if valid
            return (1<<dig) + cal(u.left, num, dig-1)
        elif u.Right():
            return cal(u.right, num, dig-1)
    else: #try to go to right first
        if u.Right():
            return (1<<dig) + cal(u.right, num, dig-1)
        elif u.Left():
            return cal(u.left, num, dig-1)
    return 0

root = Node()
insert(root, 0)

n = int(input())
for i in range(n):
    tmp = input().split()
    num = int(tmp[1])
    if tmp[0] == "+":
        insert(root, num)
    elif tmp[0] == "-":
        remove(root, num)
    else:
        ans.append(cal(root, num))
print('\n'.join(map(str, ans)))