Problem Description

Joisino's next job is to adjust the difficulty of a boss battle.
The boss's body is arranged like a grid of cells, and the cell located $ x $ steps to the right and $ y $ steps down from the top-left cell is represented by the coordinate $ (x,y) $.
During the battle with this boss, $ N $ events will occur. These events are one of the following three types:

1. Event 1

   1. Two integers $ L, R $ are given. If this is the $ K $-th Event 1, then the cells with $ y $ coordinate $ K-1 $ and $ x $ coordinates from $ L $ to $ R $ will weaken.

2. Event 2

   1. An integer $ K $ is given, and the weakening of cells with $ y $ coordinate $ K $ is canceled. It is guaranteed that there are weakened cells at $ y $ coordinate $ K $.

3. Event 3

   1. Two integers $ L, R $ are given, providing you with a chance to attack the boss.
   2. You choose a weakened $ y $ coordinate $ K $, and if the weakened cells there are from $ x $ coordinate $ A $ to $ B $, then you can attack this part only if $ A < L $ and $ R < B $.
   3. Upon attacking, you can deal $(L-A) \times (B-R)$ damage to the boss.

For difficulty adjustment, Joisino wants to know the maximum damage that can be dealt to the boss in all Event 3s in advance.
Joisino's task is to write a program that calculates the maximum damage that can be dealt to the boss in all Event 3s.

Input Format

Input is given from standard input in the following format:

$ N $ :

• The first line contains an integer $N(1 \leq N \leq 2 \times 10^5)$, representing the number of events that will occur.
• The next $ N $ lines contain information about the $ i $-th event.
• The first integer on each line is $T_i(1 \leq T_i \leq 3)$, indicating the type of event.
• If $ T_i $ is 1, two integers $L_i(0 \leq L_i \leq 10^9), R_i(L_i \leq R_i \leq 10^9)$ follow, meaning that if this is the $ K $-th Event 1, cells with $ y $ coordinate $ K-1 $ and $ x $ coordinates from $ L_i $ to $ R_i $ will weaken.
• If $ T_i $ is 2, an integer $ K_i $ follows, meaning that the weakening of cells with $ y $ coordinate $ K_i $ is canceled.
• If $ T_i $ is 3, two integers $L_i(0 \leq L_i \leq 10^9), R_i(L_i \leq R_i \leq 10^9)$ follow, indicating a chance to attack the boss.

Output Format

For each Event 3, output the maximum damage that can be dealt to the boss in one line.
If no $ y $ coordinate can be attacked, output $ -1 $.

Sample Input and Output

Sample Input #1

9
1 0 10
1 2 12
3 5 5
3 8 9
2 0
3 5 5
3 8 9
2 1
3 5 5

Sample Output #1

25
18
21
18
-1

Sample Input #2

7
1 3 7
1 0 6
1 4 10
3 1 3
3 6 7
3 5 5
3 4 6

Sample Output #2

3
6
5
1

Sample Input #3

20
3 268323303 605806817
3 397106901 526645597
1 242167025 963419065
3 306157656 666722488
3 90905255 723611215
1 135062270 656996756
1 72048580 708895403
1 254360876 741288738
3 353173849 652094091
3 274378199 520888695
1 128877839 722596185
3 367349293 905356554
3 336742409 649201453
1 353239854 521572577
2 3
3 5185803 799351855
1 139746807 783110900
3 375190636 656724546
1 462675641 992773167
1 77055484 555060299

Sample Output #3

-1
-1
18985801177770087
-1
34559196595622576
38039325599084252
7268396812754948
29717251314463008
-1
40797612391288109

Notes/Hints

Scoring

This problem has partial scoring.

1. Dataset 1 satisfies $N(1 \leq N \leq 3 \times 10^3)$ and awards 5 points for a correct answer.
2. Dataset 2 has no additional constraints and awards 155 points for a correct answer.

见题面 Input 部分

见题面 Output 部分