4
2 1
9 16
1 2 4 8
3 3
0 1 0
1 2 1 0
2 3 2 0
1 3 1 8
8 10
3 0 1 2 5 0 8 0
1 3 9 0
3 8 5 2
7 8 11 90
2 5 1 0
1 8 7 15
2 4 1 0
3 4 3 10
2 5 9 16
4 6 25 25
1 7 6 16
4 3
1000000000 1000000000 1000000000 1000000000
1 2 1000000000 2000000000
2 3 1000000000 0
3 4 1000000000 0