3 3
2 0 11000
5 0 12000
3 3 10000
1 3
3 0
5 3

1
3
2

4 2
2 -2 10000
-2 1 12000
1 -3 12000
4 5 19000
1 5
4 1

4
1
2
3