#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10, M = 3e3+2, OO = 0x3f3f3f3f;
int t, n, u, v, c,q;
int vis[N];
vector<int>vi;
int bs(int x,vector<int>v){
    int low=0,high=v.size()-1,med;
    while(low<high){
        med=(low+high+1)/2;
        if(v[med]<=x) low=med;
        else high=med-1;

    }
    return v[low];
}
int main(){
    cin>>t;
    while(t--){
    	int maxi=0;
        vector<int>v;
        cin>>n>>q;
        for(int i=0;i<n;++i){
            int x,y; cin>>x>>y;
            v.push_back(x);
            //mp[{x,y}]=1;
            maxi=max(maxi,x);
        }
        
        sort(v.begin(),v.end());
        while(q--){
        	int x,y,nx,ny; cin>>x>>y>>nx>>ny;
        	if(n==0){
        		cout<<abs(nx-x) <<"\n";
        		continue;
        	}
            ll ans=0;
            
            int dis1=abs((*lower_bound(v.begin(),v.end(),x)));
            int dis2=abs(bs(x,v)-x);
           // cout<<dis2<<" ";
            ans+=min(dis1,dis2);
            //cout<<ans;
            dis1=abs((*lower_bound(v.begin(),v.end(),nx))-nx);
            //cout<<dis1<<" ";
            dis2=abs(bs(nx,v)-nx);
            //cout<<dis2;
            ans+=min(dis1,dis2);
            cout<<min((ll)abs(nx-x),ans)<<"\n";
        }

    }

}