7 2
4 1 1 1 2
3 5 2 1 2
5 1
5 5 1 -1 1
8 3
1 2 1 0 0
3 1 8 3 -1
3 4 8 2 -3
0