#include<bits/stdc++.h>
using namespace std;
constexpr int M=1e5+5;int n,q,ans[M];
vector<tuple<int,int,int>>upd,qry;
void solve(vector<tuple<int,int,int>>&upd,vector<tuple<int,int,int>>&qry,int ql,int qr){
    if (upd.empty()||qry.empty()||ql>qr) return;
    int mid=ql+qr>>1;
    vector<tuple<int,int,int>>updl,updr,qryl,qryr;
    int res[4]={-INT_MAX,-INT_MAX,-INT_MAX,-INT_MAX};
    for (auto [w,x,y]:upd){
        if (w>=mid){
            res[0]=max(res[0],x+y);
            res[1]=max(res[1],x-y);
            res[2]=max(res[2],y-x);
            res[3]=max(res[3],-x-y);
        }
        if (w<=mid) updl.emplace_back(w,x,y);
        else updr.emplace_back(w,x,y);
    }
    for (auto [x,y,id]:qry){
        if (res[0]==-INT_MAX) {qryl.emplace_back(x,y,id);continue;} 
        int tmp=max({-x-y+res[0],y-x+res[1],x-y+res[2],x+y+res[3]});
        ans[id]=max(ans[id],min(tmp,mid));
        if (tmp<=mid) qryl.emplace_back(x,y,id);
        else qryr.emplace_back(x,y,id);
    }
    solve(updl,qryl,ql,mid-1);
    solve(updr,qryr,mid+1,qr);
}
void solve(){
    cin>>n>>q;upd.clear();qry.clear();
    for (int i=1;i<=n;i++){
        int x,y,w;cin>>x>>y>>w;
        upd.emplace_back(w,x,y);
    }
    for (int i=1;i<=q;i++){
        int x,y;cin>>x>>y;ans[i]=0;
        qry.emplace_back(x,y,i);
    }
    solve(upd,qry,0,1e9);
    for (int i=1;i<=q;i++)
        printf("%d\n",ans[i]);
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T;cin>>T;while (T--) solve();return 0;
}