2583: 地壳运动

JZ是一个坐落在地壳运动活跃的山区的城市，常受地质灾害的袭击。
城市中建立了N个应急避难所以躲避灾害，这些避难所从1～N编号。此外有M条道路连接这些避难所，所有避难所间均可通过这M条道路直接或间接到达。由于是在规划良好的市区，道路可以由若干个平行于x或y坐标轴的线段组成，所以避难所xi和yi之间的道路可以用(ui,vi)来表示，道路的长度为ui+vi。由于地壳运动会导致地面拉伸或收缩，可用两个实数k1,k2描述城市的伸缩程度，此时某条道路的实际长度变为ui*k1+vi*k2。有若干个独立的询问，每次询问给出k1和k2，政府都希望在此地壳运动前提下，以最小的花费维护其中一些道路，使得只用这些被维护的道路仍能使所有避难所间相互连通。因为花费与道路的实际总长成正比，所以你需要对每一次询问求出被维护道路的最短实际总长。

第一行三个整数N,M,Q，分别表示避难所数量、道路数量、询问数量。
接下来M行每行四个整数xi,yi,ui,vi。xi,yi表示道路连接的两个避难所编号，ui,vi意义如上文所述。
最后Q行每行两个实数，表示每次询问的k1和k2。

输出Q行，每行一个实数，表示实际总长，保留三位小数

4 8 3
2 1 3 6 
3 2 0 7 
4 1 7 0
1 4 4 6 
2 1 2 7 
1 2 2 10
2 2 5 5 
4 4 8 9
0.626436771146 0.472537839745
0.977631137354 0.190235819672
0.418883351791 0.221987861358

12.253
9.671
6.878