题目背景
原题链接:P1285
题目描述
给定一张 n 个点、m 条边的无向图,第 i 个点的权值为 ai,边有边权。
有 q 组询问,每组询问给定三个整数 u,x,k,求从 u 开始只经过权值 ≤x 的边所能到达的权值第 k 大的点的权值,如果不存在输出 −1。
本题强制在线。即:每次查询输入的是 u′,x′,k′,则 u=u′xorlastans,k 和 x 的解密方式与之相同。
输入格式
第一行,三个整数 n,m,q;
第二行,n 个整数 a1,a2,⋯,an;
接下来 m 行,每行三个整数 s,t,w,表示从 s→w 有一条困难值为 w 的双向路径;
接下来 q 行,每行三个整数 u′,x′,k′。
注意:处理第一组数据和无解时的 lastans=0。
输出格式
对于每组询问,输出一行,一个整数,表示所求的值。
样例 #1
10 11 3
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
0 5 5
1 6 8
7 8 1
1
-1
8
提示
对于 100% 的数据,1≤n≤105,0≤m,q≤5×105,1≤s,t≤n,1≤ai,w≤109,0≤u′,x′,k′<231。