Yum Yum

Time limit2sMemory limit1024 MB

Summary

For each rook replaced by the Coach, find the fewest moves needed to eat the most rooks while stepping only on cells outside every rook's row and column.

Level: Hard8 of 10
Topics: Graph, BFS, Sorting
Solved: No attempts yet

Problem

On an infinite chessboard there are $N$ rooks. A rook can attack any piece in the same row or the same column. Initially, no rook can attack another rook. In other words, every rook is in a different row, and every rook is in a different column.

You replace one of these rooks with a Coach Gu piece. The Coach can move to an orthogonally adjacent cell (up, down, left, or right). It cannot move to a cell that a rook attacks, meaning a cell in the same row or column as any rook.

The Coach likes delicious food. If a rook is in one of the 8 cells around the Coach (orthogonal or diagonal), the Coach can move onto that rook's cell and eat it. Eating a rook takes priority over being attacked by a rook.

The Coach tries to eat as many rooks as possible. If several ways reach the maximum, it uses the one with the fewest moves.

For each rook, suppose that rook is replaced by the Coach. Output the minimum number of moves the Coach makes to eat the maximum number of rooks.

Input

The first line contains $N$ ( $2 \le N \le 200\,000$ ). Each of the next $N$ lines contains the coordinates $X_i, Y_i$ of a rook ( $1 \le X_i, Y_i \le 10^6$ ).

All rooks are in different rows and different columns. In other words, $X_i \neq X_j$ and $Y_i \neq Y_j$ whenever $i \neq j$ .

Output

Print $N$ lines. The $i$ -th line contains the minimum number of moves the Coach makes to eat the maximum number of rooks when the $i$ -th rook is replaced by the Coach.

Examples2

Example 1
Input
```
6
1 8
6 10
2 7
4 4
9 3
5 1
```
Expected output
```
5
0
7
5
0
0
```

Example 2

Input

Expected output