Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,l;

#define MAXN 200010

namespace Pla

{

	struct point

	{

		double x,y;

		double operator * (point b){return x * b.y - y * b.x;}

		point operator - (point b){return (point){x - b.x,y - b.y};}

		double angle(){return atan2(y,x);}

	}p[MAXN];

	struct vector

	{

		int x,y,val;

		double k;

		void pt(){cout << p[x].x << " " << p[x].y << " - " << p[y].x << " " << p[y].y << endl;}

	}v[MAXN];

	int vnum = 0;

	void add(int a,int b,int val)

	{

		v[vnum] = (vector){a,b,val,(p[b] - p[a]).angle()};++vnum;

		v[vnum] = (vector){b,a,val,(p[a] - p[b]).angle()};++vnum;

		return;

	}

	struct cmp

	{

		bool operator ()(int a,int b){return v[a].k < v[b].k;}

	};

	set<int,cmp> s[MAXN];

	bool vis[MAXN];

	int stack[MAXN],top = 0;

	int belong[MAXN],tot = 0;

	void solve()

	{

		for(int i = 0;i < vnum;++i)s[v[i].x].insert(i);

		for(int i = 0;i < vnum;++i)

		{

			if(vis[i])continue;

			top = 0;

			stack[++top] = i;vis[i] = true;

			while(true)

			{

				set<int,cmp>::iterator it = s[v[stack[top]].y].find(stack[top] ^ 1);

				++it;

				if(it == s[v[stack[top]].y].end())it = s[v[stack[top]].y].begin();

				if(vis[*it])break;

				stack[++top] = *it;

				vis[*it] = true;

			}

			double sum = 0;

			for(int i = 1;i <= top;++i)sum += p[v[stack[i]].x] * p[v[stack[i]].y];

			if(sum >= 0)continue;

			++tot;

			while(top)belong[stack[top--]] = tot;

		}

		return;

	}

}

struct point

{

	double x,y;

}p[MAXN];

struct query

{

	int x,y;

}q[MAXN];

int qnum = 0;

void add(double a,double b,double c,double d)

{

	++qnum;q[qnum] = (query){qnum * 2 - 1,qnum * 2};

	p[qnum * 2 - 1] = (point){a,b};p[qnum * 2] = (point){c,d};

	return;

}

namespace Loc

{

	struct cmp

	{

		bool operator ()(int a,int b)

		{

			double x = max(Pla::p[Pla::v[a].x].x,Pla::p[Pla::v[b].x].x);

			point ax = (point){Pla::p[Pla::v[a].x].x,Pla::p[Pla::v[a].x].y};

			point ay = (point){Pla::p[Pla::v[a].y].x,Pla::p[Pla::v[a].y].y};

			point bx = (point){Pla::p[Pla::v[b].x].x,Pla::p[Pla::v[b].x].y};

			point by = (point){Pla::p[Pla::v[b].y].x,Pla::p[Pla::v[b].y].y};

			double ya = (ay.y - ax.y) / (ay.x - ax.x) * (x - ax.x) + ax.y;

			double yb = (by.y - bx.y) / (by.x - bx.x) * (x - bx.x) + bx.y;

			if(fabs(ya - yb) >= 1e-4)return ya < yb;

			else return (ay.y - ax.y) / (ay.x - ax.x) < (by.y - bx.y) / (by.x - bx.x);

		}

	};

	set<int,cmp> s;

	struct scanline

	{

		double x;

		int id,type;

	}sc[MAXN * 3];

	int scancnt = 0;

	bool cmp_x(scanline a,scanline b)

	{

		if(a.x != b.x)return a.x < b.x;

		else return a.type < b.type;

	}

	int bel[MAXN];

	void solve()

	{

		for(int i = 0;i < Pla::vnum;++i)

		{

			if(Pla::p[Pla::v[i].x].x >= Pla::p[Pla::v[i].y].x)continue;

			sc[++scancnt] = (scanline){Pla::p[Pla::v[i].x].x,i,1};

			sc[++scancnt] = (scanline){Pla::p[Pla::v[i].y].x,i,-1};

		}

		for(int i = 1;i <= 2 * l;++i)

		{

			sc[++scancnt] = (scanline){p[i].x,i,0};

		}

		sort(sc + 1,sc + 1 + scancnt,cmp_x);

		for(int i = 1;i <= scancnt;++i)

		{

			if(sc[i].type == 1)

			{//cout << "insert ";Pla::v[sc[i].id].pt();

				s.insert(sc[i].id);

			}

			if(sc[i].type == -1)

			{//cout << "erase ";Pla::v[sc[i].id].pt();

				s.erase(sc[i].id);

			}

			if(sc[i].type == 0)

			{

				Pla::p[n + 1].x = p[sc[i].id].x;

				Pla::p[n + 1].y = p[sc[i].id].y;

				Pla::p[n + 2].x = p[sc[i].id].x + 1;

				Pla::p[n + 2].y = p[sc[i].id].y;//cout << " -> " << p[sc[i].id].x << " " << p[sc[i].id].y << endl;

				Pla::v[Pla::vnum].x = n + 1;Pla::v[Pla::vnum].y = n + 2;

				set<int,cmp>::iterator it = s.upper_bound(Pla::vnum);

				if(it == s.end())continue;

				bel[sc[i].id] = Pla::belong[*it];

				//cout << sc[i].id << " " << p[sc[i].id].x << " " << p[sc[i].id].y << " : ";Pla::v[*it].pt();

			}

		}

		return;

	}

}

namespace Doubling

{

	struct edge

	{

		int to,nxt,v;

	}e[MAXN << 1];

	int edgenum = 0;

	int lin[MAXN] = {0};

	void add(int a,int b,int c)

	{

		e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

		e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;

		return;

	}

	int f[MAXN][19],g[MAXN][19];

	int dep[MAXN];

	void dfs(int k,int depth)

	{

		dep[k] = depth;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(e[i].to == f[k][0])continue;

			f[e[i].to][0] = k;

			g[e[i].to][0] = e[i].v;

			dfs(e[i].to,depth + 1);

		}

		return;

	}

	void build()

	{

		dfs(1,1);

		for(int k = 1;k <= 18;++k)

		{

			for(int i = 1;i <= n;++i)

			{

				f[i][k] = f[f[i][k - 1]][k - 1];

				g[i][k] = max(g[i][k - 1],g[f[i][k - 1]][k - 1]);

			}

		}

	}

	int query(int a,int b)

	{

		if(a == 0 || b == 0)return -1;

		int res = 0;

		if(dep[a] < dep[b])swap(a,b);

		for(int k = 18;k >= 0;--k)

		{

			if(dep[f[a][k]] >= dep[b])

			{

				res = max(res,g[a][k]);

				a = f[a][k];

			}

		}

		if(a == b)return res;

		for(int k = 18;k >= 0;--k)

		{

			if(f[a][k] != f[b][k])

			{

				res = max(res,max(g[a][k],g[b][k]));

				a = f[a][k];b = f[b][k];

			}

		}

		return max(res,max(g[a][0],g[b][0]));

	}

}

namespace Kruskal

{

	int f[MAXN];

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

	struct edges

	{

		int u,v,w;

	}es[MAXN];

	bool cmp_w(edges a,edges b){return a.w < b.w;}

	int edgenum = 0;

	void add(int a,int b,int c)

	{

		es[++edgenum] = (edges){a,b,c};

		return;

	}

	void solve()

	{

		for(int i = 1;i <= Pla::tot;++i)f[i] = i;

		sort(es + 1,es + 1 + edgenum,cmp_w);

		for(int i = 1;i <= edgenum;++i)

		{

			if(find(es[i].u) == find(es[i].v))continue;

			Doubling::add(es[i].u,es[i].v,es[i].w);

			f[find(es[i].u)] = find(es[i].v);

		}

		return;

	}

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%lf%lf",&Pla::p[i].x,&Pla::p[i].y);

	int x,y,v;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&x,&y,&v);

		Pla::add(x,y,v);

	}

	Pla::solve();

	scanf("%d",&l);

	double a,b,c,d;

	for(int i = 1;i <= l;++i)

	{

		scanf("%lf%lf%lf%lf",&a,&b,&c,&d);

		add(a,b,c,d);

	}

	Loc::solve();

	for(int i = 0;i < Pla::vnum;++i)

	{

		if(Pla::belong[i] == 0 || Pla::belong[i ^ 1] == 0)continue;

		Kruskal::add(Pla::belong[i],Pla::belong[i ^ 1],Pla::v[i].val);

	}

	Kruskal::solve();

	Doubling::build();

	for(int i = 1;i <= l;++i)

	{

		printf("%d\n",Doubling::query(Loc::bel[q[i].x],Loc::bel[q[i].y]));

	}

	return 0;

}