Input
3
2 3 5
1 3 3
5
1 4
2 2
1 2
2 1
1 1
Output
14.0000000000
12.0000000000
8.0000000000
6.0000000000
4.0000000000
Input
6
1 5 3
5 3 2
6 1 7
1 4 4
5 2 3
5
1 2
2 1
3 5
4 1
5 2
Output
19.6000000000
18.6000000000
16.6000000000
13.6000000000
12.6000000000