AT_tkppc2016_i ボス（Boss）

[problemUrl]: https://atcoder.jp/contests/tkppc2/tasks/tkppc2016_i joisinoお姉ちゃんの次の仕事は、ボス戦の難易度調整である。 このボスの体は、細胞がマス目のように並んでおり、最も左上の細胞から右に$ x $,下に$ y $進んだ位置にある細胞は、座標$ (x,y) $で表される。 このボスとの戦いの最中に、$ N $回のイベントが起こる。イベントは以下の$ 3 $種類のうちいずれかである 2. イベント$ 1 $ > 1. ある整数$ L,R $が与えられる。これが$ K $回目のイベント$ 1 $だとすると、$ y $座標が$ K-1 $で、$ x $座標が$ L $から$ R $までの間にある細胞が弱体化する。 4. イベント$ 2 $ > 1. ある整数$ K $が与えられ、$ y $座標$ K $の細胞の弱体化が解除される。この時、必ず$ y $座標$ K $に、弱体化している細胞があることが保証される。 6. イベント$ 3 $ > 1. ある整数$ L,R $が与えられ、あなたには、ボスへの攻撃のチャンスが一回与えられる。 > 2. 弱体化した部分のある$ y $座標$ K $を選び、そこにある弱体化した細胞が、$ x $座標$ A $から$ B $までだったとすると、$ A＜L $かつ$ R＜B $のときのみ、この部分に対して攻撃が行える。 > 3. そして攻撃を行うと、$ (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) $が与えられ、ボスへの攻撃のチャンスが一回あることを意味する。

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

### 配点 この問題には部分点が設定されている。 3. データセット$ 1 $は、$ N(1≦N≦3×10^3) $を満たし、正解すると$ 5 $点が得られる。 4. データセット$ 2 $では追加の制約はなく、正解すると$ 155 $点が得られる。 ### Sample Explanation 1 1\. 最初の$ 2 $回のイベントでの弱体化のあと、ボスの状態は下の図のようになっている（弱体化した部分は赤で表されている）。 !\[\](/img/other/tsukukoma2016/bgagbhgtioi/I\_pic1.png) 3. 次のイベントの攻撃のチャンスでは、$ y $座標$ 0 $を攻撃すると、$ (5-0)×(10-5)=25 $のダメージが与えられる。 4. 次のイベントの攻撃のチャンスでは、$ y $座標$ 1 $を攻撃すると、$ (8-2)×(12-9)=18 $のダメージが与えられる。 5. 次のイベントの弱体化解除で、ボスの状態は下の図のようになる。 !\[\](/img/other/tsukukoma2016/bgagbhgtioi/I\_pic2.png) 7. 次のイベントの攻撃のチャンスでは、$ y $座標$ 1 $を攻撃すると、$ (5-2)×(12-5)=21 $のダメージが与えられる。 8. 次のイベントの攻撃のチャンスでは、$ y $座標$ 1 $を攻撃すると、$ (8-2)×(12-9)=18 $のダメージが与えられる。 9. 次のイベントの弱体化解除で、ボスの状態は下の図のようになる。 !\[\](/img/other/tsukukoma2016/bgagbhgtioi/I\_pic3.png) 11. 次のイベントの攻撃のチャンスでは、攻撃できる$ y $座標がないため、$ -1 $を出力する。