You are given n points on the straight line — the positions (x-coordinates) of the cities and m points on the same line — the positions (x-coordinates) of the cellular towers. All towers work in the same way — they provide cellular network for all cities, which are located at the distance which is no more than r from this tower.

Your task is to find minimal r that each city has been provided by cellular network, i.e. for each city there is at least one cellular tower at the distance which is no more than r.

If r = 0 then a tower provides cellular network only for the point where it is located. One tower can provide cellular network for any number of cities, but all these cities must be at the distance which is no more than r from this tower.


-----Input-----

The first line contains two positive integers n and m (1 ≤ n, m ≤ 10^5) — the number of cities and the number of cellular towers.

The second line contains a sequence of n integers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9) — the coordinates of cities. It is allowed that there are any number of cities in the same point. All coordinates a_{i} are given in non-decreasing order.

The third line contains a sequence of m integers b_1, b_2, ..., b_{m} ( - 10^9 ≤ b_{j} ≤ 10^9) — the coordinates of cellular towers. It is allowed that there are any number of towers in the same point. All coordinates b_{j} are given in non-decreasing order.


-----Output-----

Print minimal r so that each city will be covered by cellular network.


-----Examples-----
Input
3 2
-2 2 4
-3 0

Output
4

Input
5 3
1 5 10 14 17
4 11 15

Output
3

Difficulty: interview

Starter code:

Solutions:
from bisect import *

n, m = list(map(int, input().split()))
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

r = -1

a.sort()
b.sort()

for i in a:
	y = 1000000000000
	x = bisect_left(b, i)
	if (x >= 0) and (x < m):
		y = min(y, abs(i - b[x]))
	x += 1
	if (x >= 0) and (x < m):
		y = min(y, abs(i - b[x]))
	x -= 2
	if (x >= 0) and (x < m):
		y = min(y, abs(i - b[x]))
	r = max(r, y)

print(r)


line1=input().split()
n=int(line1[0])
m=int(line1[1])
cities=input().split()
towers=input().split()
for i in range (n):
    cities[i]=int(cities[i])
for i in range (m):
    towers[i]=int(towers[i])

worst=0
i=0

for city in cities:
    if m>1:
        while (city>towers[i+1] and i+2<m):
            i+=1
        a=abs(towers[i]-city)
        b=abs(towers[i+1]-city)
        this=min(a,b)
        worst=max(worst,this)
    else:
        worst=max(worst,abs(towers[0]-city))
print (worst)


n, m = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

class Zona:
    def __init__(self, vis, gran, t):
        self.v = vis
        self.gr = gran
        self.type = t
        self.towns = []
        
zones = []
zones.append(Zona(b[0], -10**9 - 1, 1))
for i in range(0, m - 1):
    gr = (b[i] + b[i+1]) / 2
    zones.append(Zona(b[i], gr, 2))
    zones.append(Zona(b[i+1], gr, 1))
    
zones.append(Zona(b[m - 1], 10**9 + 1, 2))

i = 0
for zone in zones:
    if zone.type == 1:
        while ((a[i] >= zone.gr) and (a[i] < zone.v)):
            zone.towns.append(a[i])
            i += 1
            if (i == n): break
    if zone.type == 2:
        while (a[i] >= zone.v) and (a[i] < zone.gr):
            zone.towns.append(a[i])
            i += 1
            if (i == n): break
    if (i == n): break
    
r = 0
for zone in zones:
    for town in zone.towns:
        dist = abs(zone.v - town)
        if (dist > r):
            r = dist
            
print(r)
    


import sys
r = lambda:sys.stdin.readline()

n,m = map(int,r().split())
nrr = [int(x) for x in r().split()]
mrr = [int(x) for x in r().split()]

lrr = []
rrr = []
pointer = 0
for x in mrr:
    while True:
        if(pointer==n):
            break
        if(nrr[pointer]<=x):
            rrr.append(x-nrr[pointer])
            pointer += 1
        else:
            break
for i in range(pointer,n):
    rrr.append(10**10)

pointer = n-1
for i in range(m-1,-1,-1):
    while True:
        if(pointer==-1):
            break
        if(mrr[i]<=nrr[pointer]):
            lrr.append(nrr[pointer]-mrr[i])
            pointer -= 1
        else:
            break
for i in range(pointer,-1,-1):
    lrr.append(10**10)
srr = [min(lrr[i],rrr[n-i-1]) for i in range(n)]
print(max(srr))

def lower_bownd(key):
    left = -1
    right = m
    while left < right - 1:
        middle = (left + right) // 2
        if b[middle] <= key:
            left = middle
        else:
            right = middle
    
    if right < m:
        r = b[right] - key
    else:
        r = INF
    if left > -1:
        l = key - b[left]
    else:
        l = INF
    return min(l, r)


n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = [0] * n
INF = 10 ** 10
for i in range(n):
    ans[i] = lower_bownd(a[i])
print(max(ans))

def min_dist_to_tower(a, x):
    l, r = -1, len(a)
    while r - l > 1:
        m = (l + r) // 2
        if a[m] > x:
            r = m
        else:
            l = m
    w = abs(x - a[l]) if l >= 0 else 'SORRY'
    z = abs(x - a[r]) if r < len(a) else 'SORRY'
    if w != 'SORRY' and z != 'SORRY':
        return min(w, z)
    elif w == 'SORRY':
        return z
    else:
        return w



n, m = map(int, input().split())
houses = list(map(int, input().split()))
towers = list(map(int, input().split()))

dist = 0
for i in range(len(houses)):
    if min_dist_to_tower(towers, houses[i]) > dist:
        dist = min_dist_to_tower(towers, houses[i])

print(dist)

from sys import stdin, stdout
n, m = map(int, stdin.readline().split())
hcoordinate = list(map(int, stdin.readline().split()))
tcoordinate = list(map(int, stdin.readline().split()))
l = -1
r = max(abs(tcoordinate[-1] - hcoordinate[-1]), abs(tcoordinate[-1] - hcoordinate[0]))


while r > l + 1:
    t = (r + l) // 2
    i, j = 0, 0
    while i < n and j < m:
        if abs(hcoordinate[i] - tcoordinate[j]) <= t:
            i += 1
        else:
            j += 1
            
    if i == n:
        r = t
    else:
        l = t


stdout.write(str(r))

t = input
p = print
r = range
n, m = map(int, t().split())
a = list(map(int, t().split()))
b = list(map(int, t().split()))
ans = 0
i = 0
for j in a:
    while i < m - 1 and abs(j - b[i]) >= abs(j - b[i + 1]):
        i += 1
    ans = max(ans, abs(j - b[i]))
p(ans)

import bisect

n,m = map(int,input().split())
C=sorted(list(set(map(int,input().split()))))
T=sorted(list(set(map(int,input().split()))))

r=0
for x in C:
	ind=bisect.bisect_left(T,x)
	if(ind==len(T) or T[ind] != x):
		if ind==0:
			r=max(r,T[ind]-x)
		elif ind==len(T):
			r=max(r,x-T[ind-1])
		else:
			r=max(r,min(T[ind]-x,x-T[ind-1]))
print(r)

import bisect

x = list(map(int, input().split()))
gor = sorted(list(set(map(int, input().split()))))
vysh = sorted(list(set(map(int, input().split()))))

r = 0

for x in gor:
    vh = bisect.bisect_left(vysh, x)

    if (vh == len(vysh) or vysh[vh] != x):
        if vh == 0:
            r = max(r, vysh[vh] - x)
        elif vh == len(vysh):
            r = max(r, x - vysh[vh - 1])
        else:
            r = max(r, min(vysh[vh] - x, x - vysh[vh - 1]))

print(r)


n,m = map(int,input().split())
c = list(map(int,input().split()))
t = list(map(int,input().split()))
i = 0
ans = 0
for x in c:
    while i < m- 1 and abs(x-t[i]) >=  abs(x - t[i+1]):
        i+=1
    ans = max(ans,abs(x-t[i]))
print(ans)

n,m=[int(i) for i in input().strip().split()]
c=[int(i) for i in input().strip().split()]
t=[int(i) for i in input().strip().split()]

ci=0
ti=0
ans=0

while ci<n:
  if ti==m-1:
    ans=max(ans,abs(t[-1]-c[ci]),abs(t[-1]-c[-1]))
    break
  while ti<=m-2:
    if abs(t[ti]-c[ci])>=abs(t[ti+1]-c[ci]):
      ti+=1
    else:
      break
  ans=max(ans,abs(t[ti]-c[ci]))
  ci+=1
print(ans)


n, m = (int(t) for t in input().split())
city = [int(t) for t in input().split()]
tower = [int(t) for t in input().split()]

def check(city, tower, r):
    t = 0
    c = 0
    while c < len(city):
        if abs(city[c] - tower[t]) > r:
            #Current tower is too far
            t += 1
            if t == len(tower):
                #Ran out of towers
                return False
        else:
            c += 1
    return True

hi = 2 * (10 ** 9)
lo = 0
out = hi 
while hi >= lo:
    mid = (hi + lo) // 2
    if check(city, tower, mid):
        out = mid
        hi = mid - 1
    else:
        lo = mid + 1

print(out)

n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
b.append(b[m-1])
p=0
r=0
for i in range(n):
	while p+2<len(b) and abs(a[i]-b[p]) >= abs(a[i]-b[p+1]): p+=1
	mn=min(abs(a[i]-b[p]),abs(a[i]-b[p+1]))
	r=max(r,mn)
print(r)

def UpperBound(A, key):
   left = -1
   right = len(A)
   while right > left + 1:
      middle = (left + right) // 2
      if A[middle] > key:
         right = middle
      else:
         left = middle
   return right

def LowerBound(A, key):
   left = -1
   right = len(A)
   while right > left + 1:
      middle = (left + right) // 2
      if A[middle] >= key:
         right = middle
      else:
         left = middle
   return right


n, m = map(int, input().split())
N = list(map(int, input().split()))
M = list(map(int, input().split()))   
INF = 10**9

dist = [INF] * (n)
min_dist = 0

for i in range(n):
   l = LowerBound(M, N[i]) 
   if l > len(M) - 1:
      l = len(M) - 1

   d1 = abs(N[i] - M[l])
   #print(d1)
   if 0 < l:
      d2 = abs(N[i] - M[l - 1])
      #print(d2)
   else:
      d2 = d1
   dist[i] = min(d1,d2)

print(max(dist))

def main():
    from bisect import bisect_left
    n, m = list(map(int, input().split()))
    aa = list(map(int, input().split()))
    bb = -10 ** 10, *list(map(int, input().split())), 10 ** 10
    rr = [bb[bisect_left(bb, a)] - a for a in aa]
    bb = [-b for b in reversed(bb)]
    rr.reverse()
    aa.reverse()
    for i, r, a in zip(list(range(n)), rr, aa):
        x = bb[bisect_left(bb, -a)] + a
        if r > x:
            rr[i] = x
    print(max(rr))


def __starting_point():
    main()

__starting_point()

def main():
    from bisect import bisect_left
    input()
    aa = list(map(int, input().split()))
    bb = -10 ** 10, *list(map(int, input().split())), 10 ** 10
    for i, a in enumerate(aa):
        j = bisect_left(bb, a)
        u, v = bb[j] - a, a - bb[j - 1]
        aa[i] = u if u < v else v
    print(max(aa))


def __starting_point():
    main()

__starting_point()

n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

def lower_bound(x) :
    bl = 0
    br = m - 1
    while br - bl > 1 :
        bm = (bl + br) // 2
        if b[bm] >= x : br = bm
        else : bl = bm + 1
    if b[bl] >= x : return bl
    elif b[br] >= x : return br
    else : return m

def upper_bound(x) :
    bl = 0
    br = m - 1
    while br - bl > 1 :
        bm = (bl + br) // 2
        if b[bm] > x : br = bm
        else : bl = bm + 1
    if b[bl] > x : return bl
    elif b[br] > x : return br
    else : return m

res = 0

for i in range(n) :
    pos = lower_bound(a[i])
    tmp = 2 * (10 ** 9) + 1
    if pos < m and tmp > b[pos] - a[i] :
        tmp = b[pos] - a[i]
    pos = upper_bound(a[i]) - 1
    if pos >= 0 and tmp > a[i] - b[pos] :
        tmp = a[i] - b[pos]
    if tmp > res : res = tmp
print(res)


n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

def lower_bound(x) :
    bl = 0
    br = m - 1
    while br - bl > 1 :
        bm = (bl + br) // 2
        if b[bm] >= x : br = bm
        else : bl = bm + 1
    if b[bl] >= x : return bl
    elif b[br] >= x : return br
    else : return m

res = 0

for i in range(n) :
    pos = lower_bound(a[i])
    tmp = 2 * (10 ** 9) + 1
    if pos < m and tmp > b[pos] - a[i] :
        tmp = b[pos] - a[i]
    pos = lower_bound(a[i] + 1) - 1
    if pos >= 0 and tmp > a[i] - b[pos] :
        tmp = a[i] - b[pos]
    if tmp > res : res = tmp
print(res)


import math
line = input().split()
n = int(line[0])
m = int(line[1])
inhabited_localities = [int(x) for x in input().split()]
columns = [int(x) for x in input().split()]
max_distance = 0
current_distanse = 0
j = 0
for i in inhabited_localities:
	while j<m-1 and i>columns[j]:
		j+=1
	if j!=0:
		current_distanse = min(abs(columns[j]-i), abs(columns[j-1]-i))
	else:
		current_distanse = abs(columns[j]-i)
	if max_distance<current_distanse:
		max_distance = current_distanse
print (max_distance)

n, m = list(map(int, input().split()))

x = list(map(int, input().split()))
y = list(map(int, input().split()))

ans = -1

if m == 1:
    for i in x:
        if abs(i-y[0]) > ans:
            ans = abs(i - y[0])
else:
    c = 0
    p = 0
    q = 1
    while c != n:
        #print("city %d" %(c))
        if (y[p] <= x[c]) and (y[q] >= x[c]):
            #print("city in between tower %d and %d" %(p, q))
            ans = max(ans, min((y[q]-x[c]), (x[c]-y[p])))
            c += 1
        elif y[q] < x[c]:
            #print("tower q %d lower than city" %q)
            if q != m-1:
                #print("increase tower")
                p += 1
                q += 1
            else:
                #print("no more tower")
                ans = max(ans, x[c] - y[q])
                c += 1
        elif y[p] > x[c]:
            #print("tower p %d higher than city" %p)
            ans = max(ans, y[p] - x[c])
            c += 1

print(ans)


import bisect


def read():
    return [int(x) for x in input().split()]


def main():
    n, m = read()
    a = read()
    b = read()

    res = 0
    for i in range(0, n):
        cover_left = -1
        bi = bisect.bisect_left(b, a[i])
        if bi != m and b[bi] == a[i]:
            cover_left = 0
        elif bi:
            cover_left = a[i] - b[bi - 1]

        cover_right = -1
        bi = bisect.bisect_right(b, a[i])
        if bi != m:
            cover_right = b[bi] - a[i]
        if cover_left != -1 and cover_right != -1:
            res = max(res, min(cover_left, cover_right))
        elif cover_right != -1:
            res = max(res, cover_right)
        else:
            res = max(res, cover_left)

    print(res)

main()

import bisect


def read():
    return [int(x) for x in input().split()]


def main():
    n, m = read()
    a = read()
    b = read()

    res = 0
    for i in range(0, n):
        # cover from left
        cover_left = -1
        bi = bisect.bisect_left(b, a[i])
        if bi != m and b[bi] == a[i]:
            cover_left = 0
        elif bi:
            cover_left = a[i] - b[bi - 1]

        # cover from right
        cover_right = -1
        bi = bisect.bisect_right(b, a[i])
        if bi != m:
            cover_right = b[bi] - a[i]

        if cover_left != -1 and cover_right != -1:
            res = max(res, min(cover_left, cover_right))
        elif cover_right != -1:
            res = max(res, cover_right)
        else:
            res = max(res, cover_left)

    print(res)

main()

#!/usr/bin/env	python
#-*-coding:utf-8 -*-
n,m=list(map(int,input().split()))
A=list(map(int,input().split()))
B=tuple(map(int,input().split()))
s=i=0
for c in A:
	while m>i and c>B[i]:i+=1
	n=c-B[i-1]if i else 0x7fffffff
	if m>i:n=min(n,B[i]-c)
	s=max(s,n)
print(s)


k=0
i=0
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))
for j in a:
    if m>1:
        while (j>b[i+1] and i+2<m):
            i+=1
        w=abs(b[i]-j)
        e=abs(b[i+1]-j)
        k1=min(w,e)
        k=max(k,k1)
    else:
        k=max(k,abs(b[0]-j))
print(k)