遠い昔、はるかかなたの銀河系で。
時は内乱の嵐が吹き荒れるさなか、凶悪な銀河帝国の軍勢が反乱軍の秘密基地を襲った。
恐るべき帝国宇宙艦隊の追撃から逃れた、ウーク・スターウォーカーによって率いられる自由の戦士たちは、銀河の辺境に新たな秘密基地を築くことにした。
反乱軍の一員であり、凄腕のプログラマーであるあなたにあたえられたミッションは、銀河系のそれぞれの惑星から最も離れた惑星を見つけることである。
銀河系には $N$ 個の惑星があり、$M$ 個の「橋」と呼ばれる秘密のルートがある。
惑星にはそれぞれ $1,2, \ldots N$ の番号が、橋にはそれぞれ $1,2, \ldots M$ の番号がついている。
各惑星の位置は実三次元空間上の点として表され、惑星 $p$ は $(x_p,y_p,z_p)$ に位置する。
$i$ 番目の橋は、惑星 $u_i$ から $v_i$ へと向かう秘密のルートである。
$i$ 番目の橋を使って惑星 $v_i$ から $u_i$ へ直接移動することはできないことに注意せよ。
惑星 $p$ と $q$ の距離を以下のように定義する。
$\mathrm{d} (p,q) = |x_p - x_q| + |y_p - y_q| + |z_p - z_q|$
惑星 $p$ から $0$ 個以上の橋を伝って到達可能な惑星の集合を $S_p$ とする。
各 $p$ について、$\displaystyle \max_{s \in S_p} \mathrm{d} (p,s)$ を求めよ。
ただし、反乱軍は常に凶悪な銀河帝国の軍勢に狙われているため、橋以外のルートで惑星間を移動することはできない。
入力は以下の形式で与えられる。
$N$ $M$ $x_1$ $y_1$ $z_1$ $\vdots$ $x_N$ $y_N$ $z_N$ $u_1$ $v_1$ $\vdots$ $u_M$ $v_M$
入力は以下の条件を満たす。
$N$ 行出力せよ。
$i$ 行目には $\displaystyle \max_{s \in S_i} \mathrm{d} (i,s)$ を出力せよ。
2 1 1 1 1 2 2 2 1 2
3 0
2 2 1 1 1 2 2 2 1 2 2 1
3 3
6 6 0 8 0 2 3 0 2 5 0 4 3 0 4 5 0 6 0 0 1 3 2 3 3 5 5 4 4 2 4 6
14 7 9 5 7 0
10 7 -65870833 -68119923 -51337277 -59513976 -24997697 -46968492 -37069671 -90713666 -45043609 -31144219 43731960 -5258464 -27501033 90001758 13168637 -96651565 -67773915 56786711 44851572 -29156912 28758396 16384813 -79097935 7386228 88805434 -79256976 31470860 92682611 32019492 -87335887 6 7 7 9 6 5 1 2 2 4 4 1 9 8
192657310 138809442 0 192657310 0 270544279 99779950 0 96664294 0