#3545. [ONTAK2010]Peaks

题目描述

在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。

输入格式

第一行三个数N，M，Q。
第二行N个数，第i个数为h_i
接下来M行，每行3个数a b c，表示从a到b有一条困难值为c的双向路径。
接下来Q行，每行三个数v x k，表示一组询问。

输出格式

对于每组询问，输出一个整数表示答案。

样例

样例输入

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  

数据范围与提示

【数据范围】

N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。