B - 最寄りの避難所 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 333 点

問題文

高橋君の住む街には、東西に伸びる 1 本の大通りがあります。この大通りは数直線とみなすことができ、西側が座標の小さい方向、東側が座標の大きい方向に対応します。

この大通り上には N 軒の家が建っており、西側から順に家 1 , 家 2 , \ldots , 家 N と番号が振られています。家 i は座標 X_i の位置にあり、どの 2 軒の家も異なる位置に建っています（ X_1 < X_2 < \cdots < X_N ）。

また、この大通り上には M 箇所の避難所が設置されており、西側から順に避難所 1 , 避難所 2 , \ldots , 避難所 M と番号が振られています。避難所 j は座標 P_j の位置にあり、どの 2 箇所の避難所も異なる位置に設置されています（ P_1 < P_2 < \cdots < P_M ）。

なお、家の座標と避難所の座標が一致する場合もあります。

市の防災担当である高橋君は、災害時に各家の住民が最も近い避難所へ避難できるよう、それぞれの家から最も近い避難所までの距離を調べることにしました。ここで、座標 a の地点から座標 b の地点までの距離は |a - b| で表されます。

各家 i （ 1 \leq i \leq N ）について、家 i から最も近い避難所までの距離、すなわち \displaystyle \min_{1 \leq j \leq M} |X_i - P_j| を求めてください。最も近い避難所が複数ある場合でも、距離は一意に定まります。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq X_i \leq 10^9 （ 1 \leq i \leq N ）
  • 0 \leq P_j \leq 10^9 （ 1 \leq j \leq M ）
  • X_1 < X_2 < \cdots < X_N
  • P_1 < P_2 < \cdots < P_M
  • 入力はすべて整数である

入力

N M
X_1 X_2 \ldots X_N
P_1 P_2 \ldots P_M
  • 1 行目には、家の軒数を表す整数 N と、避難所の箇所数を表す整数 M が、空白区切りで与えられる。
  • 2 行目には、各家の座標を表す整数 X_1, X_2, \ldots, X_N が、空白区切りで与えられる。
  • 3 行目には、各避難所の座標を表す整数 P_1, P_2, \ldots, P_M が、空白区切りで与えられる。

出力

N 行にわたって出力せよ。 i 行目（ 1 \leq i \leq N ）には、家 i から最も近い避難所までの距離を整数で出力せよ。

入力例 1

3 2
1 5 9
3 8

出力例 1

2
2
1

入力例 2

5 3
2 10 25 40 60
5 30 50

出力例 2

3
5
5
10
10

入力例 3

10 4
3 15 27 48 55 72 88 100 130 200
10 50 90 150

出力例 3

7
5
17
2
5
18
2
10
20
50

Score : 333 pts

Problem Statement

In the town where Takahashi lives, there is a single main street running from east to west. This main street can be regarded as a number line, where the west side corresponds to the direction of smaller coordinates and the east side corresponds to the direction of larger coordinates.

There are N houses built along this main street, numbered house 1, house 2, \ldots, house N from west to east. House i is located at coordinate X_i, and no two houses are built at the same position (X_1 < X_2 < \cdots < X_N).

There are also M shelters set up along this main street, numbered shelter 1, shelter 2, \ldots, shelter M from west to east. Shelter j is located at coordinate P_j, and no two shelters are set up at the same position (P_1 < P_2 < \cdots < P_M).

Note that a house and a shelter may be located at the same coordinate.

Takahashi, who is in charge of disaster prevention for the city, decided to determine the distance from each house to its nearest shelter so that residents of each house can evacuate to the nearest shelter in case of a disaster. Here, the distance from a point at coordinate a to a point at coordinate b is given by |a - b|.

For each house i (1 \leq i \leq N), find the distance from house i to the nearest shelter, that is, \displaystyle \min_{1 \leq j \leq M} |X_i - P_j|. Even if there are multiple nearest shelters, the distance is uniquely determined.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq X_i \leq 10^9 (1 \leq i \leq N)
  • 0 \leq P_j \leq 10^9 (1 \leq j \leq M)
  • X_1 < X_2 < \cdots < X_N
  • P_1 < P_2 < \cdots < P_M
  • All inputs are integers

Input

N M
X_1 X_2 \ldots X_N
P_1 P_2 \ldots P_M
  • The first line contains an integer N representing the number of houses and an integer M representing the number of shelters, separated by a space.
  • The second line contains integers X_1, X_2, \ldots, X_N representing the coordinates of each house, separated by spaces.
  • The third line contains integers P_1, P_2, \ldots, P_M representing the coordinates of each shelter, separated by spaces.

Output

Print N lines. On the i-th line (1 \leq i \leq N), print the distance from house i to its nearest shelter as an integer.

Sample Input 1

3 2
1 5 9
3 8

Sample Output 1

2
2
1

Sample Input 2

5 3
2 10 25 40 60
5 30 50

Sample Output 2

3
5
5
10
10

Sample Input 3

10 4
3 15 27 48 55 72 88 100 130 200
10 50 90 150

Sample Output 3

7
5
17
2
5
18
2
10
20
50