좌석 2

면접 대비

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

요약

각 선수마다 나라가 다른 선수 중 가장 가까운 좌석까지의 거리를 구합니다.

난이도: 보통10점 중 4점
유형: 정렬, 배열
정답자: 아직 제출이 없습니다

문제

JOI 국에서 올해 프로그래밍 세계 대회가 열리게 되었다. 대회에는 $N$ 명의 선수가 참가할 예정이며, 선수에게는 1부터 $N$ 까지 번호가 붙어 있다.

각 선수의 출신 국가는 1 이상 $10^9$ 이하의 정수로 표현된다. 선수 $i$ ( $1 \le i \le N$ )의 출신 국가는 국가 $C_i$ 이다. $N$ 명의 선수가 모두 같은 국가 출신인 경우는 없다. 각 선수의 좌석은 직선 위에 놓여 있으며, 선수 $i$ ( $1 \le i \le N$ )의 좌석은 위치 $X_i$ 에 있다. 선수 $i$ 와 선수 $j$ ( $1 \le j \le N$ )의 좌석 거리는 $|X_i - X_j|$ 이다. 여기서 $|x|$ 는 $x$ 의 절댓값이다.

각 선수는 대회 중 다른 선수와 교류할 때, 자신과 출신 국가가 다른 선수 가운데 좌석이 가장 가까운 선수까지의 좌석 거리를 알고 싶어 한다.

각 선수의 출신 국가와 좌석 위치가 주어졌을 때, 각 선수 $i$ ( $1 \le i \le N$ )에 대해 선수 $i$ 와 출신 국가가 다른 선수 중 좌석 거리가 가장 작은 선수까지의 좌석 거리를 출력하라.

입력

N
C1 X1
C2 X2
⋮
CN XN

출력

$N$ 행을 출력하라. $i$ 행 ( $1 \le i \le N$ )에는 선수 $i$ 와 출신 국가가 다른 선수 중 좌석 거리가 가장 작은 선수까지의 좌석 거리를 출력하라.

제한

$2 \le N \le 300000$ .
$1 \le C_i \le 10^9$ ( $1 \le i \le N$ ).
$1 \le X_i \le 10^9$ ( $1 \le i \le 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
```