3
1 2 3 3
2 3 2 2
3 4 2 2
4
3 5
1 2
4 2
3 3
2
5 10 2 10
100 100 100 100
2
5 13
100 101
0