题目描述

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

输入

第一行三个整数$N,M,Q$，分别表示避难所数量、道路数量、询问数量。 接下来$M$行每行四个整数$x_i,y_i,u_i,v_i。x_i,y_i$表示道路连接的两个避难所编号，$u_i,v_i$意义如上文所述。 最后$Q$行每行两个实数，表示每次询问的的$k_1$和$k_2$。

输出

输出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

提示

【数据规模及约定】 对于30%的数据，$N≤30，M≤3000，Q≤3000$； 对于另外30%的数据，$N≤20，M≤25000，Q≤10000$； 对于100%的数据，$N≤35，M≤25000，Q≤200000，1≤x_i,y_i≤N，0≤u_i,v_i≤10^6，k_1,k_2>0$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。