CF687D.Dividing Kingdom II

Long time ago, there was a great kingdom and it was being ruled by The Great Arya and Pari The Great. These two had some problems about the numbers they like, so they decided to divide the great kingdom between themselves.

The great kingdom consisted of n cities numbered from 1 to n and m bidirectional roads between these cities, numbered from 1 to m. The i-th road had length equal to w__i. The Great Arya and Pari The Great were discussing about destructing some prefix (all road with numbers less than some x) and suffix (all roads with numbers greater than some x) of the roads so there will remain only the roads with numbers l, l + 1, ..., r - 1 and r.

After that they will divide the great kingdom into two pieces (with each city belonging to exactly one piece) such that the hardness of the division is minimized. The hardness of a division is the maximum length of a road such that its both endpoints are in the same piece of the kingdom. In case there is no such road, the hardness of the division is considered to be equal to  - 1.

Historians found the map of the great kingdom, and they have q guesses about the l and r chosen by those great rulers. Given these data, for each guess l__i and r__i print the minimum possible hardness of the division of the kingdom.

很久以前，有一个伟大的王国，由伟大的阿瑞亚（Arya）与伟大的帕里（Pari）共同统治。这两位君主在各自偏爱的数字上存在一些分歧，因此决定将这个伟大的王国在他们之间进行划分。

这个伟大的王国由 $n$ 座城市组成，编号从 $1$ 到 $n$，以及连接这些城市的 $m$ 条双向道路，编号从 $1$ 到 $m$。第 $i$ 条道路的长度为 $w_i$。伟大的阿瑞亚与伟大的帕里经过商议，决定摧毁道路编号的一个前缀（即所有编号小于某个 $x$ 的道路）和一个后缀（即所有编号大于某个 $x$ 的道路），从而仅保留编号在区间 $[l,\, l+1,\, \dots,\, r-1,\, r]$ 内的道路。

随后，他们将把伟大的王国划分为两个部分（每座城市恰好属于其中一个部分），使得该划分的“难度”（hardness）最小化。划分的难度定义为：所有两个端点均位于同一部分内的道路中，长度的最大值；若不存在这样的道路，则该划分的难度定义为 $-1$。

历史学家发现了这个伟大王国的地图，并得到了 $q$ 个关于上述君主所选参数 $l$ 和 $r$ 的猜测。给定这些数据，对每个猜测 $(l_i, r_i)$，请输出王国划分可能达到的最小难度。

The first line of the input contains three integers n, m and q (1 ≤ n, q ≤ 1000, ) — the number of cities and roads in the great kingdom, and the number of guesses, respectively.

The i-th line of the following m lines contains three integers u__i, v__i and w__i (1  ≤  u__i,  v__i  ≤  n, 0 ≤ w__i ≤ 109), denoting the road number i connects cities u__i and v__i and its length is equal w__i. It's guaranteed that no road connects the city to itself and no pair of cities is connected by more than one road.

Each of the next q lines contains a pair of integers l__i and r__i (1  ≤ l__i ≤ r__i ≤ m) — a guess from the historians about the remaining roads in the kingdom.

输入的第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n, q \le 1000$，），分别表示伟大王国中的城市数量、道路数量以及历史学家所作猜测的数量。

接下来的 $m$ 行中，第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $w_i$（$1 \le u_i, v_i \le n$，$0 \le w_i \le 10^9$），表示第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，其长度为 $w_i$。保证不存在连接同一城市的道路，且任意两个城市之间至多只有一条道路相连。

接下来的 $q$ 行中，每行包含一对整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le m$），表示历史学家关于王国中剩余道路的一次猜测。

For each guess print the minimum possible hardness of the division in described scenario.

对于每次猜测，请输出所述场景下划分的最小可能难度。