/*
 * 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 java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

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

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer row1 = new StringTokenizer(in.readLine());
        int numg = Integer.parseInt(row1.nextToken());
        int numi = Integer.parseInt(row1.nextToken()); 
        int[] guardsX = new int[numg];
        int[] guardsY = new int[numg];
        int[] inciX = new int[numi];
        int[] inciY = new int[numi];
        for (int i = 0; i<numg; i++){
            row1 = new StringTokenizer(in.readLine());
            guardsX[i] = (Integer.parseInt(row1.nextToken()));
            guardsY[i] = (Integer.parseInt(row1.nextToken()));
        }
        for (int i = 0; i<numi; i++){
            row1 = new StringTokenizer(in.readLine());
            inciX[i] = (Integer.parseInt(row1.nextToken()));
            inciY[i] = (Integer.parseInt(row1.nextToken()));
        }
        int dis = 0;
        for (int i =0; i<numi; i++){
            int best = 5000;
            for (int j=0; j<numg; j++){
                dis = dist(guardsX[j],guardsY[j],inciX[i],inciY[i]);
                best = best < dis ? best : dis ;
                //System.out.println(dis);
            }
            System.out.println(best);
        }
    }
    
    static int dist(int x, int y, int tx, int ty){
        return Math.max(Math.abs(x-tx), Math.abs(ty-y));
    }
    
}