“千岛之国”是二十世纪九十年代中期克罗地亚旅游业的官方口号。虽然这个口号在技术上并不精确（克罗地亚实际上有略多于 1000 个岛屿），但“跳岛游”（从一个岛航行到另一个岛）确实是一项受欢迎的夏季活动。

为了解决这个问题，亚得里亚海的地图被表示为一个由单位正方形组成的网格，包含 $2500$ 行和 $2500$ 列。行从北到南依次编号为 $1$ 到 $2500$，列从西到东依次编号为 $1$ 到 $2500$。海上有 $N$ 个岛屿，编号为 $1$ 到 $N$，每个岛屿都位于网格的某个单位正方形内。岛屿 $K$ 的位置由其对应的网格正方形坐标给出——即其行号 $R_K$ 和列号 $C_K$。最后，没有两个岛屿位于同一位置。

图 1：与下方第一个样例对应的地图

由于风向和洋流的影响，从一个岛屿只能直接航行到大致位于其西北或东南方向的岛屿。更具体地说，如果满足以下条件之一，就可以在一步（一次航行）内从岛屿 $A$ 航行到岛屿 $B$：

• $R_A < R_B$ 且 $C_A < C_B$
• $R_A > R_B$ 且 $C_A > C_B$

需要注意的是，两个岛屿之间的距离或它们之间是否存在其他岛屿，并不影响从一个岛屿直接跳跃到另一个岛屿的可行性。如果无法直接从 $A$ 航行到 $B$，则可能可以通过其他岛屿作为中转，利用一系列航行从 $A$ 到达 $B$。从 $A$ 到 $B$ 的航行距离定义为从 $A$ 航行到 $B$ 所需的最少航行次数。

例如，在图 1 中，从位于第 $2$ 行第 $3$ 列的岛屿出发，我们可以直接航行到其他四个岛屿，而到剩下的两个岛屿的航行距离为 $2$。

任务

目前正在筹划一次航海大会，组织者正在考虑将每个岛屿作为大会的候选举办地。在评估一个候选岛屿时，他们想知道：如果其他每个岛屿都派出一条帆船，所有帆船到达该候选岛屿所需的最少航行总次数是多少？这等价于求从所有其他岛屿到该候选岛屿的航行距离之和。请编写一个程序，在给定 $N$ 个岛屿的位置后，对于每个岛屿 $K$，计算从所有其他岛屿到岛屿 $K$ 的航行距离之和。

测试数据保证，对于任意两个岛屿 $A$ 和 $B$，都可以通过某种航行序列从 $A$ 航行到 $B$。

输入格式

输入的第一行包含一个整数 $N$（$3 \le N \le 250\,000$），表示岛屿的数量。

接下来的 $N$ 行包含岛屿的位置。每个位置由两个介于 $1$ 到 $2500$（含）之间的整数组成，分别表示行号和列号。

输出格式

输出应包含 $N$ 行。对于每个岛屿，按照它们在输入中出现的顺序，在单行中输出从所有其他岛屿到该岛屿的航行距离之和。

子任务

• 在总分值为 25 分的测试用例中，$N$ 最多为 $100$。
• 在总分值为 50 分的测试用例中，$N$ 最多为 $1500$。
• 在总分值为 60 分的测试用例中，$N$ 最多为 $5000$。
• 在总分值为 80 分的测试用例中，$N$ 最多为 $25000$。

样例

输入样例 1

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

输出样例 1

16
11
12
11
12
16
8

输入样例 2

4
1 1
2 3
3 2
4 4

输出样例 2

3
4
4
3