P7834 [ONTAK2010] Peaks Enhanced Version

Original problem link: [P4197 Peaks](https://www.luogu.com.cn/problem/P4197).

Given an undirected graph with $n$ vertices and $m$ edges. The weight of vertex $i$ is $a_i$, and each edge has an edge weight. There are $q$ queries. Each query gives three integers $u, x, k$. Starting from $u$, you may only traverse edges with edge weight $\leq x$. Among all vertices that can be reached, output the vertex weight that is the $k$-th largest. If it does not exist, output $-1$. **This problem is forced online. That is: for each query, the input is $u', x', k'$, then $u = (u' \operatorname{xor} \text{lastans}) \bmod n + 1$, and $k$ is decrypted in the same way, and $x = x' \operatorname{xor} \text{lastans}$.**

The first line contains three integers $n, m, q$. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$. The next $m$ lines each contain three integers $s, t, w$, representing the two endpoints of an edge and its weight. The next $q$ lines each contain three integers $u', x', k'$. **Note: for the first query and for cases with no solution, $\text{lastans} = 0$.**

For each query, output one line with one integer, representing the required value.

For $100\%$ of the testdata, $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}$. Translated by ChatGPT 5