Demon's Cedar

Time Limit : 2 sec, Memory Limit : 262144 KB

L: スギ (Demon's Cedar)

月の瀬さんは悪魔らしいことをするため、街じゅうの樹木をスギの木に変えて、人々を花粉症で困らせることにした。

樹木は $N$ 種類存在する。$i$ 種類目の樹木の天界でのランクは $A_i$、魔界でのランクは $B_i$ である。また、$1$ 種類目の樹木はスギである。

月の瀬さんは、次の操作を何度でも行うことができる。

  • 天界で、種類 $i$ の樹木を種類 $j$ に変える。これには $|A_i - A_j|$ の時間がかかる。
  • 魔界で、種類 $i$ の樹木を種類 $j$ に変える。これには $|B_i - B_j|$ の時間がかかる。

天界と魔界の移動や、その他の行動に時間はかからない。

それぞれの樹木の種類について、スギの木に変えるためにかかる最短の時間を求めよ。

入力

1 行目に、$N$ が与えられる。

2 行目に、$A_1, A_2, A_3, \dots, A_N$ が空白区切りで与えられる。

3 行目に、$B_1, B_2, B_3, \dots, B_N$ が空白区切りで与えられる。

出力

$N$ 行のうち $i$ 行目には、$i$ 種類目の樹木をスギの木に変えるための時間の最小値を出力せよ。

制約

  • $N$ は $1$ 以上 $100 \ 000$ 以下の整数
  • $A_i, B_i$ は $1$ 以上 $1 \ 000 \ 000 \ 000$ 以下の整数

入力例1

3
1 2 5
6 3 4

出力例1

0
1
2

樹木 1 は元からスギの木なので、コストはかかりません。

樹木 2 を天界で樹木 1 に変えると、コストは $|A_1 - A_2| = |1 - 2| = 1$ です。

樹木 3 を魔界で樹木 2 に変えたのち、天界で樹木 1 に変えるとコストは $|B_3 - B_2| + |A_2 - A_1| = |4 - 3| + |1 - 2| = 2$ です。

入力例2

5
1 10 5 6 9
2 3 4 7 8

出力例2

0
1
2
3
2