もっとも近い避難所は

• 自分より左側にあって、かつもっとも右にあるもの
• 自分と同じ or より右側にあって、かつもっとも左にあるもの

のどちらかです。

そのようなものを効率的に求める方法として二分探索があります。

上の条件であれば、bisect_left や lower_bound で求めることができます。具体的には「昇順に整列された配列 \(A\) から \(X \le A_i\) を満たすような最小の \(i\) の index（ポインタ）」を返しますから、後者がわかります。

「同じ」を後者ではなくて、前者に含めても成立し、この場合は bisect_right や upper_bound で同様に後者が求まります。

ということで、実装上はどちらでも良いです。

実装例

番兵をもちいると、多少実装が楽になります。

from bisect import bisect_left
inf = 1 << 60

n, m = map(int, input().split())
x = list(map(int, input().split()))
p = [-inf] + list(map(int, input().split())) + [inf]

for i in range(n):
    j = bisect_left(p, x[i])
    print(min(x[i] - p[j-1], p[j] - x[i]))