A. Points
time limit per test
4 s
memory limit per test
1024 mebibytes
input
standard input
output
standard output

There are two multisets $$$U$$$ and $$$V$$$ that contain two-dimensional points with integer coordinates.

We will define the following function $$$D(U, V)$$$ for a pair of multisets:

  • $$$D(U, V) = -1$$$ if either set is empty.
  • $$$D(U, V) = \min\limits_{\begin{smallmatrix}(u_x, u_y) \in U \\ (v_x, v_y) \in V\end{smallmatrix}}\max(u_x + v_x, u_y + v_y)$$$ otherwise.

In the beginning, both $$$U$$$ and $$$V$$$ are empty. Process $$$Q$$$ queries of the following form:

  • "1 $$$s$$$ $$$x$$$ $$$y$$$": Add a point $$$(x, y)$$$ to one of the sets. If $$$s = 1$$$, add the point to $$$U$$$. Otherwise, add the point to $$$V$$$.
  • "2 $$$s$$$ $$$x$$$ $$$y$$$": Delete a point $$$(x, y)$$$ from one of the sets. If $$$s = 1$$$, delete the point from $$$U$$$. Otherwise, delete the point from $$$V$$$.

When deleting a point, if there are multiple points at the given coordinates, you should delete only one of them. It is guaranteed that the given point exists in the given multiset at the time of each deletion.

Your task is to process the queries. After each query, print the value $$$D(U, V)$$$.

Input

The first line contains a single integer $$$Q$$$ ($$$1 \le Q \le 250\,000$$$).

Each of the next $$$Q$$$ lines contains a query in the form described above. Constraints for both types of queries: $$$s \in \{1, 2\}$$$, $$$0 \le x, y \le 250\,000$$$.

Output

Output $$$Q$$$ lines. Each line should contain the value $$$D(U, V)$$$ after the corresponding query.

Example
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