Before attending the Pre-SDOI Training Camp (also known as Public Easy Round #2) hosted by country P, your teammate asked you this simple data structure problem:

Maintain two multisets of integer pairs $U$ and $V$, initially empty. Define

$$ 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} $$

Perform $Q$ modifications of one of the following two types:

• $\texttt{1 s x y}$: Add $(x,y)$ to a set. If $s=1$, add to $U$; otherwise, add to $V$.
• $\texttt{2 s x y}$: Remove one instance of $(x,y)$ from a set. If $s=1$, remove from $U$; otherwise, remove from $V$. It is guaranteed that at least one $(x,y)$ exists in the corresponding set at that moment.

To prove that you have fully mastered simple data structure problems, you need to find the value of $D(U,V)$ after each modification.

Input

The first line contains a positive integer $Q$.

The following $Q$ lines each contain a modification, with the format described above.

Output

$Q$ lines, each containing an integer, where the $i$-th integer represents the value of $D(U,V)$ after the $i$-th modification.

Examples

Input 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

Output 1

-1
230
230
300
270
-1

Constraints

For all data, $1 \le Q \le 2.5\cdot 10^5$, $s\in\{1,2\}$, $0\le x,y\le 2.5\cdot 10^5$.