import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Security {
	
	static int atoi(String s) {
		return Integer.parseInt(s);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] parts;
		
		parts = br.readLine().split(" ");
		int N = atoi(parts[0]);
		int Q = atoi(parts[1]);
		int qx, qy, min;
		
		XY[] security = new XY[N];
		
		for (int i = 0; i < N; i++) {
			parts = br.readLine().split(" ");
			security[i] = new XY(atoi(parts[0]), atoi(parts[1]));
		}
		Arrays.sort(security);
		
		
		for (int i = 0; i < Q; i++) {
			parts = br.readLine().split(" ");
			qx = atoi(parts[0]);
			qy = atoi(parts[1]);
			
			int mid = binSearch(security, qx);
			
			min = Integer.MAX_VALUE;
		
			boolean goLeft = true;
			boolean goRight = true;
			
			
			for (int offset = 0; offset < security.length && (goLeft || goRight); offset++) {
				
				if (mid - offset < 0) 					goLeft = false;
				if (mid + offset >= security.length) 	goRight = false;
				
				if (goLeft) {
					XY left = security[mid - offset];
					
					int dl = dist(left.x, left.y, qx, qy);
					
					int dx = qx - left.x;
					if (dx > min) {
						goLeft = false;
					}
					
					if (dl < min) {
						min = dl;
					}
				}
				if (goRight) {
					XY right = security[mid + offset];
					
					int dr = dist(right.x, right.y, qx, qy);
					
					int dx = right.x - qx;
					
					if (dx > min) {
						goRight = false;
					}
					
					if (dr < min) {
						min = dr;
					}
				}
			}
			System.out.println(min);
		}
		
		
	}
	 
	public static int dist(int x1, int y1, int x2, int y2) {
		int dy = Math.abs(y2 - y1);
		int dx = Math.abs(x2 - x1);
		
		return Math.max(dx, dy);
	}
	
	private static int binSearch(XY[] arr, int x) {
		
		int from = 0;
		int to = arr.length-1;
		
		while(true) {
			int mid = (to+from)/2;
			if (arr[mid].x == x) {
				return mid;
			} else if(arr[mid].x > x) {
				to = mid - 1;
			} else {
				from = mid + 1;
			}
			
			if(from >= to) {
				return mid;
			}
		}
		
	}
	
	static class XY implements Comparable<XY> {
		public int x, y;

		public XY(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
		@Override
		public int compareTo(XY o) {
			return Integer.compare(this.x, o.x);
		}
	}
}