5 47 1000000000
150574 105585 917852 311008 914644
265916428 656735819 878073539 45819469 64103340 674631707 679508048 498509551 983852390 698424833 641486490 112332998 16961741 405611870 494021521 999999569 790212618 996261053 318264864 721320618 622925461 418292943 360411121 790228135 249555141 917956500 471578141 311676601 191700234 837375471 783038956 795302656 13901366 831040088 476180274 442717582 947603610 923119082 756562541 455307591 617657956 77467004 391456561 159416934 855736832 202201863 420231678