Description：

有 $N$ 座山峰，山峰有高度 $h_i$ 。共 $M$ 条路径，每条路径有一个困难值，现在有 $Q$ 组询问，询问从点 $v$ 开始只经过困难值小于等于 $x$ 的路径所能到达的山峰中第 $k$ 高的山峰，如果无解输出 $-1$ 。强制在线。

$1\leqslant n\leqslant 10^5,1\leqslant m,q\leqslant 5\times 10^5$

Solution：

和NOI2018归程类似，先建出 $Kruskal$ 重构树，求出 $dfs$ 序后就变成了求区间第 $k$ 大，主席树即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m,q;

#define MAXN 200010

#define MAXM 500010

struct edges

{

	int u,v,w;

}es[MAXM];

int h[MAXN];

int tot = 0;

namespace UFS{

	int f[MAXN];

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

	void init()

	{

		for(int i = 1;i <= n;++i)f[i] = i;

		return;

	}

}

namespace Tree{

	struct edge

	{

		int to,nxt;

	}e[MAXN << 1];

	int edgenum = 0;

	int lin[MAXN] = {0};

	void add(int a,int b)

	{

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

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

		return;

	}

	int val[MAXN],rnk[MAXN],pos[MAXN],siz[MAXN],th = 0;

}

namespace Kruskal{

	using namespace Tree;

	using namespace UFS;

	bool v[MAXN];

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

	void build()

	{

		init();

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

		tot = n;

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

		{

			int p = find(es[i].u),q = find(es[i].v);

			if(p == q)continue;

			++tot;

			f[p] = f[q] = f[tot] = tot;

			add(p,tot);add(q,tot);

			val[tot] = es[i].w;

		}

		return;

	}

}

namespace Doubling{

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

	bool v[MAXN];

	using namespace Tree;

	void dfs(int k)

	{

		v[k] = true;

		rnk[k] = ++th;pos[th] = k;

		siz[k] = 1;

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

		{

			if(v[e[i].to])continue;

			dfs(e[i].to);

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

			g[e[i].to][0] = val[k];

			siz[k] += siz[e[i].to];

		}

		return;

	}

	void build()

	{

		for(int i = tot;i >= 1;--i)

		{

			if(!v[i])dfs(i);

		}

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

		{

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

			{

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

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

			}

		}

		return;

	}

	int calc(int p,int h)

	{

		int pos = p;

		for(int i = 19;i >= 0;--i)

		{

			if(f[pos][i] != 0 && g[pos][i] <= h)

			{

				pos = f[pos][i];

			}

		}

		return pos;

	}

}

int v[MAXN],N = 0;

namespace Discretize

{

	int b[MAXN];

	void build()

	{

		for(int i = 1;i <= n;++i)b[i] = h[i];

		sort(b + 1,b + 1 + n);

		N = unique(b + 1,b + 1 + n) - b - 1;

		for(int i = 1;i <= n;++i)v[i] = lower_bound(b + 1,b + 1 + N,h[i]) - b;

		b[0] = -1;

		return;

	}

} 

namespace PresidentTree

{

	struct node

	{

		int lc,rc;

		int sum;

		node(){sum = 0;}

	}t[MAXN * 31];

	int ptr = 0;

	int newnode(){return ++ptr;}

	#define mid ((l + r) >> 1)

	int root[MAXN];

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		if(l == r)return;

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		return;

	}

	void insert(int &rt,int p,int l,int r)

	{

		if(p == 0)return;

		int k = newnode();t[k] = t[rt];rt = k;

		++t[rt].sum;

		if(l == r)return;

		if(p <= mid)insert(t[rt].lc,p,l,mid);

		else insert(t[rt].rc,p,mid + 1,r);

		return;

	}

	void init()

	{

		build(root[0],1,N);

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

		{

			root[i] = root[i - 1];

			insert(root[i],v[Tree::pos[i]],1,N);

		}

		return;

	}

	int query(int rtr,int rtl,int k,int l,int r)

	{

		if(t[rtr].sum - t[rtl].sum < k)return 0;

		if(l == r)return l;

		int rs = t[t[rtr].rc].sum - t[t[rtl].rc].sum;

		if(k <= rs)return query(t[rtr].rc,t[rtl].rc,k,mid + 1,r);

		else return query(t[rtr].lc,t[rtl].lc,k - rs,l,mid);

	}

}

int calc(int p,int x,int k)

{

	p = Doubling::calc(p,x);

	int lef = Tree::rnk[p],rig = Tree::rnk[p] + Tree::siz[p] - 1;

	using namespace PresidentTree;

	return query(root[rig],root[lef - 1],k,1,N);

}

int main()

{

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

	for(int i = 1;i <= n;++i)h[i] = rd();

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

	{

		es[i].u = rd();es[i].v = rd();

		es[i].w = rd();

	}

	Kruskal::build();

	Doubling::build();

	Discretize::build();

	int p,x,k;

	PresidentTree::init();

	int lastans = 0;

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

	{

		p = rd();x = rd();k = rd();

		if(lastans != -1)

		{

			p ^= lastans;

			x ^= lastans;

			k ^= lastans;

		}

		int ans = Discretize::b[calc(p,x,k)];

		lastans = ans;

		printf("%d\n",ans);

	}

	return 0;

}