/*
 * 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.
 */

/* 
 * File:   main.c
 * Author: tym7
 *
 * Created on October 20, 2018, 10:58 AM
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct Point{
    int x;
    int y;
};
/*
 * 
 */
int main(int argc, char** argv) {
    int n_guards,n_incidents,distance,s_dist;
    int in = 0;
    struct Point *guards,*incidents;
 
    in = scanf("%d %d",&n_guards,&n_incidents);
    
    guards = calloc(n_guards,sizeof(struct Point));
    incidents = calloc(n_incidents,sizeof(struct Point));
    
    for(int i = 0;i<n_guards;++i){
        in = scanf(" %d %d",&(guards+i)->x,&(guards+i)->y);
    }
    for(int i = 0;i<n_incidents;++i){
        in = scanf(" %d %d",&(incidents+i)->x,&(incidents+i)->y);
    }
    //scout = malloc()
    for(int j = 0;j<n_incidents;++j){
        s_dist = 10001;
        int a = (incidents+j)->x;
        int b = (incidents+j)->y;
        for(int i = 0;i<n_guards;++i){
            //if(((guards+i)->x == (incidents+j)->x) && ((guards+i)->y == (incidents+j)->y)) { s_dist = 0; break; }
            int xdif = abs(((guards+i)->x)-a);
            int ydif = abs(((guards+i)->y)-b);
            distance = abs(xdif - ydif) + (xdif>ydif?ydif:xdif);
            if(distance==0){
                s_dist = distance;
                break;
            }
            if(distance<s_dist)s_dist = distance;
        }
        printf("%d\n",s_dist);
    }
    free(guards);
    free(incidents);
    return (EXIT_SUCCESS);
}