// Arup Guha
// 3/26/2024
// Solution to 2024 USACO Bronze Problem: Walking Along a Fence

import java.util.*;
import java.io.*;

public class walkfence {

	public static void main(String[] args) throws Exception {
	
		FastScanner stdin = new FastScanner(System.in);
		int n = stdin.nextInt();
		int nPosts = stdin.nextInt();
		
		// locs[x][y] will store the time when someone walking around the fence would get to x,y.
		int[][] locs = new int[1001][1001];
		for (int i=0; i<=1000; i++)
			Arrays.fill(locs[i], -1);
			
		// Just read these in.
		int[][] pts = new int[nPosts][2];
		for (int i=0; i<nPosts; i++)
			for (int j=0; j<2; j++)
				pts[i][j] = stdin.nextInt();
				
		int t = 0;
		
		// Move through each pair of adjacent posts.
		for (int i=0; i<nPosts; i++) {
			int next = (i+1)%nPosts;
			
			// How many steps we'll take.
			int steps = Math.abs(pts[i][0]-pts[next][0]) + Math.abs(pts[i][1]-pts[next][1]);
			
			// Direction we're moving.
			int dx = 0, dy = 0;
			int x = pts[i][0], y = pts[i][1];
			if (pts[next][0] != pts[i][0]) dx = (pts[next][0] - pts[i][0])/Math.abs(pts[i][0]-pts[next][0]);
			if (pts[next][1] != pts[i][1]) dy = (pts[next][1] - pts[i][1])/Math.abs(pts[i][1]-pts[next][1]);
			
			// Walk in the direction, filling in time steps.
			for (int z=0; z<steps; z++) {
				locs[x][y] = t++;
				x += dx;
				y += dy;
			}
		}
		
		// Collate answers to all queries.
		StringBuffer sb = new StringBuffer();
		for (int i=0; i<n; i++) {
		
			// Get two locations.
			int x1 = stdin.nextInt();
			int y1 = stdin.nextInt();
			int x2 = stdin.nextInt();
			int y2 = stdin.nextInt();
			
			// Find time difference.
			int d = Math.abs(locs[x1][y1]-locs[x2][y2]);
			
			// This is walking the opposite way.
			d = Math.min(d, t - d);
			
			sb.append(d+"\n");
		}
		
		// Ta da!
		System.out.print(sb);
	}
}

class FastScanner {
    BufferedReader br;
    StringTokenizer st;
	
    public FastScanner(InputStream i) {
        br = new BufferedReader(new InputStreamReader(i));
        st = new StringTokenizer("");
    }
			
    public String next() throws IOException {
        if(st.hasMoreTokens())
            return st.nextToken();
        else
            st = new StringTokenizer(br.readLine());
        return next();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    //#
    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}