def dist(inc, g):
    return max(abs(inc[0] - g[0]), abs(inc[1] - g[1]))


if __name__ == "__main__":
    n, q = map(int, input("").split())
    guards = []
    incidents = []
    for _ in range(n):
        x, y = map(int, input("").split())
        guards.append((x, y))
    for _ in range(q):
        x, y = map(int, input("").split())
        incidents.append((x, y))

    for inc in incidents:
        min_dist = dist(inc, guards[0])
        for j in range(1, len(guards)):
            if min_dist == 0:
                break
            tmp = dist(inc, guards[j])
            if tmp < min_dist:
                min_dist = tmp
        print(min_dist)