만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

봉우리

시간 제한2초메모리 제한128 MB

요약
각 질의마다 한 봉우리에서 출발해 난이도 제한 이하의 길만 이용할 때 도달 가능한 봉우리 중 k번째로 높은 높이를 구하고, 부족하면 -1을 출력한다.
난이도

어려움10점 중 9점

유형
그래프, 유니온 파인드, 세그먼트 트리, 정렬
정답자
아직 제출이 없습니다

문제

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

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

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

입력

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

둘째 줄에 nn개의 정수 h1,h2,…,hnh_1, h_2, \dots, h_n (1≤hi≤1091 \le h_i \le 10^9)이 주어지며, 각 봉우리의 높이를 나타낸다.

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

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

출력

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

예제8

  1. 예제 1

    입력
    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

  2. 예제 2

    입력
    2 1 5
10 20
1 2 5
1 5 1
1 5 2
1 4 1
1 4 2
2 5 2
    예상 출력
    20
10
10
-1
10

  3. 예제 3

    입력
    6 4 8
5 3 9 1 7 2
1 2 2
2 3 2
4 5 3
6 1 100
1 2 1
1 2 3
3 2 2
4 3 1
4 3 3
6 2 1
6 100 4
6 100 5
    예상 출력
    9
3
5
7
-1
2
2
-1

  4. 예제 4

    입력
    5 4 5
4 4 4 2 2
1 2 1
2 3 1
3 4 1
4 5 1
1 1 1
1 1 3
1 1 4
1 1 5
1 1 6
    예상 출력
    4
4
2
2
-1

  5. 예제 5

    입력
    4 3 3
7 7 7 7
1 2 5
2 3 5
3 4 5
1 3 1
1 5 4
1 5 5
    예상 출력
    7
7
-1

  6. 예제 6

    입력
    6 5 7
10 20 30 40 50 60
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
1 1 1
1 2 3
1 3 3
1 5 6
1 5 7
6 4 1
6 5 6
    예상 출력
    20
10
20
10
-1
60
10

  7. 예제 7

    입력
    3 1 3
1 2 3
1 2 10
1 1 5
1 10 5
3 10 2
    예상 출력
    -1
-1
-1

  8. 예제 8

    입력
    4 5 4
100 200 300 400
1 2 1
1 3 2
1 4 3
2 3 1
3 4 2
1 1 1
1 1 4
1 3 4
4 2 2
    예상 출력
    300
-1
100
300