409537: GYM103627 A Points

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)$$$.

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 $$$Q$$$ lines. Each line should contain the value $$$D(U, V)$$$ after the corresponding query.

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
230
230
300
270
-1