友情提示：380元/半年，儿童学编程，就上码丁实验室。
【题目描述】
城市中建立了$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$。