[ONTAK2010] Peaks 加强版
题目背景
原题链接:[P4197 Peaks](https://www.luogu.com.cn/problem/P4197)
题目描述
给定一张 $n$ 个点、$m$ 条边的无向图,第 $i$ 个点的权值为 $a_i$,边有边权。
有 $q$ 组询问,每组询问给定三个整数 $u, x, k$,求从 $u$ 开始只经过权值 $\leq x$ 的边所能到达的权值第 $k$ 大的点的权值,如果不存在输出 $-1$。
**本题强制在线。即:每次查询输入的是 $u', x', k'$,则 $u = (u' \operatorname{xor} \text{lastans}) \bmod n + 1$,$k$ 的解密方式与之相同,$x = x' \operatorname{xor} \text{lastans}$**。
输入输出格式
输入格式
第一行,三个整数 $n, m, q$;
第二行,$n$ 个整数 $a_1, a_2, \cdots, a_n$;
接下来 $m$ 行,每行三个整数 $s, t, w$,表示一条边的两个端点和权值;
接下来 $q$ 行,每行三个整数 $u', x', k'$。
**注意:处理第一组数据和无解时的 $\text{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
-1
8
说明
对于 $100\%$ 的数据,$1 \leq n \leq 10^5$,$0 \leq m, q \leq 5 \times 10^5$,$1 \leq s, t \leq n$,$1 \leq a_i, w \leq 10^9$,$0 \leq u', x', k' < 2^{31}$。