LG4073

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long
#define db double

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=2e5+7;
const db eps=1e-6;

struct Point{
    //这里坐标都是原来的两倍
    //这样就可以用int储存了
    int x,y;

    Point(){}
    Point(int x,int y):x(x),y(y){}
};

#define Vec Point

inline Vec operator -(const Vec &a,const Vec &b){
    return Vec(a.x-b.x,a.y-b.y);
}

inline ll Cross(const Vec &a,const Vec &b){
    return (ll)a.x*b.y-(ll)a.y*b.x;
}

inline db Angle(const Vec &a){
    return atan2(a.y,a.x);
}

int n,m,q;

namespace Graph{

    Point P[N];

    struct Edge{
        int u,v,w;
        db angle;
        Edge(){}
        Edge(int u,int v,int w):u(u),v(v),w(w),angle(Angle(P[v]-P[u])){}
    };

    int tot,OUT;
    int ecnt=1;
    Edge E[N];
    int ID[N];
    int nex[N];
    vector<int>G[N];

    inline void addedge(int u,int v,int w){
        E[++ecnt]=Edge(u,v,w),G[u].push_back(ecnt);
        E[++ecnt]=Edge(v,u,w),G[v].push_back(ecnt);
    }

    inline bool cmp(const int &a,const int &b){
        return E[a].angle<E[b].angle;
    }

    inline void work(){
        r(n),r(m);
        for(int i=1;i<=n;++i){
            int x,y;r(x),r(y);
            P[i]=Point(x*2,y*2);
        }
        for(int i=1;i<=m;++i){
            int u,v,w;
            r(u),r(v),r(w);
            addedge(u,v,w);
        }
        //极角排序
        //ID表示排名
        for(int i=1;i<=n;++i){
            sort(G[i].begin(),G[i].end(),cmp);
            for(int j=1;j<G[i].size();++j){
                ID[G[i][j]]=j;
            }
        }
        //nex表示下一条该走哪条
        //就是其反向边的前一条
        for(int i=2;i<=ecnt;++i){
            int x=E[i].v;
            if(ID[i^1])nex[i]=G[x][ID[i^1]-1];
            else nex[i]=G[x][G[x].size()-1];
        }
        //ID现在表示所属区域
        for(int i=2;i<=ecnt;++i)ID[i]=0;
        for(int i=2;i<=ecnt;++i){
            if(!ID[i]){
                ID[i]=++tot;
                ll Area=0;
                for(int j=nex[i];j!=i;j=nex[j]){
                    ID[j]=tot;
                    Area+=Cross(P[E[i].u]-P[E[j].u],P[E[i].u]-P[E[j].v]);
                }
                //无穷大区域面积为负
                if(Area<0)OUT=tot;
            }
        }
    }
}

namespace Local{

    struct Node{
        int id;
        Point A;
        inline Node(){}
        inline Node(const int &id,const Point &A):id(id),A(A){}
        inline bool operator <(const Node &x)const {
            return (A.x==x.A.x)?id<x.id:A.x<x.A.x;
        }
    };

    inline bool cmp(const Node &a,const Node &b){
        return a.id<b.id;
    }

    int NOW;
    struct Info{
        int id;
        db k,b;
        int x,y;
        inline Info(){}
        inline Info(const int &id,const Point &A,const Point &B):id(id){
            x=A.x;
            y=A.y;
            k=(db)(A.y-B.y)/(A.x-B.x);
            b=y-k*x;
        }

        inline db f()const {
            return k*NOW+b;
        }
        //先按高低排再按斜率排
        inline bool operator < (const Info &A)const {
            db t=f()-A.f();
            if(fabs(t)<eps)return k<A.k;
            return t<0;
        }
    };

    Node S[N];
    Node Q[N];
    int Pos[N];
    Info Data[N];
    set<Info>Set;

    inline void work(){
        r(q);
        for(int i=0;i<q<<1;++i){
            db x,y;
            scanf("%lf%lf",&x,&y);
            Q[i]=Node(i,Point(x*2,y*2));
        }
        sort(Q,Q+(q<<1));

        using Graph::P;
        using Graph::E;
        using Graph::ID;
        using Graph::ecnt;
        int tot=0;
        for(int i=2;i<=ecnt;i+=2){
            if(P[E[i].u].x>P[E[i].v].x)i^=1;
            if(P[E[i].u].x==P[E[i].v].x)continue;
            S[tot++]=Node(i,P[E[i].u]);
            S[tot++]=Node(-i,P[E[i].v]);
        }
        sort(S,S+tot);

        for(int i=0,j=0;i<(q<<1);++i){
            while(j<tot&&S[j].A.x<=Q[i].A.x){
                NOW=S[j].A.x;
                int id=S[j].id;
                if(id<0)Set.erase(Data[-id]);
                else Set.insert(Data[id]=Info(id,P[E[id].u],P[E[id].v]));
                ++j;
            }
            NOW=Q[i].A.x;
            Point A=Q[i].A;
            Point B=A;B.x++;
            //上面没有边，在无界区域
            if(Set.lower_bound(Info(0,A,B))==Set.end())Pos[Q[i].id]=Graph::OUT;
            else {
                //上面有边，因为当前边一定是从左到右，所以在其反向边所在区域
                Info t=*Set.lower_bound(Info(0,A,B));
                Pos[Q[i].id]=ID[t.id^1];
            }
        }
    }

}

namespace Tree{
    struct Edge{
        int u,v,w;

        inline Edge(){}
        inline Edge(int u,int v,int w):u(u),v(v),w(w){}

        inline bool operator <(const Edge &a)const{
            return w<a.w;
        }
    }E[N];

    int ecnt;
    int fir[N],nex[N],to[N],w[N];

    inline void addedge(int u,int v,int c){
        nex[++ecnt]=fir[u],fir[u]=ecnt,to[ecnt]=v,w[ecnt]=c;
        nex[++ecnt]=fir[v],fir[v]=ecnt,to[ecnt]=u,w[ecnt]=c;
    }

    int dep[N];
    int ac[N][20];
    int mx[N][20];

    void dfs(int x,int f){
        dep[x]=dep[f]+1;
        ac[x][0]=f;
        for(int i=1;(ac[x][i]=ac[ac[x][i-1]][i-1]);++i){
            mx[x][i]=max(mx[x][i-1],mx[ac[x][i-1]][i-1]);
        }
        for(int i=fir[x];i;i=nex[i]){
            int v=to[i];
            if(v==f)continue;
            mx[v][0]=w[i];
            dfs(v,x);
        }
    }

    inline int query(int u,int v){
        int ret=0;
        if(dep[u]<dep[v])swap(u,v);
        for(int i=17;~i;--i){
            if(dep[ac[u][i]]>=dep[v]){
                ret=max(ret,mx[u][i]);
                u=ac[u][i];
            }
        }
        if(u==v)return ret;
        for(int i=17;~i;--i){
            if(ac[u][i]!=ac[v][i]){
                ret=max(ret,mx[u][i]);
                ret=max(ret,mx[v][i]);
                u=ac[u][i],v=ac[v][i];
            }
        }
        return max(ret,max(mx[u][0],mx[v][0]));
    }

    int fa[N];

    int find(int x){
        return x==fa[x]?x:fa[x]=find(fa[x]);
    }

    inline bool uni(int u,int v){
        u=find(u),v=find(v);
        if(u==v)return 0;
        fa[u]=v;
        return 1;
    }
    //注意特判无解
    inline void solve(){
        using Graph::ID;
        int tot=0;
        for(int i=2;i<=Graph::ecnt;i+=2){
            E[++tot]=Edge(ID[i],ID[i^1],Graph::E[i].w);
        }
        sort(E+1,E+tot+1);
        for(int i=1;i<=Graph::tot;++i)fa[i]=i;
        for(int i=1;i<=tot;++i){
            if(E[i].u==Graph::OUT||E[i].v==Graph::OUT)continue;
            if(uni(E[i].u,E[i].v)){
                addedge(E[i].u,E[i].v,E[i].w);
                if(ecnt==(n-1)*2)break;
            }
        }
        for(int i=1;i<=Graph::tot;++i){
            if(!ac[i][0])dfs(i,0);
        }
        using Local::Pos;
        for(int i=0;i<(q<<1);i+=2){
            if(find(Pos[i])!=find(Pos[i^1])||Pos[i]==Graph::OUT)puts("-1");
            else printf("%d\n",query(Pos[i],Pos[i^1]));
        }
    }
}

int main(){
    Graph::work();
    Local::work();
    Tree::solve();
    return 0;
}