配点 : $2200$ 点

問題文

無限に広がるチェス盤上の $N$ 個の敵ルークの位置 $(X_i, Y_i)$ が与えられます。[訳注: ルークは将棋の飛車と似た動きをする駒です。] どの二つのルークも、お互いを攻められる位置にはありません (すなわち、一行あたり、または一列あたりのルークの数は一個以下です)。

あなたは、ルークのうち一個をキングに置き換え、キングを繰り返し動かしてできるだけ多くのルークを取ろうとしています。[訳注: キングは将棋の王将と似た動きをする駒です。]

ルークに攻められているマスに入ることはできません。 また、斜めに移動することで空きマスに移ることもできません (しかし、斜めに移動することでルークを取ることはできます)。

(つまり、このキングの動きは、斜め四方向に動いて駒を取ることと縦横四方向に動くことができる強化版ポーンのようなものです。)

各ルークについて、そのルークをキングで置き換えた際に取ることのできる最大数のルークを取るために必要な最小手数を求めてください。

制約

• $2 \leq N \leq 200\,000$
• $1 \leq X_i, Y_i \leq 10^6$
• $X_i \neq X_j$
• $Y_i \neq Y_j$
• 入力中の値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$X_1$ $Y_1$

$X_2$ $Y_2$

$\vdots$

$X_N$ $Y_N$

出力

$N$ 行出力せよ。 $i$ 行目は、$(X_i, Y_i)$ に置かれたルークをキングに置き換えた場合に対応する。 この行には、一つの整数、すなわち $M_i$ 個のルークを取るために必要な最小手数を出力せよ。 ここで、$M_i$ は (何手かけてもよいとして) この場合に取ることのできるルークの最大数である。

6
1 8
6 10
2 7
4 4
9 3
5 1

5
0
7
5
0
0

下図を見てください。 ルーク $3$ をキングに置き換えた場合、他のルークを最大で二個取ることができます。 図の赤い経路がこの場合の最適な手順の一つ - ルーク $1$ を取り、右下方向に進み続けてルーク $4$ を取る - です。 ここでの手数は $7$ 手であり、これが出力例の三つ目の数です。

x 軸正方向: 右、y 軸正方向: 上

ルーク $2, 5, 6$ のいずれかをキングに置き換えた場合には、他のルークを一個も取ることができません。このとき、最小手数は $0$ です。

5
5 5
100 100
70 20
81 70
800 1

985
985
1065
1034
0

10
2 5
4 4
13 12
12 13
14 17
17 19
22 22
16 18
19 27
25 26

2
2
9
9
3
3
24
5
0
25