/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package security;

import static java.lang.Integer.max;
import java.util.Scanner;

/**
 *
 * @author boban3
 */
public class Security {

    public static void main(String[] args) {
        Scanner skener = new Scanner(System.in);
        int pocetG = skener.nextInt();
        int pocetI = skener.nextInt();
        int[] gX = new int[pocetG];
        int[] gY = new int[pocetG];
        for (int i = 0; i < pocetG; i++) {
            gX[i] = skener.nextInt();
            gY[i] = skener.nextInt();
        }
        int[] vysledky = new int[pocetI]; 
        for (int i = 0; i < pocetI; i++) {
            int iX = skener.nextInt();
            int iY = skener.nextInt();
            int vysledok = Integer.MAX_VALUE;
            for (int j = 0; j < pocetG; j++) {
                int cisloX = Math.abs(iX - gX[j]);
                int cisloY = Math.abs(iY - gY[j]);
                int vacsie = max(cisloX, cisloY);
                if (vacsie < vysledok) {
                    vysledok = vacsie;
                }
            }
            vysledky[i] = vysledok;
        }
        for (int i = 0; i < pocetI; i++) {
            System.out.println(vysledky[i]);
        }
    }
}
// 2 3 0 1 4 0 5 0 4 3 1 2