시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1536 MB89292540.323%

문제

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$

예제 입력 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
W3sicHJvYmxlbV9pZCI6IjIxNzMzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiMlx1Y2MyOFx1YzZkMCBcdWM4MTBcdWFjZmMgXHVjZmZjXHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD4yXHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NCBcdWM3MDRcdWM1ZDAgXHVjODE1XHVjMjE4XHVjODEwXHViNGU0XHVjNzU4IFx1YzkxMVx1YmNmNVx1YzlkMVx1ZDU2OShtdWx0aXNldClcdWM3NzggJFUkXHVjNjQwICRWJFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWM5MTFcdWJjZjVcdWM5ZDFcdWQ1NjkgJFUsIFYkXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjJlNFx1Yzc0Y1x1Yzc1OCBcdWFjMTIgJEQoVSwgVikkXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD4kJEQoVSwgVikgPSBcXG1pbl97dSBcXGluIFUsIHYgXFxpbiBWfSBcXGxlZnQoIFxcbWF4ICh1X3grdl94LCB1X3krdl95KVxccmlnaHQpJCQ8XC9wPlxyXG5cclxuPHA+XHVjYzk4XHVjNzRjXHVjNWQwICRVJFx1YzY0MCAkViRcdWIyOTQgXHViYWE4XHViNDUwIFx1YmU0NFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1ZDNiOFx1Yzc1OFx1YzBjMSAkVSQgXHViNjEwXHViMjk0ICRWJFx1YWMwMCBcdWJlNDRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMCAkRChVLFYpJFx1YWMxMlx1Yzc0MCAkLTEkXHViODVjIFx1YzgxNVx1Yzc1OFx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWQ1NThcdWM3OTAuIFx1Yzc3NFx1YzgxYyBcdWNmZmNcdWI5YWNcdWI5N2MgXHVkMWI1XHVkNTc0ICRVJFx1YzY0MCAkViRcdWM1ZDAgXHVjODE1XHVjMjE4XHVjODEwXHVjNzc0IFx1Yzc5MFx1YzcyMFx1Yjg2ZFx1YWM4YyBcdWNkOTRcdWFjMDBcdWI0MThcdWFjNzBcdWIwOTggXHVjODFjXHVhYzcwXHViNDFjXHViMmU0LiBcdWJjYzBcdWQ2NTRcdWFjMDAgXHVjNzdjXHVjNWI0XHViMGEwIFx1YjU0YyBcdWI5YzhcdWIyZTQgJEQoVSxWKSRcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWIzYzRcdWI4NWQgXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWM5MTFcdWJjZjVcdWM5ZDFcdWQ1NjlcdWM1ZDAgXHVjODEwXHVjNzQ0IFx1Y2Q5NFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWNmZmNcdWI5YWNcdWIyOTQgPGVtPjEgcyB4IHk8XC9lbT4gXHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICRzPTEkXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAkVSRcdWM1ZDAsICRzPTIkXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAkViRcdWM1ZDAgXHVjODEwICQoeCx5KSRcdWI5N2MmbmJzcDtcdWNkOTRcdWFjMDBcdWQ1NThcdWI3N2NcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5MTFcdWJjZjVcdWM5ZDFcdWQ1NjlcdWM1ZDAgXHVjODEwXHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1OFx1YjI5NCBcdWNmZmNcdWI5YWNcdWIyOTQgPGVtPjIgcyB4IHk8XC9lbT4gXHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICRzPTEkXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAkVSRcdWM1ZDBcdWMxMWMsICRzPTIkXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAkViRcdWM1ZDBcdWMxMWMgXHVjODEwICQoeCx5KSRcdWI5N2MmbmJzcDtcdWM4MWNcdWFjNzBcdWQ1NThcdWI3N2NcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4kVSRcdWM2NDAgJFYkXHViMjk0IFx1YWMwMVx1YWMwMSBcdWM5MTFcdWJjZjVcdWM5ZDFcdWQ1NjlcdWM3NzRcdWJiYzBcdWI4NWMsIFx1YzgxMFx1Yzc3NCBcdWNkOTRcdWFjMDBcdWI0MjAgXHViNTRjIFx1Yzc3NFx1YmJmOCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVjODEwXHVjNzc0IFx1Y2Q5NFx1YWMwMFx1YjQyMCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD4kVSRcdWM2NDAgJFYkXHVjNWQwXHVjMTFjIFx1YzgxMFx1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NjAgXHViNTRjIFx1Yzc3NFx1YmJmOCBcdWIzZDlcdWM3N2NcdWQ1NWMgXHVjODhjXHVkNDVjXHViOTdjIFx1YWMwMFx1YzljMFx1YjI5NCBcdWM4MTBcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwLCBcdWFkZjggXHVjOTExIFx1ZDU1OFx1YjA5OFx1YjljYyBcdWM1YzZcdWM1NjBcdWIyOTQgXHVhYzgzXHVjNzNjXHViODVjIFx1Y2M5OFx1YjlhY1x1ZDU1Y1x1YjJlNC4gXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWM4MTBcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTU4XHViMjk0IFx1Y2ZmY1x1YjlhY1x1YjI5NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjZmZjXHViOWFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgJHEkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0ICRxJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1Y2ZmY1x1YjlhY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4IDxlbT5yIHMgeCB5PFwvZW0+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4kcSRcdWFjMWMgXHVjOTA0XHVjNWQwIFx1YWMwMSBcdWNmZmNcdWI5YWNcdWI5N2MgXHVjMmU0XHVkNTg5XHVkNTVjIFx1YzljMVx1ZDZjNFx1Yzc1OCAkRChVLFYpJFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWM5ZDFcdWQ1NjkgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjc3Y1x1YjNjNCBcdWJlNDRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMCAkRChVLFYpID0gLTEkXHVjNzg0XHVjNWQwIFx1YzcyMFx1Yzc1OFx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDEgXFxsZSBxIFxcbGUgMjUwXFwsMDAwJDxcL2xpPlxyXG5cdDxsaT4kMSBcXGxlIHIsIHMgXFxsZSAyJDxcL2xpPlxyXG5cdDxsaT4kMCBcXGxlIHgsIHkgXFxsZSAyNTBcXCwgMDAwJDxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjE3MzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQb2ludHMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSB0d28gbXVsdGlzZXRzICRVJCBhbmQgJFYkIHRoYXQgY29udGFpbiB0d28tZGltZW5zaW9uYWwgcG9pbnRzIHdpdGggaW50ZWdlciBjb29yZGluYXRlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2Ugd2lsbCBkZWZpbmUgdGhlIGZvbGxvd2luZyBmdW5jdGlvbiAkRChVLCBWKSQgZm9yIGEgcGFpciBvZiBtdWx0aXNldHM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JEQoVSwgVikgPSAtMSQgaWYgZWl0aGVyIHNldCBpcyBlbXB0eS48XC9saT5cclxuXHQ8bGk+JEQoVSwgVikgPSBcXG1pblxcbGltaXRzX3tcXGJlZ2lue3NtYWxsbWF0cml4fSh1X3gsIHVfeSkgXFxpbiBVIFxcXFwgKHZfeCwgdl95KSBcXGluIFZcXGVuZHtzbWFsbG1hdHJpeH19XFxtYXgodV94ICsgdl94LCB1X3kgKyB2X3kpJCBvdGhlcndpc2UuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SW4gdGhlIGJlZ2lubmluZywgYm90aCAkVSQgYW5kICRWJCBhcmUgZW1wdHkuIFByb2Nlc3MgJFEkIHF1ZXJpZXMgb2YgdGhlIGZvbGxvd2luZyBmb3JtOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiZxdW90Ozxjb2RlPjEmbmJzcDs8XC9jb2RlPiRzJDxmb250IGZhY2U9XCJtb25vc3BhY2VcIj4gPFwvZm9udD4keCQ8Zm9udCBmYWNlPVwibW9ub3NwYWNlXCI+IDxcL2ZvbnQ+JHkkJnF1b3Q7OiBBZGQgYSBwb2ludCAkKHgsIHkpJCB0byBvbmUgb2YgdGhlIHNldHMuIElmICRzID0gMSQsIGFkZCB0aGUgcG9pbnQgdG8gJFUkLiBPdGhlcndpc2UsIGFkZCB0aGUgcG9pbnQgdG8gJFYkLjxcL2xpPlxyXG5cdDxsaT4mcXVvdDs8Y29kZT4yIDxcL2NvZGU+JHMkPGZvbnQgZmFjZT1cIm1vbm9zcGFjZVwiPiA8XC9mb250PiR4JDxmb250IGZhY2U9XCJtb25vc3BhY2VcIj4gPFwvZm9udD4keSQmcXVvdDs6IERlbGV0ZSBhIHBvaW50ICQoeCwgeSkkIGZyb20gb25lIG9mIHRoZSBzZXRzLiBJZiAkcyA9IDEkLCBkZWxldGUgdGhlIHBvaW50IGZyb20gJFUkLiBPdGhlcndpc2UsIGRlbGV0ZSB0aGUgcG9pbnQgZnJvbSAkViQuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+V2hlbiBkZWxldGluZyBhIHBvaW50LCBpZiB0aGVyZSBhcmUgbXVsdGlwbGUgcG9pbnRzIGF0IHRoZSBnaXZlbiBjb29yZGluYXRlcywgeW91IHNob3VsZCBkZWxldGUgb25seSBvbmUgb2YgdGhlbS4gSXQgaXMgZ3VhcmFudGVlZCB0aGF0IHRoZSBnaXZlbiBwb2ludCBleGlzdHMgaW4gdGhlIGdpdmVuIG11bHRpc2V0IGF0IHRoZSB0aW1lIG9mIGVhY2ggZGVsZXRpb24uPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBwcm9jZXNzIHRoZSBxdWVyaWVzLiBBZnRlciBlYWNoIHF1ZXJ5LCBwcmludCB0aGUgdmFsdWUgJEQoVSwgVikkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciAkUSQgKCQxIFxcbGUgUSBcXGxlIDI1MFxcLDAwMCQpLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0ICRRJCBsaW5lcyBjb250YWlucyBhIHF1ZXJ5IGluIHRoZSBmb3JtIGRlc2NyaWJlZCBhYm92ZS4gQ29uc3RyYWludHMgZm9yIGJvdGggdHlwZXMgb2YgcXVlcmllczogJHMgXFxpbiBcXHsxLCAyXFx9JCwgJDAgXFxsZSB4LCB5IFxcbGUgMjUwXFwsMDAwJC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgJFEkIGxpbmVzLiBFYWNoIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIHZhbHVlICREKFUsIFYpJCBhZnRlciB0aGUgY29ycmVzcG9uZGluZyBxdWVyeS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > IDTcup > 제 3회 IDTcup I번

Camp > Petrozavodsk Programming Camp > Winter 2022 > Day 2: Grand Prix of Daejeon A번