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())
    gi = [None for x in range(n + q)]
    for i in range(n):
        x, y = map(int, input("").split())
        gi[i] = ((x, y))
    for j in range(q):
        x, y = map(int, input("").split())
        gi[j+n] = ((x, y))

    for i in range(n, n+q):
        min_dist = dist(gi[i], gi[0])
        for j in range(1, n):
            if min_dist == 0:
                break
            tmp = dist(gi[i], gi[j])
            if tmp < min_dist:
                min_dist = tmp
        print(min_dist)