并不会克鲁斯卡尔重构树，于是就写了离线算法。
使用了最小生成树，启发式合并treap
在最小生成树，克鲁斯卡尔算法 时 ，将询问一块处理。便可以保证询问时边的要求。然后利用平衡树，加速计算。
// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#define Ls T[R].ch[0]
#define Rs T[R].ch[1]
#define T_d T[R].ch[d]
using std::sort;
const int maxn=201000;
const int inf=0x7fffffff;
struct Tree
{
int val;
int key;
int Size;
int Self;
int ch[2];
Tree(int a=0,int b=1,int c=1)
{
key=rand();
val=a;
Size=b;
Self=c;
ch[0]=ch[1]=0;
}
void Clear()
{
Size=Self;
ch[0]=ch[1]=0;
}
};
struct Data
{
int A,B;
int Value,Tag;
int Num;
Data (int a=0,int b=0,int v=0,int t=-inf,int n=0)
{
A=a;B=b;
Value=v;
Tag=t;
Num=n;
}
};
Tree T[maxn];
Data base[maxn*5];
int h[maxn],f[maxn],tail;
int belong[maxn],ans[maxn*5];
int Find(int x)
{
if(f[x]==x) return f[x];
return f[x]=Find(f[x]);
}
int compare(const Data &a,const Data &b)
{
if(a.Value!=b.Value) return a.Value<b.Value;
return a.Tag<b.Tag;
}
int cmpkth(int R,int kth)
{
int s=T[Rs].Size;
if(kth<=s) return 1;
if(kth>s+T[R].Self) return 0;
return -1;
}
int cmpval(int R,int val)
{
if(T[R].val==val) return -1;
return T[R].val<val;
}
void Sum(int R)
{
T[R].Size=T[R].Self+T[Ls].Size+T[Rs].Size;
return ;
}
void Rotate(int &R,int dir)
{
int k=T[R].ch[dir^1];
T[R].ch[dir^1]=T[k].ch[dir];
T[k].ch[dir]=R;
Sum(R);Sum(k);
R=k;
}
int Seek_kth(int R,int kth)
{
int d=cmpkth(R,kth);
if(d==-1) return T[R].val;
return Seek_kth(T_d,kth-=( d==0 ? T[Rs].Size+T[R].Self : 0 ));
}
void Insert(int &R,int val,int model=0,int num=0)
{
if(R==0)
{
if(model==0){ R=++tail;T[R]=Tree(val); }
else { T[num].Clear();R=num; }
return ;
}
int d=cmpval(R,val);
if(d==-1)
{
int add=( model ? T[num].Self : 1 );
T[R].Self+=add;
T[R].Size+=add;
return ;
}
Insert(T_d,val,model,num);
Sum(R);
if(T[T_d].key>T[R].key) Rotate(R,d^1);
return ;
}
void _merge(int &R,int &Dir)
{
if(R==0) return ;
_merge(Ls,Dir);
_merge(Rs,Dir);
Insert(Dir,T[R].val,1,R);
return ;
}
void Merge(int &A,int &B,int f1,int f2)
{
if(T[A].Size>T[B].Size)
{
_merge(B,A);
f[f2]=f1;
B=A;
return ;
}
else
{
_merge(A,B);
f[f1]=f2;
A=B;
return ;
}
}
void visit(int now)
{
if(now==0) return ;
visit(T[now].ch[0]);
printf("%d ",T[now].val);
visit(T[now].ch[1]);
}
int main()
{
srand(time(NULL));
int n,m,q;
T[0].Self=0;T[0].Size=0;
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
scanf("%d",&h[i]),f[i]=i;
for(int i=1;i<=n;i++)
Insert(belong[i],h[i]);
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
base[i]=Data(a,b,c);
}
for(int i=1;i<=q;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
base[i+m]=Data(a,c,b,0,i);
ans[i]=-1;
}
sort(base+1,base+1+m+q,compare);
for(int i=1;i<=m+q;i++)
{
if(base[i].Tag==0)
{
int _f=Find(base[i].A);
if(T[belong[_f]].Size>=base[i].B)
ans[base[i].Num]=Seek_kth(belong[_f],base[i].B);
}
else
{
int f1=Find(base[i].A),f2=Find(base[i].B);
if(f1==f2) continue;
Merge(belong[f1],belong[f2],f1,f2);
}
}
for(int i=1;i<=q;i++)
printf("%d\n",ans[i]);
// return 0;
return 0;
}