Seats 2

Interview

Time limit2sMemory limit1024 MB

Summary

For each player, find the smallest seat distance to a player from a different country when N players sit on a line.

Level: Medium4 of 10
Topics: Sorting, Array
Solved: No attempts yet

Problem

The JOI country is holding a programming world competition this year. $N$ players are scheduled to attend, numbered from 1 to $N$ .

Each player's home country is an integer from 1 to $10^9$ . Player $i$ ( $1 \le i \le N$ ) is from country $C_i$ . Not all $N$ players are from the same country. Each player's seat lies on a straight line, and player $i$ ( $1 \le i \le N$ ) sits at position $X_i$ . The seat distance between player $i$ and player $j$ ( $1 \le j \le N$ ) is $|X_i - X_j|$ , where $|x|$ is the absolute value of $x$ .

During the competition, each player wants to know the seat distance to the nearest player from a different country.

Given each player's country and seat position, print for each player $i$ ( $1 \le i \le N$ ) the smallest seat distance from player $i$ to a player from a different country.

Input

N
C1 X1
C2 X2
⋮
CN XN

Output

Print $N$ lines. On line $i$ ( $1 \le i \le N$ ), print the seat distance from player $i$ to the nearest player whose country differs from player $i$ 's country.

Constraints

$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$ ).
Not all $N$ players are from the same country.
All input values are integers.

Examples3

Example 1
Input
```
3
2 5
1 1
1 2
```
Expected output
```
3
4
3
```
Example 2
Input
```
5
1 1
2 4
2 14
3 10
2 2
```
Expected output
```
1
3
4
4
1
```
Example 3
Input
```
3
1 1
2 1
1 1
```
Expected output
```
0
0
0
```