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 = [[False for y in range(5001)] for x in range(5001)]

for i in range(n):
	a, b = list(map(int, sys.stdin.readline().split(" ")))
	guards[a][b] = True

def horizontal(x, y, j):
	top = max(0, y - j)
	bot = min(5000, y + j)
	for d in range(max(0, x - j), min(x+j + 1, 5001)):
		if guards[d][top] == True:
			return dist(x, y, d, top)  
		if guards[d][bot] == True:
			return dist(x, y, d, bot)
	return -1

	

for i in range(q):
	x, y = list(map(int, sys.stdin.readline().split(" ")))
	for j in range(5001):
		ret = horizontal(x, y, j)
		if (ret != -1):
			print(ret)
			break
		ret = horizontal(y, x, j)
		if (ret != -1):
			print(ret)
			break