/*
 * 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.awt.Point;
import java.util.LinkedList;
import java.util.Scanner;

/**
 *
 * @author cteam087
 */
public class Security {   
    
    public static void main(String[] args) {
        // TODO code application logic here                    
        Scanner sc = new Scanner(System.in);
        int N, Q;
        N = sc.nextInt();
        Q = sc.nextInt();
        sc.nextLine();
        LinkedList<Point> al = new LinkedList<>();
        LinkedList<Point> al2 = new LinkedList<>();
        LinkedList<Integer> al3 = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            al.add(new Point(sc.nextInt(), sc.nextInt()));
            sc.nextLine();
        }
        for (int i = 0; i < Q; i++) {
            al2.add(new Point(sc.nextInt(), sc.nextInt()));
            sc.nextLine();
        }
        int distanceX, distanceY;
        for (Point incident : al2) {
            for (Point guard : al) {                   
                distanceX = Math.abs(incident.x - guard.x);
                distanceY = Math.abs(incident.y - guard.y);                                                
                if(distanceX > distanceY){
                    al3.add(distanceX);                    
                }
                else al3.add(distanceY);                
            }                       
            
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < al3.size(); i++) {
                if (min > al3.get(i)) {
                    min = al3.get(i);
                }
            }
            System.out.println(min);
            al3.clear();
        }
    }
}