题目描述

在无限扩展的棋盘上，给定 $N$ 个敌方车的位置 $(X_i,\ Y_i)$。[译注：车的走法与国际象棋中的 Rook 相同。] 任意两个车都不会互相攻击（即每一行和每一列至多只有一个车）。

你可以将其中一个车替换为国王，并反复移动国王，尽可能多地吃掉其他车。[译注：国王的走法与国际象棋中的 King 相同。]

你不能进入被车攻击的位置。此外，不能通过斜向移动到空白格子（但可以通过斜向移动吃掉车）。

（也就是说，这个国王的移动方式类似于一种强化版的“兵”，可以沿斜向四个方向吃子，也可以沿纵横四个方向移动。）

对于每一个车，求当你将该车替换为国王时，能够吃掉的最大车数所需的最小步数。

输入格式

输入以如下格式从标准输入给出。

$N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\cdots$ $X_N$ $Y_N$

输出格式

输出 $N$ 行。第 $i$ 行对应将 $(X_i,\ Y_i)$ 处的车替换为国王的情况。该行输出一个整数，即吃掉 $M_i$ 个车所需的最小步数。这里 $M_i$ 表示在这种情况下能够吃掉的最大车数（步数不限）。

输入输出样例 #1

输入 #1

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

输出 #1

5
0
7
5
0
0

输入输出样例 #2

输入 #2

5
5 5
100 100
70 20
81 70
800 1

输出 #2

985
985
1065
1034
0

输入输出样例 #3

输入 #3

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

输出 #3

2
2
9
9
3
3
24
5
0
25

说明/提示

限制条件

• $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$
• 输入中的所有值均为整数。

样例说明 1

请参见下图。当将第 $3$ 个车替换为国王时，最多可以吃掉另外两个车。图中的红色路径是一种最优方案——先吃掉第 $1$ 个车，然后不断向右下方移动，吃掉第 $4$ 个车。此时所需步数为 $7$，这就是输出样例第三个数字。

$x$ 轴正方向为右，$y$ 轴正方向为上
如果将第 $2,5,6$ 个车替换为国王，则无法吃掉任何其他车，此时最小步数为 $0$。