Background

Original problem link: P4197 Peaks.

Problem Description

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}$.

Input Format

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$.

Output Format

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

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

Hint

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