记录编号	256143	评测结果	TTTTTTTTTT
题目名称	2291.[HZOI 2015]火龙果	最终得分	0
用户昵称	stdafx.h	是否通过	未通过
代码语言	C++	运行时间	100.003 s
提交时间	2016-04-29 12:15:07	内存使用	5.43 MiB

#define maxb 20ul
#define maxn 60010ul

#include <stdio.h>
#include <algorithm>

struct pii{int x,y;};
struct Edge{int u,v,a,b,c;}edge[maxn];
struct opr{int u,v,a,b,id;}op[maxn];

int n,m,q,vl[maxn],sta[maxn],seq[maxn],ms[maxn],tp[maxn],fa[maxn],ans[maxn],ch[maxn][2],mb[maxn];
bool tag[maxn];
pii ap[maxn];

const int inf=0x7fffffff;

#define L(e) ch[e][0]
#define R(e) ch[e][1]

void giverev(int x){
	if(!x) return;
	tag[x]^=1;
	std::swap(L(x),R(x));
	return;
}

inline void update(int x){
	mb[x]=x>n?x-n:0;
	if(L(x)&&edge[mb[L(x)]].b>edge[mb[x]].b) mb[x]=mb[L(x)];
	if(R(x)&&edge[mb[R(x)]].b>edge[mb[x]].b) mb[x]=mb[R(x)];
	return;
}

bool isroot(int x){
	return (!fa[x])||(L(fa[x])!=x&&R(fa[x])!=x);
}
 
void rotate(int x,int d){
	int y=ch[x][d^1];
	ch[x][d^1]=ch[y][d];
	fa[ch[y][d]]=x,ch[y][d]=x;
	if(L(fa[x])==x) L(fa[x])=y;
	else if(R(fa[x])==x) R(fa[x])=y;
	fa[y]=fa[x],fa[x]=y;
	update(x);return;
}

void pushdown(int x){
	if(tag[x]){
		giverev(L(x));
		giverev(R(x));
		tag[x]=false;
	}
	return;
}

void splay(int p){
	sta[++sta[0]]=p;
	for(int i=p;!isroot(i);i=fa[i]) sta[++sta[0]]=fa[i];
	while(sta[0]) pushdown(sta[sta[0]--]);
	int x,y;
	while(!isroot(p)){
		x=fa[p],y=fa[x];
		if(isroot(x)) rotate(x,L(x)==p);
		else{
			if((L(y)==x)==(L(x)==p)) rotate(y,L(y)==x),rotate(x,L(x)==p);
			else rotate(x,L(x)==p),rotate(y,L(y)==p);
		}
	}
	update(p);
	return;
}

void access(int x){
	int t=0;
	while(x){
		splay(x);pushdown(x);
		R(x)=t;update(x);
		t=x,x=fa[x];
	}
	return;
}
 
void makeroot(int x){
	access(x);splay(x);
	giverev(x);return;
}
 
void link(int x,int y){
	makeroot(x),fa[x]=y;
	return;
}
 
void cut(int x,int y){
	makeroot(x),access(y);splay(y),pushdown(y);
	if(L(y)==x) fa[x]=L(y)=0;
	update(y);return;
}

int dfs(int x){
	pushdown(x);
	return L(x)?dfs(L(x)):x;
}

int find(int x){
	access(x),splay(x);
	return dfs(x);
}

int query(int u,int v){
	if(find(u)!=find(v)) return 0;
	makeroot(u),access(v),splay(v);
	return mb[v];
}

int add_edge(int d){
	int k=query(edge[d].u,edge[d].v);
	if(k&&edge[k].b<=edge[d].b) return -1;
	if(k) cut(edge[k].u,k+n),cut(edge[k].v,k+n);
	link(edge[d].u,d+n),link(edge[d].v,d+n);
	return k;
}

void reb(int r,int nv){
	cut(edge[nv].u,nv+n),cut(edge[nv].v,nv+n);
	if(r) link(edge[r].u,r+n),link(edge[r].v,r+n);
	return;
}

void read(int &x){
	x=0;int c=getchar();
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return;
}

bool cmp_with_a(const Edge &a,const Edge &b){return a.a<b.a;}
bool cmp2_with_a(const opr &a,const opr &b){return a.a<b.a;}

void divide(int l,int r,int ml,int mr,int ql,int qr,pii *rb){//<=mid
	if(l>r||ml>mr||ql>qr) return;
	int tot=0,mid=(l+r)>>1,qla=ql,qlb=ql,mla=ml,mlb=ml,px,pc;
	for(int i=ql,j=ml,mx,qx,k;i<=qr;i++){
		qx=seq[i];
		while(j<=mr){
			mx=ms[j];
			if(edge[mx].c<=mid&&edge[mx].a<=op[qx].a){
				if((k=add_edge(mx))!=-1) rb[++tot]=(pii){k,mx};
				++j;
			}
			else if(edge[mx].a>op[qx].a) break;
			else ++j;
		}
		k=query(op[qx].u,op[qx].v);
		if(k&&edge[k].b<=op[qx].b) ans[op[qx].id]=mid,++qlb;
	}
	pc=qlb;
	for(int i=ql;i<=qr;i++){
		if(ans[op[seq[i]].id]<=mid) tp[qla++]=seq[i];
		else tp[qlb++]=seq[i];
	}
	for(int i=ql;i<=qr;i++) seq[i]=tp[i];
	for(int i=ml;i<=mr;i++) if(edge[ms[i]].c<=mid) ++mlb;
	px=mlb;
	for(int i=ml;i<=mr;i++){
		if(edge[ms[i]].c<mid) tp[mla++]=ms[i];
		else if(edge[ms[i]].c>mid) tp[mlb++]=ms[i];
	}
	for(int i=ml;i<=mr;i++) ms[i]=tp[i];
	divide(mid+1,r,px,mlb-1,pc,qlb-1,rb+tot+1);
	for(int i=1;i<=tot;i++) reb(rb[i].x,rb[i].y);
	divide(l,mid-1,ml,mla-1,ql,qla-1,rb);
	return;
}

int main(){
	freopen("Dragon_fruit.in","r",stdin);
	freopen("Dragon_fruit.out","w",stdout);
	read(n),read(m),read(q);int mx=-1;
	for(int i=1;i<=m;i++) read(edge[i].u),read(edge[i].v),read(edge[i].a),read(edge[i].b),read(edge[i].c);
	for(int i=1;i<=m;i++) if(edge[i].c>mx) mx=edge[i].c;
	std::sort(edge+1,edge+m+1,cmp_with_a);
	for(int i=1;i<=m;i++) vl[i]=edge[i].b;
	for(int i=1;i<=n+m;i++) update(i);
	for(int i=1;i<=q;i++) read(op[i].u),read(op[i].v),read(op[i].a),read(op[i].b),op[i].id=i;
	for(int i=1;i<=q;i++) ans[i]=inf;
	std::sort(op+1,op+q+1,cmp2_with_a);
	for(int i=1;i<=q;i++) seq[i]=i;
	for(int i=1;i<=m;i++) ms[i]=i;
	divide(1,mx,1,m,1,q,ap);
	for(int i=1;i<=q;i++) if(ans[i]>mx) ans[i]=-1;
	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
	return 0;
}