小w负责a国的火车系统调度。a国的火车系统由$m$条铁轨构成，每条火车线路形如$(a,b,c)$的形式，表示有两辆火车在$c$时刻，分别从$a$地和$b$地出发前往对面。由于a国科技发达，我们可以认为火车不需要时间，在$c$时刻出发就可以在$c$时刻到达。

为了从$x$到$y$，小w可能会换乘一系列的铁路线路，小w为了从第一个铁路线路$(a1, b1, c1)$换乘第二个铁路线路$(a2, b2, c2)$，需要$c1 \leq c2, b1 = a2$。

现在有$q$个询问，每个询问问小w最早什么时间能从$a$地到$b$地。注意一条换乘线路的时间是线路上最后一段火车的到达时间。

输入格式

第一行三个整数$n, m, q$。

接下来$m$行，每行三个整数$a_i, b_i, c_i$。

最后$q$行，每行表示一个询问$a_i, b_i$, $a_i \not= b_i$。

输出格式

$q$行，每行一个整数表示答案。

如果不能到达输出-1.

样例一

input

3 3 3
1 3 1
2 3 2
1 2 1
1 2
1 3
2 3

output

1
1
1

样例二

input

3 3 3
1 3 5
2 3 2
1 2 7
1 2
1 3
2 3

output

7
5
2

数据范围

时间限制1s, 空间范围512MB

$q \leq 10^5$