在参加 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$。