题目描述

用 $(a,b,c,d)$ 表示左下角在 $(a,b)$ ,右上角在 $(c,d)$ 的矩形。

支持三种操作：

I x1 y1 x2 y2：插入矩形 $(x1,y1,x2,y2)$ 。

D x：删除第 $x$ 个 $I$ 操作时插入的矩形（保证不会多次删除同一个矩形）。

Q x1 y1 x2 y2：求有多少矩形，与 $(x1,y1,x2,y2)$ 至少有一个公共点。

$1 \leq x1 \leq x2 \leq 10^9$

$1 \leq y1 \leq y2 \leq 10^9$

试题来源: CodeChef QRECT

输入格式

输入数据的第一行包含一个整数 $Q$，表示操作的总数。

接下来的 $Q$ 行，每行包含一个操作。

输出格式

对于每个询问操作，输出一行表示对应的答案。

5
I 1 1 2 2
I 2 2 3 3
Q 3 3 4 4
D 2
Q 3 3 4 4

1
0

7
I 1 1 2 2
I 3 3 4 4
D 2
I 5 5 6 6
I 7 7 8 8
D 3
Q 7 7 8 8

1

数据范围与提示

$30\%$ 的数据，$Q \leq 1000$ 。

$30\%$ 的数据，$Q \leq 100000$，无删除操作。

$40\%$ 的数据，$Q \leq 100000$ 。