首先强制在线的话，肯定是不能再离线排序+平衡树启发式合并了。
这回要用的是线段树合并，每次把两棵线段树合并，总复杂度为$O(n\log n)$
预处理：
把边按权值从小到大排序，依次加边，
对于边(x,y)，权值为z，如果x和y已经在一个联通块里就无视掉
假设x块大小小于等于y块大小
将x,y两块的线段树合并，设合并后线段树根为r，并在y所在块根节点处root表后面加入一个(r,z)
然后把x块内所有点的top表后面加入一个(top[y],z)
这里启发式合并的总复杂度也为$O(n\log n)$
查询从v出发走权值不超过x所到达的点中第k大：
先在v的top表里二分出最后面的权值不超过x的根节点r
再在r的root表里二分出最后面的权值不超过x的线段树根节点t
最后在t树中查询第k大
所以查询一次的复杂度为$O(\log n)$
所以总复杂度为$O((n+q)\log n)$
（吐槽：$O(n\log n)$的线段树合并不知道为什么比我之前$O(n\log^2n)$的平衡树启发式合并还要慢1S）
#include<cstdio>
#include<algorithm>
#define N 100010
#define M 3500000
#define T 1500000
using namespace std;
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
struct edge{int a,b,c;}e[500010];
inline bool cmp(edge a,edge b){return a.c<b.c;}
int n,m,q,i,j,et,x,y,k,last;
int h[N],b[N];
inline int lower(int x){
int l=1,r=n,mid,t;
while(l<=r)if(b[mid=(l+r)>>1]<x)l=mid+1;else r=(t=mid)-1;
return t;
}
int l[M],r[M],val[M],tot;
int merge(int x,int y,int a,int b){
if(!x)return y;
if(!y)return x;
int z=++tot;
if(a==b){
val[z]=val[x]+val[y];
return z;
}
int mid=(a+b)>>1;
l[z]=merge(l[x],l[y],a,mid);
r[z]=merge(r[x],r[y],mid+1,b);
val[z]=val[l[z]]+val[r[z]];
return z;
}
int build(int a,int b,int c){
int x=++tot;
val[x]=1;
if(a==b)return x;
int mid=(a+b)>>1;
if(c<=mid)l[x]=build(a,mid,c);else r[x]=build(mid+1,b,c);
return x;
}
int kth(int x,int k){
if(k>val[x])return 0;
int a=1,b=n,mid,t;
while(1){
if(a==b)return a;
mid=(a+b)>>1,t=val[r[x]];
if(k<=t)x=r[x],a=mid+1;else k-=t,x=l[x],b=mid;
}
}
int size[N],g[N],nxt[N<<1],v[N<<1],ed;
int top_st[N],top_en[N],top_nxt[T],top_v[T],top_w[T],top_list[T],top_bg[N],top_cnt[N],td;
int root_st[N],root_en[N],root_nxt[N<<1],root_v[N<<1],root_w[N<<1],root_list[N<<1],root_bg[N],root_cnt[N],rd;
inline void addedge(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
inline void addtop(int x,int y,int z){top_v[++td]=y;top_w[td]=z;top_nxt[top_en[x]]=td;top_en[x]=td;}
inline void addroot(int x,int y,int z){root_v[++rd]=y;root_w[rd]=z;root_nxt[root_en[x]]=rd;root_en[x]=rd;}
void go(int x,int pre,int y,int t){
addtop(x,y,t);
for(int i=g[x];i;i=nxt[i])if(v[i]!=pre)go(v[i],x,y,t);
}
inline void link(int x,int y,int t){
if(top_v[top_en[x]]==top_v[top_en[y]])return;
if(size[top_v[top_en[x]]]>size[top_v[top_en[y]]])swap(x,y);
addroot(top_v[top_en[y]],merge(root_v[root_en[top_v[top_en[x]]]],root_v[root_en[top_v[top_en[y]]]],1,n),t);
size[top_v[top_en[y]]]+=size[top_v[top_en[x]]];
go(x,0,top_v[top_en[y]],t);
addedge(x,y);
addedge(y,x);
}
inline int gettop(int x,int y){
int l=top_bg[x],r=l+top_cnt[x]-1,mid,t;
while(l<=r)if(top_w[top_list[mid=(l+r)>>1]]<=y)t=top_v[top_list[mid]],l=mid+1;else r=mid-1;
return t;
}
inline int getroot(int x,int y){
int l=root_bg[x],r=l+root_cnt[x]-1,mid,t;
while(l<=r)if(root_w[root_list[mid=(l+r)>>1]]<=y)t=root_v[root_list[mid]],l=mid+1;else r=mid-1;
return t;
}
int main(){
read(n);read(m);read(q);
for(i=1;i<=n;i++)read(h[i]),b[i]=h[i];b[0]=-1;
sort(b+1,b+n+1);
for(i=1;i<=n;i++)root_v[i]=build(1,n,lower(h[i])),top_st[i]=top_en[i]=top_v[i]=root_st[i]=root_en[i]=i,top_w[i]=root_w[i]=-1,size[i]=1;
td=rd=n;
for(i=1;i<=m;i++)read(e[i].a),read(e[i].b),read(e[i].c);
sort(e+1,e+m+1,cmp);
for(i=1;i<=m;i++)link(e[i].a,e[i].b,e[i].c);
td=rd=0;
for(i=1;i<=n;i++){
for(top_bg[i]=td+1,j=top_st[i];j;j=top_nxt[j])++top_cnt[i],top_list[++td]=j;
for(root_bg[i]=rd+1,j=root_st[i];j;j=root_nxt[j])++root_cnt[i],root_list[++rd]=j;
}
while(q--){
read(x);read(y);read(k);
if(~last)x^=last,y^=last,k^=last;
printf("%d\n",last=b[kth(getroot(gettop(x,y),y),k)]);
}
return 0;
}