10 12 1000000000
313957685 818603188
387010958 567539413
1000000000 645615315
0 306911040
408490846 256102866
0 797355213
921743263 805856654
1000000000 426613333
1000000000 234556862
622808474 345098189
5 2
7 2
3 8
9 10
10 7
4 2
4 5
4 6
2 6
8 9
1 7
10 5