I - ボス（Boss） Editorial /

Time Limit: 2.5 sec / Memory Limit: 256 MB

問題文

joisinoお姉ちゃんの次の仕事は、ボス戦の難易度調整である。
このボスの体は、細胞がマス目のように並んでおり、最も左上の細胞から右にx,下にy進んだ位置にある細胞は、座標(x,y)で表される。
このボスとの戦いの最中に、N回のイベントが起こる。イベントは以下の3種類のうちいずれかである

  • イベント1
  • ある整数L,Rが与えられる。これがK回目のイベント1だとすると、y座標がK-1で、x座標がLからRまでの間にある細胞が弱体化する。
  • イベント2
  • ある整数Kが与えられ、y座標Kの細胞の弱体化が解除される。この時、必ずy座標Kに、弱体化している細胞があることが保証される。
  • イベント3
  • ある整数L,Rが与えられ、あなたには、ボスへの攻撃のチャンスが一回与えられる。
  • 弱体化した部分のあるy座標Kを選び、そこにある弱体化した細胞が、x座標AからBまでだったとすると、A＜LかつR＜Bのときのみ、この部分に対して攻撃が行える。
  • そして攻撃を行うと、(L-A)×(B-R)のダメージをボスに与えることができる。

    • 難易度調節のために、すべてのイベント3において、ボスに与えることのできる最大ダメージをあらかじめ知っておきたい。
    joisinoお姉ちゃんの仕事は、すべてのイベント3において、ボスに与えることのできる最大ダメージを求めるプログラムを作ることである。

    入力

    入力は以下の形式で標準入力から与えられる。

    N
:
    • 1行目には、これから起こるイベントの数を表す整数N(1 ≦ N ≦ 2×10^5)が与えられる。
    • 続くN行のうちi行目には、i番目に起こるイベントの情報が書かれている。
    • 各行の先頭には、イベントの種類を表す整数T_i(1≦T_i≦3)が与えられる。
    • T_iが1のとき、その後に整数L_i(0≦L_i≦10^9),R_i(L_i≦R_i≦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≦L_i≦10^9),R_i(L_i≦R_i≦10^9)が与えられ、ボスへの攻撃のチャンスが一回あることを意味する。

    配点

    この問題には部分点が設定されている。

  • データセット1は、N(1≦N≦3×10^3)を満たし、正解すると5点が得られる。
  • データセット2では追加の制約はなく、正解すると155点が得られる。

    • 出力

    すべてのイベント3について、ボスに与えることのできる最大ダメージを1行に出力せよ。
    もし、どのy座標に対しても攻撃できない場合は、-1を出力せよ。

    入力例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

    出力例1

    25
18
21
18
-1

  • 最初の2回のイベントでの弱体化のあと、ボスの状態は下の図のようになっている（弱体化した部分は赤で表されている）。
  • 次のイベントの攻撃のチャンスでは、y座標0を攻撃すると、(5-0)×(10-5)=25のダメージが与えられる。
  • 次のイベントの攻撃のチャンスでは、y座標1を攻撃すると、(8-2)×(12-9)=18のダメージが与えられる。
  • 次のイベントの弱体化解除で、ボスの状態は下の図のようになる。
  • 次のイベントの攻撃のチャンスでは、y座標1を攻撃すると、(5-2)×(12-5)=21のダメージが与えられる。
  • 次のイベントの攻撃のチャンスでは、y座標1を攻撃すると、(8-2)×(12-9)=18のダメージが与えられる。
  • 次のイベントの弱体化解除で、ボスの状態は下の図のようになる。
  • 次のイベントの攻撃のチャンスでは、攻撃できるy座標がないため、-1を出力する。

    • 入力例2

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

    出力例2

    3
6
5
1

    入力例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

    出力例3

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