题目描述

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

奶牛的训练场中有 $\red{N (1 ≤}$ $\red{N ≤}$ $\red{300) }$个站台，分别标记为$\red{1..N}$。所有站台之间有$\red{M (1 ≤}$ $\red{M ≤}$ $\red{25,000)}$条单向路径，第$\red{i}$条路经是从站台$\red{S_i}$开始，到站台$\red{Ei，}$其中最高的栏的高度为$\red{Hi (1 ≤}$ $\red{H_i ≤}$ $\red{1,000,000)}$。无论如何跑，奶牛们都 要跨栏。

奶牛们有 $\red{T (1 ≤}$ $\red{T ≤}$ $\red{40,000) }$个训练任务要完成。第 $\red{i }$个任务包含两个数字 $\red{A_i }$和 $\red{B_i (1 ≤}$ $\red{A_i ≤}$ $\red{N}$; $\red{1 ≤}$ $\red{B_i ≤}$ $\red{N)，}$表示奶牛必须从站台$\red{A_i}$跑到站台$\red{B_i，}$可以路过别的站台。奶牛们想找一条路径从站台$\red{A_i}$到站台$\red{B_i，}$使路径上最高的栏的高度最小。

你的任务就是写一个程序，计算出路径上最高的栏的高度的最小值。

输入格式

第$\red{1}$行: 两个整数 $\red{N, M, T }$行

第$\red{2..M+1}$行: 行 $\red{i+1 }$包含三个整数 $\red{S_i , E_i , H_i }$

第 $\red{M+2..M+T+1}$行: 第 $\red{i+M+1}$行 包含两个整数，表示任务$\red{i}$的起始站台和目标站台: $\red{A_i , B_i}$

输出格式

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

样例

输入样例

5 6 3
1 2 12
3 2 8
1 3 5
2 5 3
3 4 4
2 4 8
3 4
1 2
5 1

输出样例

4
8
-1