line = [int(x) for x in input().split(" ")]
orok = []
esetek = []

for x in range(line[0]):
	line2 = [int(x) for x in input().split(" ")]
	orok.append({"x":line2[0],"y":line2[1]})
	
for x in range(line[1]):
	line2 = [int(x) for x in input().split(" ")]
	esetek.append({"x":line2[0],"y":line2[1]})


distance = [int()]

for j in esetek:
	min_distance = [10000000]
	for n in orok:
		
		if abs(j["x"] - n["x"]) >= abs(j["y"] - n["y"]):
			distance[0] = abs(n["x"] - j["x"])
			
		else:
			distance[0] = abs(n["y"] - j["y"])

	
		

		if distance[0] < min_distance[0]:
			min_distance = distance.copy()
		
	
	
	
	print(min_distance[0])