Description

现给定一个电阻网络，已知其中每条边上的电阻，和若干个点和负极之间的电压（电源电压不变） ，现在求任意两点之间的电压。

Input Format

第一行四个正整数 $n,m,k,q$，表示有 $n$ 个节点（可能是几个点用导线相连接，与一个点等价，编号为 $1$ 至 $n$，$0$ 号节点为电源负极），$m$ 个定值电阻（每个定值电阻连接两个点），电源正极有 $k$ 个接口，有 $q$ 个询问。

接下来 $k$ 行，每行两个正整数，表示这个正极的编号与该接线柱与电源负极之间的电压 $u_i$。

再接下来 $m$ 行，每行三个正整数 $v_i,w_i,r_i$，表示节点 $v_i$ 与 $w_i$ 之间有一条阻值为 $r_i$ 的电阻丝。

再接下来 $q$ 行，每行两个正整数 $a_i,b_i$，表示要求 $a_i$ 与 $b_i$ 之间的电压。

Output Format

一共 $q$ 行，每行一个实数表示 $a_i$ 与 $b_i$ 之间的电压（保留两位小数）。若 $a_i$ 点电压小于 $b_i$ 点电压，输出负值。

3 5 1 3
1 18
1 2 6
1 3 2
2 3 6
3 0 6
2 0 2
1 0
2 3
1 2

18.00
-6.00
12.00

Hint

【数据范围】

对于 $10\%$ 的数据，$1\le q\le 10$；

对于 $20\%$ 的数据，$1\le n\le 10$，且保证电路为串联、并联或混联；

对于 $40\%$ 的数据，$1\le n\le 40$，$k\le 5$；

对于 $100\%$ 的数据，$1\le k\le n\le 200$，$1\le m\le 2\times 10^5$，$1\le r_i,u_i\le 10^4$，$1\le q\le 10^6$。

【时空限制】

时间限制：1.00s，空间限制：125.00MB。

【样例解释】

如图所示。