#!/usr/bin/env python3

if __name__ == '__main__':
    guards = list()
    incidents = list()
    outputs = list()

    line0 = [int(i) for i in input().split()]

    for i in range(line0[0]):
        guards.append(
            [int(i) for i in input().split()]
        )

    for i in range(line0[1]):
        inc = [int(i) for i in input().split()]
        shortest_dist = None
        for g in guards:
            dist = max( abs(inc[0] - g[0]), abs(inc[1] - g[1]) )
            if shortest_dist is None or dist < shortest_dist:
                shortest_dist = dist
        outputs.append(str(round(shortest_dist)))

    print("\n".join(outputs))