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 = []
    closest = []
    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_ = 0
        min_dist = dist(inc, guards[min_])
        for j in range(1, len(guards)):
            print("min_dist", min_dist)
            tmp = dist(inc, guards[j])
            print("tmp", tmp)
            if tmp < min_dist:
                min_ = j
                min_dist = tmp
        closest.append(min_dist)

    for c in closest:
        print(c)