31638번 - 座席 2 (Seats 2) 서브태스크다국어

문제

JOI 国では,今年プログラミングの世界大会が開かれることとなった.大会には N 人の選手が参加予定であり,選手には 1 から N までの番号が付けられている.

各選手の出身国は 1 以上 10⁹ 以下の整数の番号で表され,選手 i (1 ≦ i ≦ N) の出身国は国 C_i である.N 人の選手の出身国がすべて同じであることはない. また,各選手の座席は直線状に並んでおり,選手 i (1 ≦ i ≦ N) の座席は位置 X_i にある.選手 i (1 ≦ i ≦ N) と選手 j (1 ≦ j ≦ N) の座席の距離は |X_i - X_j| である.ただし,|x| は x の絶対値を表す.

各選手は大会中他の選手と交流をするにあたって,自分とは出身国の異なる選手のうち,自分と座席が最も近い選手までの座席の距離を知りたい.

各選手の出身国と座席の位置の情報が与えられたとき,各選手 i (1 ≦ i ≦ N) について,選手 i とは出身国の異なる選手のうち,選手 i との座席の距離が最も小さい選手までの座席の距離を出力するプログラムを作成せよ.

입력

入力は以下の形式で与えられる.

N
C1 X1
C2 X2
...
CN XN

출력

N 行出力せよ.i 行目 (1 ≦ i ≦ N) には,選手 i とは出身国の異なる選手のうち,選手 i との座席の距離が最も小さい選手までの座席の距離を出力せよ.

제한

• 2 ≦ N ≦ 300 000.
• 1 ≦ C_i ≦ 10⁹ (1 ≦ i ≦ N).
• 1 ≦ X_i ≦ 10⁹ (1 ≦ i ≦ N).
• N 人の選手の出身国がすべて同じであることはない.
• 入力される値はすべて整数である.

서브태스크

힌트