Public Judge

pjudge

Time Limit: 2 s Memory Limit: 2048 MB Total points: 100 Hackable ✓
统计

在参加 P 国主办的 Pre-SDOI Training Camp(也被称作 Public Easy Round #2)前,你的队友问了你一道这样的简单数据结构题

维护两个整数二元组的多重集合 $U,V$,初始为空,定义

$$ D(U,V):=\begin{cases}-1,&U=\varnothing\lor V=\varnothing, \\ \min\{\max(u_x+v_x,u_y+v_y):(u_x,u_y)\in U,(v_x,v_y)\in V\},&\text{otherwise}.\end{cases} $$

进行如下两种类型之一的 $Q$ 次修改:

  • $\texttt{1 s x y}$:加入 $(x,y)$ 到某个集合。若 $s=1$ 则是 $U$,否则是 $V$。
  • $\texttt{2 s x y}$:从某个集合删除 $(x,y)$,若有多个则删除其中一个。若 $s=1$ 则是 $U$,否则是 $V$。保证当前时刻对应集合存在至少一个 $(x,y)$。

为了证明你已经完全掌握了简单数据结构题,你需要求出每次修改之后 $D(U,V)$ 的值。

输入格式

第一行,一个正整数 $Q$。

之后 $Q$ 行,每行一次修改,格式见题目描述。

输出格式

$Q$ 行,每行一个整数,第 $i$ 个整数表示第 $i$ 次修改之后 $D(U,V)$ 的值。

样例

input

6
1 1 100 100
1 2 30 130
1 1 120 170
2 1 100 100
1 2 70 100
2 1 120 170

output

-1
230
230
300
270
-1

数据范围

对于所有数据,$1 \le Q \le 2.5\cdot 10^5$,$s\in\{1,2\}$,$0\le x,y\le 2.5\cdot 10^5$。

子任务编号 追加限制 分数
$1$ $Q \leq 10\,000$ $5$
$2$ $Q \leq 10^5$ $35$
$3$ $ $ $60$