봉우리

바이트아사르는 바이트산맥 국립공원 방문자 센터에서 일한다. 바이트산맥에는 봉우리가 $n$개 있고, 일부 봉우리 쌍은 서로 다른 난이도의 등산로로 이어져 있다.

관광객들은 바이트아사르에게 늘 비슷한 질문을 한다. 어떤 봉우리에서 출발해 정해진 난이도 이하의 등산로만 이용해 이동할 수 있을 때, 도달할 수 있는 봉우리 중 $k$번째로 높은 봉우리의 높이는 얼마인가?

각 난이도가 주어진 한계 이하인 등산로들을 차례로 지나 걸어서 갈 수 있으면, 그 봉우리는 출발 봉우리에서 도달 가능하다고 한다. 출발한 봉우리 자신도 항상 도달 가능한 것으로 본다. 모든 질문에 답할 수 있도록 바이트아사르를 도와주자.

첫째 줄에 세 정수 $n$, $m$, $q$ ($1 \le n \le 100000$, $1 \le m, q \le 500000$)가 주어진다. 각각 봉우리의 수, 등산로의 수, 질문의 수이다. 봉우리는 $1$번부터 $n$번까지 번호가 매겨져 있다.

둘째 줄에 $n$개의 정수 $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$)이 주어지며, 각 봉우리의 높이를 나타낸다.

이어지는 $m$개의 줄에는 각각 세 정수 $a$, $b$, $c$ ($1 \le a, b \le n$, $a \ne b$, $1 \le c \le 10^9$)가 주어진다. 이는 봉우리 $a$와 $b$를 잇는 양방향 등산로이며 난이도가 $c$임을 뜻한다. $c$가 클수록 더 어려운 등산로이다. 두 봉우리 사이에 등산로가 여러 개 있을 수도 있다.

이어지는 $q$개의 줄에는 각각 세 정수 $v$, $x$, $k$ ($1 \le v \le n$, $1 \le x \le 10^9$, $1 \le k \le n$)가 주어진다. 봉우리 $v$에서 출발하여 난이도가 $x$ 이하인 등산로만 이용할 때, 도달할 수 있는 봉우리 중 $k$번째로 높은 봉우리의 높이를 구하라.

$q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질문의 답, 즉 해당 조건에서 도달할 수 있는 봉우리 중 $k$번째로 높은 봉우리의 높이를 출력한다. 도달할 수 있는 봉우리가 $k$개보다 적으면 대신 $-1$을 출력한다.