问题描述

给定 $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$ 的最小移动次数（在无限时间内）。

示例输入 1

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

示例输出 1

5
0
7
5
0
0

请参见下面的示意图。如果我们用国王替换第 3 辆车，我们可以打败最多两辆其他车。红色路径是最佳移动序列之一：先打败第 1 辆车，然后一直向下和向右移动，直到你可以打败第 4 辆车。总共需要 7 步，这是输出中的第三个数字。

x 坐标从左到右递增，y 坐标从下到上递增。

从车辆 2、5 或 6 开始，我们无法打败其他车。最佳移动次数为 0。

示例输入 2

5
5 5
100 100
70 20
81 70
800 1

示例输出 2

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

示例输出 3

2
2
9
9
3
3
24
5
0
25