import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;



public class Security {

    
    public static void main(String[] args) {
        
//        Scanner sc = new Scanner(new File("input"));
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int Q = sc.nextInt();
        
        List<int[]> guards = new ArrayList<>(N);
        
        for (int i = 0; i < N; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            guards.add(new int[]{x, y});
        }
        
        for (int i = 0; i < Q; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int min = Integer.MAX_VALUE;
            for (int[] guard : guards) {
                final int dist = manDst(guard, x, y);
                if (dist < min) {
                    min = dist;
                }
            }
            System.out.println(min);
        }
    }
    
    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;
        }
    }
}