支付或收取

题目描述

有编号为 $1,\ldots,N$ 的 $N$ 个城镇,以及编号为 $1,\ldots,M$ 的 $M$ 条道路。

道路 $i$ 连接城镇 $A_i$ 和 $B_i$。使用道路时,分数按如下方式变化:

沿道路 $i$ 从城镇 $A_i$ 移动到城镇 $B_i$ 时,分数增加 $C_i$;沿道路 $i$ 从城镇 $B_i$ 移动到城镇 $A_i$ 时,分数减少 $C_i$。

分数可能变为负数。

请回答下列 $Q$ 个询问。

从城镇 $X_i$ 出发,初始分数为 $0$。求到达城镇 $Y_i$ 时分数能达到的最大值。

这里,若无法从城镇 $X_i$ 到达城镇 $Y_i$,则输出 nan;若在城镇 $Y_i$ 时分数可以任意大,则输出 inf。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$ $Q$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_M$ $B_M$ $C_M$
$X_1$ $Y_1$
$\vdots$
$X_Q$ $Y_Q$

输出格式

按照题目描述输出 $Q$ 行。

第 $i$ 行输出第 $i$ 个询问的答案。

样例

5 5 3
1 2 1
1 2 2
3 4 1
4 5 1
3 5 2
5 3
1 2
3 1

-2
inf
nan

对于第一个询问,沿道路 $5$ 从城镇 $5$ 移动到城镇 $3$,到达城镇 $3$ 时分数为 $-2$。

由于无法使分数更大,答案为 $-2$。

对于第二个询问,按如下方式旅行,可以使到达城镇 $2$ 时的分数任意大: 反复执行「沿道路 $2$ 从城镇 $1$ 移动到城镇 $2$,再沿道路 $1$ 从城镇 $2$ 移动到城镇 $1$」任意多次, 最后沿道路 $2$ 从城镇 $1$ 移动到城镇 $2$。

对于第三个询问,无法从城镇 $3$ 到达城镇 $1$。

2 1 1
1 1 1
1 1

inf

道路的两个端点可能相同,询问中的两个城镇也可能相同。

9 7 5
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
3 2 3
8 4 6
2 6
4 3
3 8
3 2
7 9

inf
nan
nan
inf
-9

数据范围

• $2 \le N \le 10^5$
• $0 \le M \le 10^5$
• $1 \le Q \le 10^5$
• $1 \le A_i, B_i, X_i, Y_i \le N$
• $0 \le C_i \le 10^9$
• 输入中的所有值均为整数。