Rectangle Query

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are given a Cartesian plane, and you are asked to support the following three kinds of operations:
 I x1 y1 x2 y2: add an axesparallel rectangle on the plane. The bottomleft corner has coordinates (x1, y1), the topright one has coordinates (x2, y2)
 D index: remove the retangle that was added during the indexth addition operation
 Q x1 y1 x2 y2: output the number of rectangles on the plane that have the common area with the rectangle with a bottomleft corner coordinates (x1, y1) and a topright corner coordinates (x2, y2).
Please notice that, even if the two rectangles only share a common point, they are still regarded as sharing common area
Also, there can be a few same rectangles on the plane, they should be regarded as a few different rectangles.
There are Q operations in all, can you fulfill them?
Input
The first line contains an integer Q.
The next Q lines represent the operations you are to deal with. Each of them contains an operation in one of the three forms above.
Output
For each Qtype operation, output the result on the separate line of the output.
Constraints
 1 <= Q <= 100000
 1 <= x1 <= x2 <= 10^{9}
 1 <= y1 <= y2 <= 10^{9}
Example
Input:
5
I 1 1 2 2
I 2 2 3 3
Q 3 3 4 4
D 2
Q 3 3 4 4
Output:
1
0
Explanation
In the third operation, the rectangle (2, 2)(3, 3) has a common point with the given rectangle. But in the fifth operation, as the rectangle (2, 2)(3, 3) has been removed, so there are no rectangles that has the common area with the given rectangle.
Author:  xiaodao 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/QRECT 
Tags  fenwick, hard, sept14, sqrtdecomp, xiaodao 
Date Added:  3072014 
Time Limit:  2 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. 