Description

给定一个包含 \(n\) 个节点和 \(m\) 条边的图，每条边有一个权值。

你的任务是回答 \(k\) 个询问，每个询问包含两个正整数 \(s\) 和 \(t\) 表示起点和终点，要求寻找从 \(s\) 到 \(t\) 的一条路径，使得路径上权值最大的一条边权值最小。

Format

Input

第一行包含三个整数 \(n , m, k\)，分别表示 \(n\) 个节点， \(m\) 条路径， \(k\) 个询问。

接下来 \(m\) 行，每行三个整数 \(u, v, w\), 表示一个由 \(u\) 到 \(v\) 的长度为 \(w\) 的双向边。

再接下来 \(k\) 行，每行两个整数 \(s ,t\) ，表示询问从 \(s\) 连接到 \(t\) 的所有路径中单边长度最大值的最小值。

Output

输出包含 \(k\) 行，每一行包含一个整数 \(p\) 。\(p\) 表示 \(s\) 连接到 \(t\) 的所有路径中单边长度最大值的最小值。另外，如果 \(s\) 到 \(t\) 没有路径相连通，输出 -1 即可。

Sample

Input

8 11 3
1 2 10
2 5 50
3 4 60
7 5 60
3 6 30
1 5 30
6 7 20
1 7 70
2 3 20
3 5 40
2 6 90
1 7
2 8
6 2

Output

30
-1
30

Limitation

\(n \le 1000, m \le 10^5, k \le 1000, w \le 10 ^ 7\)