3
2 1 
1 1000000 
1000000 1000000 
1 1 
1 1
5 2
1 2
3 1
4 5
7 2
8 6