题目描述

给你一个无限大的棋盘和 $N$ 个敌方车的位置 $(X_i, Y_i)$。每辆车的攻击范围为这辆车所在的一行与这辆车所在的一列，这些车互不攻击（每行每列最多只有一辆车）。

你要把其中一辆车换成国王，然后让国王不断移动，尽可能多地吃掉其他车。

国王可以向前、向后、向左、向右移动，但是不能走进会被车攻击的格子。另外，如果有一辆车在国王的斜对角方向，国王可以斜着移动并吃掉车，但是 不能斜着走到空格。

换句话说，这个国王就像个超级兵，能斜着四个方向吃子，横竖四个方向走动。

对每辆车，假设把它换成国王，求吃掉最多车的情况下，最少需要多少步。

输入格式

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

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

输出格式

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

样例 1

输入

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

输出

5
0
7
5
0
0

样例 2

输入

5
5 5
100 100
70 20
81 70
800 1

输出

985
985
1065
1034
0

样例 3

输入

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

说明/提示

限制条件

• $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$。