2차원 점과 쿼리

문제

2차원 평면 위에 정수점들의 중복집합(multiset)인 $U$와 $V$가 있다.

두 중복집합 $U, V$가 주어졌을 때, 다음의 값 $D(U, V)$를 생각할 수 있다.

$D(U, V) = \min_{u \in U, v \in V} \left( \max (u_x+v_x, u_y+v_y)\right)$

처음에 $U$와 $V$는 모두 비어 있다. 편의상 $U$ 또는 $V$가 비어 있는 경우 $D(U,V)$값은 $-1$로 정의하도록 하자. 이제 쿼리를 통해 $U$와 $V$에 정수점이 자유롭게 추가되거나 제거된다. 변화가 일어날 때 마다 $D(U,V)$를 계산하는 프로그램을 작성하도록 하자.

중복집합에 점을 추가하는 쿼리는 1 s x y 와 같이 주어진다. $s=1$인 경우에는 $U$에, $s=2$인 경우에는 $V$에 점 $(x,y)$를 추가하라는 의미이다.

중복집합에 점을 제거하는 쿼리는 2 s x y 와 같이 주어진다. $s=1$인 경우에는 $U$에서, $s=2$인 경우에는 $V$에서 점 $(x,y)$를 제거하라는 의미이다.

$U$와 $V$는 각각 중복집합이므로, 점이 추가될 때 이미 존재하는 점이 추가될 수도 있다.

$U$와 $V$에서 점을 제거할 때 이미 동일한 좌표를 가지는 점이 여러 개 존재하는 경우, 그 중 하나만 없애는 것으로 처리한다. 존재하지 않는 점을 제거하는 쿼리는 주어지지 않는다.

입력

입력의 첫 줄에 쿼리의 개수를 나타내는 $q$가 주어진다.

이후 $q$개의 줄에 걸쳐 쿼리를 나타내는 정수 r s x y가 주어진다.

출력

$q$개 줄에 각 쿼리를 실행한 직후의 $D(U,V)$값을 출력한다.

두 집합 중 하나라도 비어 있는 경우 $D(U,V) = -1$임에 유의하라.

제한

• $1 \le q \le 250\,000$

• $1 \le r, s \le 2$

• $0 \le x, y \le 250\, 000$

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

출처

• 문제를 만든 사람: Diuven, leesongun

• 문제를 검수한 사람: jhnah917, jhwest2