有两个多重集 $U$ 和 $V$，其中包含具有整数坐标的二维点。 我们为一对多重集定义如下函数 $D(U, V)$：

• 若任一集合为空，则 $D(U, V) = -1$。
• 否则，$D(U, V) = \min_{\substack{(u_x, u_y) \in U \\ (v_x, v_y) \in V}} \max(u_x + v_x, u_y + v_y)$。

最初，$U$ 和 $V$ 均为空。处理 $Q$ 个如下形式的查询：

• “1 $s$ $x$ $y$”：向其中一个集合添加一个点 $(x, y)$。若 $s = 1$，则将点添加到 $U$ 中。否则，将点添加到 $V$ 中。
• “2 $s$ $x$ $y$”：从其中一个集合中删除一个点 $(x, y)$。若 $s = 1$，则从 $U$ 中删除该点。否则，从 $V$ 中删除该点。

删除点时，如果给定坐标处存在多个点，则仅删除其中一个。保证在每次删除时，该点在对应的多重集中一定存在。 你的任务是处理这些查询。在每次查询后，输出 $D(U, V)$ 的值。

输入格式

第一行包含一个整数 $Q$ ($1 \le Q \le 250\,000$)。 接下来的 $Q$ 行，每行包含一个上述形式的查询。两种查询的约束条件均为：$s \in \{1, 2\}$，$0 \le x, y \le 250\,000$。

输出格式

输出 $Q$ 行。每行应包含对应查询后的 $D(U, V)$ 值。

样例

输入 1

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

输出 1

-1
230
230
300
270
-1