1000000 4000000 5000000 2000000
11 0 1.0 8 7 8
0  0
2  0
2  2
1  2
1  1
0  1
1  0
2  1
1.5  1.5
0.5  0.5
1.5  0.5
12
1 7 2 11
-1 12 5
1 8 3 9
-2 8 6
1 6 1 10
-6 11 10
1 7 5 10
5 10 11
1 5 7 11
4 1 7
1 5 8 9
7 2 9
1 8 5 11
6 5 12
1 3 4 9
-3 9 2
1 4 5 9
-4 6 8
1 5 6 10
-5 3 4
1 1 7 10
-1 4 3
1 2 8 11
-2 7 1