题目描述

今年，JOI 国将主办 IOI（国际信息学奥林匹克竞赛）。届时将有 $N$ 名选手参赛，编号从 $1$ 到 $N$。

每位选手的国籍由一个介于 $1$ 和 $10^9$ 之间的整数表示：选手 $i(1\le i\le N)$ 来自国家 $C_i$。保证 $N$ 个选手的国籍不完全相同（即存在 $i\ne j(1\le i,j\le N)$ 使得 $C_i\ne C_j$）。

选手的座位排成一条直线，选手 $i(1\le i\le N)$ 的座位在 $X_i$ 处。选手 $i(1\le i\le N)$ 和选手 $j(1\le j\le N)$ 之间的座位距离为 $|X_i-X_j|$。

每个选手都想知道在与其他选手交流时，与离自己最近的异国选手的座位距离。

给定每个选手的国籍和座位位置，请为每个选手 $i(1\le i\le N)$ 求出与其来自不同国家的选手中，座位离选手 $i$ 最近的选手与 $i$ 的座位距离。

输入格式

第一行输入一个整数 $N$。

接下来 $N$ 行，每行输入两个整数 $C_i,X_i$。

输出格式

输出 $N$ 行，第 $i$ 行输出一个整数，表示座位离选手 $i$ 最近的选手与 $i$ 的座位距离。

3
2 5
1 1
1 2

3
4
3

5
1 1
2 4
2 14
3 10
2 2

1
3
4
4
1

3
1 1
2 1
1 1

0
0
0

提示

【样例解释 #1】

• 选手 $1$ 来自国家 $2$，选手 $2, 3$ 和他 / 她来自不同国家。在这些选手中，与选手 $1$ 座位距离最小的是选手 $3$，座位距离为 $3$。因此，答案为 $3$；
• 选手 $2$ 来自国家 $1$，选手 $1$ 是唯一和他 / 她来自不同国家的选手。选手 $2$ 和选手 $1$ 之间的座位距离为 $4$；
• 选手 $3$ 来自国家 $1$，选手 $1$ 是唯一和他 / 她来自不同国家的选手。选手 $3$ 和选手 $1$ 之间的座位距离为 $3$。

该样例满足子任务 $1,2,3$ 的限制。

【样例解释 #2】

该样例满足子任务 $1,2,3$ 的限制。

【样例解释 #3】

该样例满足子任务 $1,2,3$ 的限制。

【数据范围】

• $2\le N \le 3\times 10^5$；
• $1\le C_i\le 10^9(1\le i\le N)$ 且 $C_i$ 不完全相同；
• $1\le X_i\le 10^9(1\le i\le N)$。

【子任务】

1. （$20$ 分）$N\le 1000$；
2. （$40$ 分）$C_i\le 10(1\le i\le N)$；
3. （$40$ 分）无附加限制。