AT_tkppc2016_i.ボス（Boss）

joisino姐姐的下一个工作是调整Boss战的难度。
这个Boss的身体由像格子一样排列的细胞组成，从最左上角的细胞向右移动 $x$，向下移动 $y$ 的位置的细胞用坐标 $(x, y)$ 表示。
在与Boss的战斗过程中，将会发生 $N$ 次事件。事件分为以下三种类型之一：

1. 事件 1

   • 给定整数 $L, R$。假设这是第 $K$ 次事件 1，则 $y$ 坐标为 $K-1$，$x$ 坐标在 $L$ 到 $R$ 之间的细胞会被弱体化。

2. 事件 2

   • 给定整数 $K$，表示解除 $y$ 坐标为 $K$ 的细胞的弱体化。保证此时 $y$ 坐标为 $K$ 的细胞中一定存在被弱体化的细胞。

3. 事件 3

   • 给定整数 $L, R$，你有一次攻击Boss的机会。
   • 你可以选择一个存在弱体化部分的 $y$ 坐标 $K$，假设该 $y$ 坐标下弱体化的细胞区间为 $x$ 坐标 $A$ 到 $B$，仅当 $A < L$ 且 $R < B$ 时，才能对该部分进行攻击。
   • 攻击时，可以对Boss造成 $(L-A) \times (B-R)$ 的伤害。

为了调整难度，需要事先知道在所有事件 3 中，对Boss能够造成的最大伤害。
joisino姐姐的任务是编写一个程序，求出每次事件 3 能对Boss造成的最大伤害。

输入通过标准输入给出。

• 第 1 行输入一个整数 $N$，表示接下来将发生的事件数 $N$（$1 \leq N \leq 2 \times 10^5$）。
• 接下来的 $N$ 行中，第 $i$ 行描述第 $i$ 个事件的信息。
• 每行的开头是一个整数 $T_i$（$1 \leq T_i \leq 3$），表示事件的类型。
• 若 $T_i = 1$，则接下来有两个整数 $L_i$（$0 \leq L_i \leq 10^9$）、$R_i$（$L_i \leq R_i \leq 10^9$），表示这是第 $K$ 次事件 1，则 $y$ 坐标为 $K-1$，$x$ 坐标在 $L_i$ 到 $R_i$ 之间的细胞被弱体化。
• 若 $T_i = 2$，则接下来有一个整数 $K_i$，表示解除 $y$ 坐标为 $K_i$ 的细胞的弱体化。
• 若 $T_i = 3$，则接下来有两个整数 $L_i$（$0 \leq L_i \leq 10^9$）、$R_i$（$L_i \leq R_i \leq 10^9$），表示你有一次攻击Boss的机会。

对于每一次事件 3，输出能够对Boss造成的最大伤害，输出一行。
如果没有任何 $y$ 坐标可以进行攻击，则输出 $-1$。

配分

本题设有部分分。

• 数据集 1 满足 $N(1 \leq N \leq 3 \times 10^3)$，全部正确可得 5 分。
• 数据集 2 无额外限制，全部正确可得 155 分。

样例解释 1

1. 前两次事件的弱体化后，Boss 的状态如下图所示（红色部分为弱体化区域）。
   
2. 下一次攻击机会时，攻击 $y$ 坐标 $0$，可以造成 $(5-0) \times (10-5) = 25$ 的伤害。
3. 下一次攻击机会时，攻击 $y$ 坐标 $1$，可以造成 $(8-2) \times (12-9) = 18$ 的伤害。
4. 下一次弱体化解除后，Boss 的状态如下图所示。
   
5. 下一次攻击机会时，攻击 $y$ 坐标 $1$，可以造成 $(5-2) \times (12-5) = 21$ 的伤害。
6. 下一次攻击机会时，攻击 $y$ 坐标 $1$，可以造成 $(8-2) \times (12-9) = 18$ 的伤害。
7. 下一次弱体化解除后，Boss 的状态如下图所示。
   
8. 下一次攻击机会时，没有可以攻击的 $y$ 坐标，因此输出 $-1$。

由 ChatGPT 4.1 翻译