Most Distant Points

All submissions for this problem are available.
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 nonencrypted 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.
Author:  kostya_by 
Editorial  http://discuss.codechef.com/problems/MOSTDIST 
Tags  cook52, easy, geometry, heap, kostya_by, manhattan 
Date Added:  24102014 
Time Limit:  1.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 