Description

In Bytemountains, there are $n$ peaks, and each peak has its height $h_i$. Some pairs of peaks are connected by bidirectional roads; there are $m$ roads in total. Each road has a difficulty value, and a larger value means it is harder to traverse.

There are $q$ queries. For each query, starting from vertex $v$, you may only traverse roads whose difficulty is less than or equal to $x$. Among all peaks reachable this way, find the $k$-th highest peak. If there is no such peak, output $-1$.

Input Format

The first line contains three integers $n, m, q$. The second line contains $n$ integers, where the $i$-th is $h_i$.

The next $m$ lines each contain three integers $a, b, c$, indicating there is a bidirectional road between $a$ and $b$ with difficulty $c$.

The next $q$ lines each contain three integers $v, x, k$, describing a query.

Output Format

For each query, output a single integer: the height of the $k$-th highest reachable peak.

10 11 4
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
1 5 2
1 5 6
1 5 8
8 9 2

6
1
-1
8

Hint

Constraints
For $100\%$ of the testdata, $1 \le v, k \le n \le 10^5$, $1 \le m, q \le 5 \times 10^5$, $1 \le h_i, c, x \le 10^9$.

Translated by ChatGPT 5