座席 2 (Seats 2)

시간 제한2초메모리 제한1024 MB

요약

각 선수마다 출신 국가가 다른 선수 중 좌석 거리가 가장 가까운 선수까지의 거리를 구한다.

난이도: 보통10점 중 5점
유형: 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

JOI 国では，今年プログラミングの世界大会が開かれることとなった．大会には N 人の選手が参加予定であり，選手には 1 から N までの番号が付けられている．

各選手の出身国は 1 以上 109 以下の整数の番号で表され，選手 i (1 ≦ i ≦ N) の出身国は国 Ci である．N 人の選手の出身国がすべて同じであることはない．また，各選手の座席は直線状に並んでおり，選手 i (1 ≦ i ≦ N) の座席は位置 Xi にある．選手 i (1 ≦ i ≦ N) と選手 j (1 ≦ j ≦ N) の座席の距離は |Xi - Xj| である．ただし，|x| は x の絶対値を表す．

各選手は大会中他の選手と交流をするにあたって，自分とは出身国の異なる選手のうち，自分と座席が最も近い選手までの座席の距離を知りたい．

各選手の出身国と座席の位置の情報が与えられたとき，各選手 i (1 ≦ i ≦ N) について，選手 i とは出身国の異なる選手のうち，選手 i との座席の距離が最も小さい選手までの座席の距離を出力するプログラムを作成せよ．

입력

入力は以下の形式で与えられる．

N
C1   X1
C2   X2
︙
CN   XN

출력

N 行出力せよ．i 行目 (1 ≦ i ≦ N) には，選手 i とは出身国の異なる選手のうち，選手 i との座席の距離が最も小さい選手までの座席の距離を出力せよ．

제한

2 ≦ N ≦ 300 000．
1 ≦ Ci ≦ 109 (1 ≦ i ≦ N)．
1 ≦ Xi ≦ 109 (1 ≦ i ≦ N)．
N 人の選手の出身国がすべて同じであることはない．
入力される値はすべて整数である．

예제3

예제 1
입력
```
3
2 5
1 1
1 2
```
예상 출력
```
3
4
3
```
예제 2
입력
```
5
1 1
2 4
2 14
3 10
2 2
```
예상 출력
```
1
3
4
4
1
```
예제 3
입력
```
3
1 1
2 1
1 1
```
예상 출력
```
0
0
0
```