记录编号	256212	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]火龙果	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	31.711 s
提交时间	2016-04-29 16:22:07	内存使用	4.72 MiB

#define maxb 180ul
#define maxn 60010ul

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

#define fastcall __attribute__((optimize("-O3")))
#define IL __inline__ __attribute__((always_inline))

#define pb push_back

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

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

const int inf=0x7fffffff;

int n,m,q,tot,mxa,bcnt,bsiz,sta[maxn],fa[maxn],mc[maxn],ch[maxn][2],ans[maxn],bls[maxn],all[maxn];
bool tag[maxn];
std::vector<int> G[maxb],Q[maxb];

fastcall IL 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;
}

fastcall IL void _swap(int &x,int &y){
	if(x!=y) x^=y,y^=x,x^=y;
	return;
}

fastcall IL void giverev(int x){
	if(!x) return;
	tag[x]^=1;
	_swap(L(x),R(x));
	return;
}

fastcall IL void update(int x){
	mc[x]=x>n?x-n:0;
	if(L(x)&&edge[mc[L(x)]].c>edge[mc[x]].c) mc[x]=mc[L(x)];
	if(R(x)&&edge[mc[R(x)]].c>edge[mc[x]].c) mc[x]=mc[R(x)];
	return;
}

fastcall IL bool isroot(int x){
	return (!fa[x])||(L(fa[x])!=x&&R(fa[x])!=x);
}

fastcall IL 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;
	if(R(fa[x])==x) R(fa[x])=y;
	fa[y]=fa[x],fa[x]=y;
	update(x);return;
}

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

fastcall IL 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;
}

fastcall IL void access(int x){
	int t=0;
	while(x){
		splay(x),pushdown(x);
		R(x)=t,update(x);
		t=x,x=fa[x];
	}
	return;
}

fastcall IL void makeroot(int x){
	access(x),splay(x);
	giverev(x);return;
}

fastcall IL int find(int x){
	access(x),splay(x),pushdown(x);
	while(L(x)) x=L(x),pushdown(x);
	return x;
}

fastcall IL 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;
}

fastcall IL void link(int x,int y){
	makeroot(x),fa[x]=y;
	return;
}

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

fastcall IL bool qcmp(int a,int b){return op[a].b<op[b].b;}
fastcall IL bool ecmp(int a,int b){return edge[a].b<edge[b].b;}

fastcall IL void rp(int x){
	fa[x]=tag[x]=L(x)=R(x)=0;
	update(x);return;
}

fastcall int add_edge(int d){
	int k=query(edge[d].u,edge[d].v);
	if(k&&edge[k].c<=edge[d].c) 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;
}

fastcall 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;
}

fastcall void work(int b){
	int esize=G[b].size(),qsize=Q[b].size(),head=1;
	for(int i=1;i<=n+m;i++) rp(i);
	for(int i=0,j,x,y,t,top;i<qsize;i++){
		x=Q[b][i],top=0;
		while(head<=tot){
			t=all[head];
			if(edge[t].b>op[x].b) break;
			add_edge(t),++head;
		}
		for(j=0;j<esize;j++){
			y=G[b][j];
			if(edge[y].b>op[x].b) break;
			if(edge[y].a<=op[x].a&&(t=add_edge(y))!=-1) st[++top]=(pii){t,y};
		}
		t=query(op[x].u,op[x].v);
		if(t) ans[x]=edge[t].c;
		while(top) reb(st[top].x,st[top].y),--top;
	}
	return;
}

fastcall void add(int b){
	int esize=G[b].size();
	for(int i=0;i<esize;i++) all[++tot]=G[b][i];
	std::sort(all+1,all+tot+1,ecmp);
	return;
}

int main(){
	freopen("Dragon_fruit.in","r",stdin);
	freopen("Dragon_fruit.out","w",stdout);
	read(n),read(m),read(q);
	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);
		if(edge[i].a>mxa) mxa=edge[i].a;
	}
	for(int i=1;i<=q;i++){
		read(op[i].u),read(op[i].v),read(op[i].a),read(op[i].b),ans[i]=-1;
		if(op[i].a>mxa) mxa=op[i].a;
	}
	bsiz=sqrt(mxa);
	for(int i=1;i<=mxa;i++) bls[i]=(i-1)/bsiz+1;
	bcnt=bls[mxa];
	for(int i=1;i<=m;i++) G[bls[edge[i].a]].pb(i);
	for(int i=1;i<=q;i++) Q[bls[op[i].a]].pb(i);
	for(int i=1;i<=bcnt;i++) std::sort(G[i].begin(),G[i].end(),ecmp),std::sort(Q[i].begin(),Q[i].end(),qcmp);
	for(int i=1;i<=bcnt;i++) work(i),add(i);
	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
	return 0;
}