8 3 0 1
0 0 0 0 1
1 1000 0 0 1
2 1000 500 0 1
3 0 500 0 1
4 0 0 500 1
5 1000 0 500 1
6 1000 500 500 1
7 0 500 500 1
6 1
1
4 0 1 2 3 1
1
4 4 5 6 7 1
1
4 0 1 5 4 1
1
4 1 2 6 5 1
1
4 2 3 7 6 1
1
4 3 0 4 7 1
0