[ONTAK2010] Peaks 加强版

题目背景

原题链接：P4197 Peaks

题目描述

给定一张 $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$，$1 \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}$。