import sys

def dist(x, y, gx, gy):
	return max(abs(gx - x),abs(gy - y)) 

n, q = list(map(int, sys.stdin.readline().split(" ")))
guards = []

for i in range(n):
	guards.append(list(map(int, sys.stdin.readline().split(" "))))


for i in range(q):
	steps = 5001
	x, y = list(map(int, sys.stdin.readline().split(" ")))
	for g in guards:
		tmp = dist(x, y, g[0], g[1])
		if (tmp < steps):
			steps = tmp
		if (steps == 0):
			break;
	print(steps)