2
10
0
1 1
1 1
2 3
3
100
0
0 1 2
1 2 3
5 3 7
7
1000
0
0 0 0 0 0 0 0
1 1 1 1 1 1 1
2 3 4 5 6 7 8
-1