AT_agc047_f.[AGC047F] Rooks

给你一个无限大的棋盘和 $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$ 表示在这种情况下能够吃掉的最大车数（步数不限）。

限制条件

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