Farmer John 想让她的奶牛准备郡级跳跃比赛，Bessie 和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。

奶牛的训练场中有 N 个站台，分别标记为 1,\dots,N。所有站台之间有 M 条单向路径，第 i 条路径是从站台 S_i 开始，到站台 E_i，其中最高的栏的高度为 H_i。无论如何跑，奶牛们都要跨栏。

奶牛们有 T 个训练任务要完成。第 i 个任务包含两个数字 A_i 和 B_i，表示奶牛必须从站台 A_i 跑到站台 B_i，可以路过别的站台。奶牛们想找一条路径从站台 A_i 到站台 B_i，使路径上最高的栏的高度最小。你的任务就是写一个程序，计算出路径上最高的栏的高度的最小值。

第一行：三个空格隔开的整数 N, M, T。

接下来 M 行：第 i 行包含三个空格隔开的整数 S_i, E_i, H_i。

接下来 T 行：第 i 行包含两个空格隔开的整数，表示任务 i 的起始站台和目标站台 A_i, B_i。

T 行：第 i 行为一个整数，表示任务 i 路径上最高的栏的高度的最小值。如果无法到达，输出 -1。

对于 100\% 的数据，1 \le N \le 300，1 \le M \le 2.5 \times 10^4，1 \le H_i \le 1 \times 10^6，1 \le T \le 4 \times 10^4，1 \le A_i, B_i \le N。