Read problems statements in Mandarin Chinese and Russian as well. 

	Let's consider a set of points S. Initially, S is an empty set. Your task is to implement a data structure that can process the following queries efficiently:

			"+ X Y" - add a new point P with coordinates (X, Y) to S. It's guaranteed that this point will not be in S.
		
			"- N" - remove a point that was added during the N'th adding query from S. All of the adding queries are numbered in the order of their appearance starting from 1 (queries of other types are not included). It's guaranteed that this point is in S.
		
			"? X Y" - calculate the maximal Manhattan distance between a point P with coordinates (X, Y) and any point from S. It's guaranteed that S will not be empty.
		
	In addition, you won't be given the exact query data, but instead should decode it in the following way:

	Let's store the result of the last processed query of the third type in a variable called ANSWER. Initially, ANSWER is equal to 0. You will be given X', Y' and N' instead of the real values of X, Y and N. To get the real data you should perform the following computations:

			X = X' xor ANSWER;
		
			Y = Y' xor ANSWER;
		
			N = N' xor ANSWER.
		
	Don't forget to update the value of ANSWER after processing each query of the third type.

------ Note ------ 

	Maybe some of you aren't familiar with some terms in the statement. Here are some articles that could help you understand the problem correctly:

XOR operation: http://en.wikipedia.org/wiki/Exclusive_{or}
Manhattan distance: http://en.wikipedia.org/wiki/Taxicab_{geometry}

------ Input ------ 

	The first line of the input contains one integer Q denoting the number of queries to process.

	Each of the next Q lines contains a query to process in the format described above.

------ Output ------ 

	For each query on the third type you should output your answer on a new line.

------ Constraints ------ 

1 ≤ Q ≤ 500,000(5 × 10^{5});
0 ≤ X', Y', N'  < 2^{31} for each query;
0 ≤ X, Y ≤ 10^{9} for each query.

------ Example ------ 

Input:
10
+ 8 1
1
+ 3 9
? 8 4
? 8 8
? 12 0
+ 6 5
? 7 8
? 4 5
9

Output:
10
8
2
4
11

------ Explanations ------ 

Here's a non-encrypted version of the example:

10
+ 8 1
1
+ 3 9
? 8 4
? 2 2
? 4 8
+ 4 7
? 5 10
? 0 1
2
The answers are the same.

Source: codechef | Difficulty: VERY_HARD
Tags: Geometry

Bit manipulation

Data structures

Mathematics


Solutions:
from heapq import heappush, heappop
add = []
a = []
b = []
c = []
d = []
dela = {}
delb = {}
delc = {}
deld = {}
answer = 0
for q in range(int(input())):
	inp = list(input().split())
	if inp[0] == '+':
		x = int(inp[1]) ^ answer
		y = int(inp[2]) ^ answer
		adda = -x - y
		addb = x - y
		addc = -x + y
		addd = x + y
		add.append([adda, addb, addc, addd])
		heappush(a, -adda)
		heappush(b, -addb)
		heappush(c, -addc)
		heappush(d, -addd)
	elif inp[0] == '-':
		n = int(inp[1]) ^ answer
		deladd = add[n - 1]
		dela[deladd[0]] = dela.get(deladd[0], 0) + 1
		delb[deladd[1]] = delb.get(deladd[1], 0) + 1
		delc[deladd[2]] = delc.get(deladd[2], 0) + 1
		deld[deladd[3]] = deld.get(deladd[3], 0) + 1
	else:
		x = int(inp[1]) ^ answer
		y = int(inp[2]) ^ answer
		while dela.get(-a[0], 0):
			dela[-a[0]] -= 1
			heappop(a)
		maxa = -a[0]
		while delb.get(-b[0], 0):
			delb[-b[0]] -= 1
			heappop(b)
		maxb = -b[0]
		while delc.get(-c[0], 0):
			delc[-c[0]] -= 1
			heappop(c)
		maxc = -c[0]
		while deld.get(-d[0], 0):
			deld[-d[0]] -= 1
			heappop(d)
		maxd = -d[0]
		maxman = max(maxa + x + y, maxb + -x + y, maxc + x - y, maxd + -x - y)
		answer = maxman
		print(maxman)


from heapq import *
answer = 0
bool_dict_present = dict()
ele_number = 1
(h_1, h_2, h_3, h_4) = (list(), list(), list(), list())
for i in range(int(input().strip())):
	inp = list(input().strip().split())
	if inp[0] == '+':
		(x, y) = map(int, inp[1:])
		(x, y) = (x ^ answer, y ^ answer)
		heappush(h_1, (x + y, ele_number))
		heappush(h_2, (x - y, ele_number))
		heappush(h_3, (-x + y, ele_number))
		heappush(h_4, (-x - y, ele_number))
		bool_dict_present[ele_number] = True
		ele_number += 1
	elif inp[0] == '?':
		(x, y) = map(int, inp[1:])
		(x, y) = (x ^ answer, y ^ answer)
		while h_1 and (not bool_dict_present[h_1[0][1]]):
			heappop(h_1)
		while h_2 and (not bool_dict_present[h_2[0][1]]):
			heappop(h_2)
		while h_3 and (not bool_dict_present[h_3[0][1]]):
			heappop(h_3)
		while h_4 and (not bool_dict_present[h_4[0][1]]):
			heappop(h_4)
		answer = max(x + y - h_1[0][0], x - y - h_2[0][0], -x + y - h_3[0][0], -x - y - h_4[0][0])
		print(answer)
	else:
		n = int(inp[1])
		n = n ^ answer
		bool_dict_present[n] = False


import heapq
from sys import stdin
points = {}
count = 1
answer = 0
(h1, h2, h3, h4) = ([], [], [], [])
for _ in range(int(stdin.readline())):
	query = [i for i in stdin.readline().split()]
	if query[0] == '+':
		(x, y) = (int(query[1]) ^ answer, int(query[2]) ^ answer)
		heapq.heappush(h1, (x + y, count))
		heapq.heappush(h2, (x - y, count))
		heapq.heappush(h3, (y - x, count))
		heapq.heappush(h4, (-x - y, count))
		points[count] = True
		count += 1
	elif query[0] == '-':
		n = int(query[1]) ^ answer
		points[n] = False
	else:
		(x, y) = (int(query[1]) ^ answer, int(query[2]) ^ answer)
		while h1 and (not points[h1[0][1]]):
			heapq.heappop(h1)
		while h2 and (not points[h2[0][1]]):
			heapq.heappop(h2)
		while h3 and (not points[h3[0][1]]):
			heapq.heappop(h3)
		while h4 and (not points[h4[0][1]]):
			heapq.heappop(h4)
		result = max(x + y - h1[0][0], x - y - h2[0][0], y - x - h3[0][0], -x - y - h4[0][0])
		print(result)
		answer = result


import heapq as hq
ans = 0
i = 1
h1 = []
h2 = []
h3 = []
h4 = []
valid = {}
for _ in range(int(input())):
	ip = list(input().split())
	if ip[0] == '+':
		x = ans ^ int(ip[1])
		y = ans ^ int(ip[2])
		hq.heappush(h1, (x + y, i))
		hq.heappush(h2, (x - y, i))
		hq.heappush(h3, (-x + y, i))
		hq.heappush(h4, (-x - y, i))
		valid[i] = True
		i += 1
	elif ip[0] == '-':
		n = ans ^ int(ip[1])
		valid[n] = False
	else:
		x = ans ^ int(ip[1])
		y = ans ^ int(ip[2])
		while len(h1) > 0 and (not valid[h1[0][1]]):
			hq.heappop(h1)
		while len(h2) > 0 and (not valid[h2[0][1]]):
			hq.heappop(h2)
		while len(h3) > 0 and (not valid[h3[0][1]]):
			hq.heappop(h3)
		while len(h4) > 0 and (not valid[h4[0][1]]):
			hq.heappop(h4)
		ans = max(x + y - h1[0][0], x - y - h2[0][0], -x + y - h3[0][0], -x - y - h4[0][0])
		print(ans)


import heapq
h1 = []
h2 = []
h3 = []
h4 = []
ans = 0
m = {}
cnt = 1
for __ in range(int(input())):
	q = list(input().split())
	if q[0] == '+':
		x = ans ^ int(q[1])
		y = ans ^ int(q[2])
		heapq.heappush(h1, (x + y, cnt))
		heapq.heappush(h2, (x - y, cnt))
		heapq.heappush(h3, (-x + y, cnt))
		heapq.heappush(h4, (-x - y, cnt))
		m[cnt] = True
		cnt += 1
	elif q[0] == '-':
		n = ans ^ int(q[1])
		m[n] = False
	else:
		a = ans ^ int(q[1])
		b = ans ^ int(q[2])
		while len(h1) > 0 and m[h1[0][1]] == False:
			heapq.heappop(h1)
		while len(h2) > 0 and m[h2[0][1]] == False:
			heapq.heappop(h2)
		while len(h3) > 0 and m[h3[0][1]] == False:
			heapq.heappop(h3)
		while len(h4) > 0 and m[h4[0][1]] == False:
			heapq.heappop(h4)
		ans = max(a + b - h1[0][0], a - b - h2[0][0], -a + b - h3[0][0], -a - b - h4[0][0])
		print(ans)


from heapq import *
q = int(input())
(h1, h2, h3, h4) = ([], [], [], [])
if_present = {}
ans = 0
t = 1
while q > 0:
	en = list(input().split())
	if en[0] == '+':
		(u, v) = map(int, en[1:])
		u = u ^ ans
		v = v ^ ans
		heappush(h1, (u + v, t))
		heappush(h2, (u - v, t))
		heappush(h3, (-u + v, t))
		heappush(h4, (-u - v, t))
		if_present[t] = True
		t += 1
	elif en[0] == '?':
		(u, v) = map(int, en[1:])
		u = u ^ ans
		v = v ^ ans
		while h1 and (not if_present[h1[0][1]]):
			heappop(h1)
		while h2 and (not if_present[h2[0][1]]):
			heappop(h2)
		while h3 and (not if_present[h3[0][1]]):
			heappop(h3)
		while h4 and (not if_present[h4[0][1]]):
			heappop(h4)
		ans = max(u + v - h1[0][0], u - v - h2[0][0], -u + v - h3[0][0], -u - v - h4[0][0])
		print(ans)
	else:
		u = int(en[1])
		u = u ^ ans
		if_present[u] = False
	q -= 1


from heapq import *
res = 0
mark = dict()
bb = 1
(pq1, pq2, pq3, pq4) = ([], [], [], [])
for i in range(int(input())):
	arr = list(input().split())
	if arr[0] == '+':
		(x, y) = map(int, arr[1:])
		(x, y) = (x ^ res, y ^ res)
		heappush(pq1, (x + y, bb))
		heappush(pq2, (x - y, bb))
		heappush(pq3, (-x + y, bb))
		heappush(pq4, (-x - y, bb))
		mark[bb] = True
		bb += 1
	elif arr[0] == '?':
		(x, y) = map(int, arr[1:])
		(x, y) = (x ^ res, y ^ res)
		while pq1 and (not mark[pq1[0][1]]):
			heappop(pq1)
		while pq2 and (not mark[pq2[0][1]]):
			heappop(pq2)
		while pq3 and (not mark[pq3[0][1]]):
			heappop(pq3)
		while pq4 and (not mark[pq4[0][1]]):
			heappop(pq4)
		res = max(x + y - pq1[0][0], x - y - pq2[0][0], -x + y - pq3[0][0], -x - y - pq4[0][0])
		print(res)
	else:
		n = int(arr[1])
		n = n ^ res
		mark[n] = False


from heapq import *
n = ans = 0
(h1, h2, h3, h4) = ([], [], [], [])
deleted = set()
for _ in range(int(input())):
	query = input().split()
	if query[0] == '+':
		n += 1
		(x, y) = (ans ^ int(query[1]), ans ^ int(query[2]))
		heappush(h1, (-(x + y), n))
		heappush(h2, (-(x - y), n))
		heappush(h3, (-(-x + y), n))
		heappush(h4, (-(-x - y), n))
	elif query[0] == '-':
		deleted.add(ans ^ int(query[1]))
	else:
		(x, y) = (ans ^ int(query[1]), ans ^ int(query[2]))
		while h1[0][1] in deleted:
			heappop(h1)
		while h2[0][1] in deleted:
			heappop(h2)
		while h3[0][1] in deleted:
			heappop(h3)
		while h4[0][1] in deleted:
			heappop(h4)
		(f1, f2, f3, f4) = (x + y, x - y, -x + y, -x - y)
		ans = max(-h1[0][0] - f1, -h2[0][0] - f2, -h3[0][0] - f3, -h4[0][0] - f4)
		print(ans)