配点: 100 点
問題文
在JOI国,今年将举办编程世界大赛。比赛预计有 N 名选手参加,选手被分配了直到 1 到 N 的编号。
各选手的出身国家用 1 以上 10^9 以下的整数编号表示,选手 i (1 \leqq i \leqq N) 的出身国家是国 C_i 。N 人的选手的出身国家不都是相同的。 另外,各选手的座位排列成直线,选手 i (1 \leqq i \leqq N) 座位的位置是 X_i 。 参赛者 i (1 \leqq i \leqq N) 和选手 j (1 \leqq j \leqq N) 的座位的距离是是 |X_i - X_j| 。 但是,|x| 是 x 表示绝对值。
各位选手在比赛中与其他选手交流时,希望知道与自己来自不同国家的选手中,离自己座位最近的选手的座位距离。
当给出各位选手的出身国家和座位位置的信息时,各位选手 i (1 \leqq i \leqq N) 关于,选手 i 中与自己出身国家不同的选手,以及与自己座位最近的选手的座位距离。 i 请编写一个程序,输出各选手与出身国家不同且座位最近的选手的座位距离。
制約
- 2 \leqq N \leqq 300\,000.
- 1 \leqq C_i \leqq 10^9 (1 \leqq i \leqq N).
- 1 \leqq X_i \leqq 10^9 (1 \leqq i \leqq N).
- N 不会出现所有选手都来自同一个国家。
- 所有输入值均为整数。
小課題
- (20 点) N \leqq 1\,000.
- (40 点) C_i \leqq 10 (1 \leqq i \leqq N).
- (40 点)没有额外的限制。
入力
输入按以下格式给出。
N C_1 X_1 C_2 X_2 \vdots C_N X_N
出力
N 行。i 行目 (1 \leqq i \leqq N) 中,输出选手 i 中与自己出身国家不同的选手,以及与自己座位最近的选手的座位距离。 i 与座位最近的出身国家不同的选手的座位距离。
入力例 1
3 2 5 1 1 1 2
出力例 1
3 4 3
選手 1 的出身国家是国家 2 ,与选手 1 出身国家不同的选手是选手 2, 3 。在这些选手中,与选手 1 座位最近的选手是选手 3 ,其座位的距离是 3 。因此,只有1 行是
一个整数,表示第 3 。
選手 2 的出身国家是国家 1 ,与选手 2 出身国家不同的选手是选手 1 。参赛者 2 和选手 1 的座位距离是 4 ,所以,2 行是
一个整数,表示第 4 。
選手 3 的出身国家是国家 1 ,与选手 3 出身国家不同的选手是选手 1 。参赛者 3 和选手 1 的座位距离是 3 ,所以,3 行是
一个整数,表示第 3 。
此输入示例是一个小作业。 1, 2, 3 满足约束。
入力例 2
5 1 1 2 4 2 14 3 10 2 2
出力例 2
1 3 4 4 1
此输入示例是一个小作业。 1, 2, 3 满足约束。
入力例 3
3 1 1 2 1 1 1
出力例 3
0 0 0
同一个位置可能有多个运动员的座位。
此输入示例是一个小作业。 1, 2, 3 满足约束。