很久以前,有一个伟大的王国,由伟大的艾莉亚和帕里大帝统治。这两个人对自己喜欢的数字有些疑问,所以他们决定瓜分这个伟大的王国。
这个伟大的王国由编号为 1 到 n 的 n 个城市以及这些城市之间编号为 1 到 m 的 m 条双向道路组成。第 i 条路的长度等于 wi。大雅利安和帕里大帝正在讨论破坏一些道路的前缀(所有数字小于某个x的道路)和后缀(所有数字大于某个x的道路),这样就只剩下数字为l,l + 1,...,r - 1和r的道路。
之后他们会将这个伟大的王国分成两块(每个城市都属于一块),这样划分的难度就会降到最低。分区的硬度是指其两个端点位于王国同一部分的道路的最大长度。如果没有这样的道路,则划分的硬度被认为等于-1。
历史学家找到了伟大王国的地图,他们对那些伟大统治者选择的l和r有q个猜测。给定这些数据,对于每个猜测 li 和 ri 都会打印王国划分的最小可能硬度。
输入
输入的第一行包含三个整数 n、m 和 q (1 ≤ n, q ≤ 1000, $$1 \leq m \leq \frac{n \times (n-1)}{2}$$) – 分别是大王国中的城市和道路的数量以及猜测的数量。
接下来 m 行中的第 i 行包含三个整数 ui、vi 和 wi (1 ≤ ui, vi ≤ n, 0 ≤ wi ≤ 109),表示连接城市 ui 和 vi 的道路编号 i,其长度等于 wi。保证没有道路将城市与其本身连接起来,并且没有一对城市由多条道路连接。
接下来的 q 行中的每一行都包含一对整数 li 和 ri (1 ≤ li ≤ ri ≤ m)——历史学家对王国中剩余道路的猜测。
输出
对于每个猜测,打印所描述场景中划分的最小可能硬度。
示例
输入 #1
5 6 5 5 4 86 5 1 0 1 3 38 2 1 33 2 4 28 2 3 40 3 5 2 6 1 3 2 3 1 6
输出 #1
-1 33 -1 -1 33