1000000000 1000000000 
47
1 8465310
1 358403181
1 683447134
1000000000 133145006
1 553666286
1000000000 194041605
1000000000 513494529
1 278840199
1 69909135
1 106923811
1 225450721
1000000000 87708701
1 39202255
1 37379061
1 466701607
1 3615545
1 29331901
1 48581613
1000000000 391749388
1 33557677
1 436291073
1 939151438
1 473038165
1 659598369
1 634446253
1 554160985
1 392289611
1000000000 150378796
1000000000 189920160
1 139695685
1 366496749
1000000000 84970744
1 110710191
1 247776868
1 416998222
1 368026285
1 170427799
1 103301481
1 318773941
1 222071041
1 8670529
1 675016434
1000000000 738066085
1 82426873
1 450219949
1000000000 35766291
1 709031779