题目描述

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

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

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

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

输入格式

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

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

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

输出格式

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