注意

yukicoder contest 279 (Zelkova and Cherry) の問題は 難易度順に並んではいない. よって, 問題文や難易度を表すの星の数, 正解者数等といった公開されている情報から問題を取捨選択することを強く推奨する.

お詫び

問題文

$N$ 人からなるグループがあり, 人 $i$ は最初エネルギーとして $A_i$ を持っている. 機械 $j$ を用いることによって, 人 $X_j$ と, 人 $Y_j$ の間でエネルギーのやり取りが出る. ただし, この機械は使い捨てである. より厳密には, 機械 $j$ を用いることによって, 以下の2つの行動のうち, 一方が1回だけできるようになる.

• ある正の実数 $g$ を選び, 人 $X_j$ の持っているエネルギーを $g$ 減らし, 人 $Y_j$ の持っているエネルギーを $g$ 増やす.
• ある正の実数 $g$ を選び, 人 $X_j$ の持っているエネルギーを $g$ 増やし, 人 $Y_j$ の持っているエネルギーを $g$ 減らす.

このグループのマネージャーであるあなたは $Q$ 個の機械を用いて, $i$ 番目の人のエネルギーをなるべく $B_i$ にしたい. そこで, 以下のように定義される不安度を最小化するように機械を使いたい.

 人 $i$ が持っているエネルギーが $E_i(i=1,\dots ,N)$ のときの不安度は ${\displaystyle \sum _{i=1}^N{P}_i(E_i-B_i{)}^2}$ である.

しかし, この機械は1個ずつしか作れず, また, 作るのに非常に時間がかかる. しかも, 使い捨てなので, 時間と不安度のトレードオフを考慮しなければならない. そこで, $q$ 個目の機械が完成した時点でどのくらい不安度を小さくできるかを考えたい.

より厳密には, $q=1,\dots ,Q$ に対して, 以下の問題を解け.

機械$1$, $\dots$, 機械$q$ の $q$ 個の機械のみを用いて実現できる不安度の最小値を求めよ. ただし, 使わない機械があってもよい.

制約

• $2\le N\le {10}^5$
• $0\le A_i\le 10$
• $0\le B_i\le 10$
• $0\le P_i\le 10$
• $1\le Q\le 2\times {10}^5$
• $1\le X_j,Y_j\le N$
• $X_j\ne Y_j$
• 入力は全て整数.

入力

$N$
$A_1\dots A_N$
$B_1\dots B_N$
$P_1\dots P_N$
$Q$
$X_1{Y}_1$
$⋮$
$X_Q{Y}_Q$

出力

サンプル

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

1.0
1.0
0.3333333333333333

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

158.75
122.17857142857143
120.17857142857143
82.67857142857143
75.85526315789474
43.41666666666667
42.06666666666667

26
1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3
20 24
24 26
26 20

0.0
0.0
0.0