题目描述

在一个充满危险的城市地图上，忍者神龟们为了证明自己的实力，接受了导师的挑战。

城市中有 $N$ 个地点，地点之间有 $M$ 条单向道路，每条道路上都有 一个 强大的敌人守护。第 $i$ 条道路上敌人的战斗力为 $P_i$。

现在有 $Q$ 个挑战任务，每个任务要求一只神龟从某个地点 $S_i$ 出发，到达目标地点 $E_i$。神龟们希望找到一条能到达目标地点的路径，并且在所有可行路径中，遇到的战斗力最强的敌人尽可能弱。

你的任务是帮助神龟们计算出，每个任务中所有可行路径上遇到的最强敌人的最小战斗力。如果无法到达目标地点，输出 -1。

输入格式

第 1 行，读入三个整数 $N, M, Q$，分别表示地点数、道路数和任务数。

接下来 $M$ 行，每行包含三个整数 $U_i, V_i, P_i$，表示从地点 $U_i$ 到地点 $V_i$ 的一条单向道路，以及这条道路上敌人的战斗力 $P_i$。

接下来 $Q$ 行：每行包含两个整数 $S_i, E_i$，表示第 $i$ 个挑战任务的起点和终点。

输出格式

对于每个挑战任务，输出一个整数，表示该任务中所有可行路径上战斗力最强的敌人的最小值。如果无法从 $S_i$ 到达 $E_i$，输出 -1。

样例

输入

5 6 4
1 2 10
1 3 20
2 3 30
3 4 35
4 5 20
3 5 50
1 3
3 5
1 5
5 3

输出

20
35
35
-1

数据范围

对于 $20\%$ 的数据，满足 $1 \le N \le 50$，$1 \le M \le 100$，$1 \le Q \le 100$。

对于 $100\%$ 的数据，满足 $1 \le N \le 300$，$1 \le M \le 25,000$，$1 \le P_i \le 1,000,000$，$1 \le Q \le 40,000$，$1 \le S_i, E_i \le N$。