import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;



public class Security {
    
    private static Integer[][] memo;
    
    public static void main(String[] args) throws FileNotFoundException {
        
//        Scanner sc = new Scanner(new File("input"));
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int Q = sc.nextInt();
        
        boolean[][] guards = new boolean[5001][5001];
        memo = new Integer[5001][5001];
        
        for (int i = 0; i < N; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            guards[x][y] = true;
        }
        
        for (int i = 0; i < Q; i++) {
            int incX = sc.nextInt();
            int incY = sc.nextInt();
            
            if (memo[incX][incY] != null) {
                System.out.println(memo[incX][incY]);
                continue;
            }
            
            boolean found = false;
            
            for (int dist = 0; dist < 5001; dist++) {
                
                for (int x = incX - dist; x <= incX + dist; x++) {
                    for (int y = incY - dist; y <= incY + dist; y++) {
                        if (isGuard(guards, x, y)) {
                            System.out.println(dist);
                            memo[x][y] = dist;
                            found = true;
                            break;
                        }
                        if (found) {
                            break;
                        }
                    }
                    if (found) {
                        break;
                    }
                }
                
                if (found) {
                    break;
                }
            }
        }
    }
    
    private static  int manDst(int[] guard, int x, int y) {
        
        if(guard[0] == x && guard[1] == y){
            return 0;
        }
        int diffX = Math.abs(guard[0] - x);
        int diffY = Math.abs(guard[1] - y);
        
        if (diffX < diffY) {
            return diffX + Math.abs(guard[1] - y) - diffX;
        } else {
            return diffY + Math.abs(guard[0] - x) - diffY;
        }
    }
    
    private static boolean isGuard(boolean[][] guards, int x, int y) {
        if (x <0 || y<0 || x > 5000 || y > 5000) {
            return false;
        }
        return guards[x][y];
    }
}