Input: 505
316797346 997765906 983908715 693055816 611766285 386737317 354128851 54461260 495493684 921105535 986215140 837198569 814440310 555192935 603302047 907232310 56971376 520441287 870175836 20770322 425593717 733883231 306389542 135700734 691630671 447255085 227747652 253975023 14169246 975461551 829801990 531991633 778119173 588735346 622396101 66640060 268514415 12393610 605073458 962301120 217439255 890843141 518987724 610512763 282094684 473415495 12876029 68679792 320656409 351791739 194201909 489689015 765586919 792395794 162972539 215827652 145865520 608925791 305477065 417637209 561771521 958230240 565186183 404431232 516438227 301017003 921516488 41515574 261866630 808302560 882263156 565616432 76911926 945231406 456113618 837335590 395498436 661832384 920707236 570270311 627836345 734769768 81542629 892217215 989081602 73306560 269226783 10498261 863281850 433290970 541335181 122613827 521390861 97805719 146977672 315860591 395370234 605216302 714159670 234805033 36773085 245159948 354153657 858496274 332867894 19254430 942770751 677324925 386943227 576325042 214525221 309310465 650161586 887209431 860172123 700381379 803537763 584097012 795745677 259302291 544161384 974086979 338004601 919182241 732198622 525495053 890416224 180410922 661828544 355571353 166864550 115828294 553472455 518650799 706707497 440055258 134072178 987067119 415120341 767389318 102549111 273360127 803449254 639105518 118370376 690441838 885041805 81161681 803077458 136008836 877501179 651466728 459201724 139880876 23570385 403422502 931498042 927963879 228571547 108473521 262098162 277045735 475656660 550261928 644960220 91038076 66912664 468794527 633481388 165887827 233264094 787854963 744429676 479075881 562200608 959017028 199557233 660076316 728367517 659984058 150242971 481121962 912326049 687920803 888592539 926305287 549355144 80361088 299877095 971871161 652678957 284475690 778159282 681246531 138696889 481362104 539365355 611986842 814114871 956787450 973331891 408348630 112449357 731227786 591213035 856817256 208735764 326825022 149794227 167182135 272395807 998148809 261957485 198883511 439944906 404975238 346665824 231216830 604211878 652323831 311585661 933076188 855826521 107553666 518723331 14613096 915134498 496036869 573782647 948571938 510754144 231443644 177852559 14186923 878673358 790371115 832171012 3667994 888823970 400526409 337849211 751533132 804036470 624194501 605589582 138103540 248487695 605077626 632184071 765400652 155172636 906755187 484464537 158334511 554711482 162029641 250206489 628012544 242155389 379614817 843798756 246716653 125002286 58787432 974999535 733161962 643869576 393601575 837190550 769411712 160365500 265452700 686027449 5483095 174106702 516455234 540443768 983100067 619178805 878546532 933771013 99800053 76588622 404922937 243149943 330579997 440900339 134276307 738063639 878106545 921877249 142383837 586574975 520577850 390680968 547707892 184277 345598611 111172933 486065135 689661161 998911038 160670153 919623607 321589161 977641450 498568568 945586189 506215755 527462457 591693866 595252341 93716321 545671320 964989811 438156606 438440037 627319968 767356360 252491270 958499216 262322001 474260082 816308968 616284334 437472619 432747132 108346909 686379004 890877191 61583783 588409637 688014667 225857899 685793208 468220446 772484387 200873261 697295481 204221434 591424949 519672607 322596326 599736949 426658777 175844456 509138809 354730099 656580757 108400083 754879705 447404137 172237084 240717707 645368305 415749592 28272548 624385043 848145786 95283198 982544243 286958614 696582694 660405022 968263599 915875412 153741561 655841958 405032570 166994736 709656496 140525370 368985789 798490982 97348022 780743177 305699480 796957497 267629025 434570628 452809778 956377050 685928376 549213370 207264375 662612970 623642719 379215215 477681853 158086939 562135476 906937781 690617337 911516044 585109265 99603002 132498458 96299891 961656433 59912456 140836754 530123254 345431299 781493677 354900599 862592744 525587368 299315950 571582564 800318305 252216581 252082180 699078689 935845472 151430000 67440436 957411454 116474037 433646287 18503947 595977671 140712599 183425797 733372407 873485896 251426455 70577210 895171993 496777932 489445099 293309731 216026666 120026888 302054923 333894530 70459763 427339633 178632774 300499682 717441598 858689001 371110889 759809607 306936967 736924689 844157135 492478970 967604190 387289894 356403043 442785863 25154670 281428542 811937456 839546373 706091500 537988655 522513341 907450565 188499851 438753429 547375517 170000755 132198890 234555248 641810799 149691483 55138284 636747850 333000239 665353537 18897427 590338382 739904130 521095721 554566218 315752486 694461361 276268248 879039591 547106823 525488854 279519940 255240514 766649963 217076217 389642421 147496014 895238557 282018896 619336196 132938812 739549980 37985073 313420105 196589393 777148388 892259397 970841596 734866505 750391506 432236977 726964110 607843497 227422135
Output: 998911038 998148809 997765906 989081602 987067119 986215140 983908715 983100067 982544243 977641450 975461551 974999535 974086979 973331891 971871161 970841596 968263599 967604190 964989811 962301120 961656433 959017028 958499216 958230240 957411454 956787450 956377050 948571938 945586189 945231406 942770751 935845472 933771013 933076188 931498042 927963879 926305287 921877249 921516488 921105535 920707236 919623607 919182241 915875412 915134498 912326049 911516044 907450565 907232310 906937781 906755187 895238557 895171993 892259397 892217215 890877191 890843141 890416224 888823970 888592539 887209431 885041805 882263156 879039591 878673358 878546532 878106545 877501179 873485896 870175836 863281850 862592744 860172123 858689001 858496274 856817256 855826521 848145786 844157135 843798756 839546373 837335590 837198569 837190550 832171012 829801990 816308968 814440310 814114871 811937456 808302560 804036470 803537763 803449254 803077458 800318305 798490982 796957497 795745677 792395794 790371115 787854963 781493677 780743177 778159282 778119173 777148388 772484387 769411712 767389318 767356360 766649963 765586919 765400652 759809607 754879705 751533132 750391506 744429676 739904130 739549980 738063639 736924689 734866505 734769768 733883231 733372407 733161962 732198622 731227786 728367517 726964110 717441598 714159670 709656496 706707497 706091500 700381379 699078689 697295481 696582694 694461361 693055816 691630671 690617337 690441838 689661161 688014667 687920803 686379004 686027449 685928376 685793208 681246531 677324925 665353537 662612970 661832384 661828544 660405022 660076316 659984058 656580757 655841958 652678957 652323831 651466728 650161586 645368305 644960220 643869576 641810799 639105518 636747850 633481388 632184071 628012544 627836345 627319968 624385043 624194501 623642719 622396101 619336196 619178805 616284334 611986842 611766285 610512763 608925791 607843497 605589582 605216302 605077626 605073458 604211878 603302047 599736949 595977671 595252341 591693866 591424949 591213035 590338382 588735346 588409637 586574975 585109265 584097012 576325042 573782647 571582564 570270311 565616432 565186183 562200608 562135476 561771521 555192935 554711482 554566218 553472455 550261928 549355144 549213370 547707892 547375517 547106823 545671320 544161384 541335181 540443768 539365355 537988655 531991633 530123254 527462457 525587368 525495053 525488854 522513341 521390861 521095721 520577850 520441287 519672607 518987724 518723331 518650799 516455234 516438227 510754144 509138809 506215755 498568568 496777932 496036869 495493684 492478970 489689015 489445099 486065135 484464537 481362104 481121962 479075881 477681853 475656660 474260082 473415495 468794527 468220446 459201724 456113618 452809778 447404137 447255085 442785863 440900339 440055258 439944906 438753429 438440037 438156606 437472619 434570628 433646287 433290970 432747132 432236977 427339633 426658777 425593717 417637209 415749592 415120341 408348630 405032570 404975238 404922937 404431232 403422502 400526409 395498436 395370234 393601575 390680968 389642421 387289894 386943227 386737317 379614817 379215215 371110889 368985789 356403043 355571353 354900599 354730099 354153657 354128851 351791739 346665824 345598611 345431299 338004601 337849211 333894530 333000239 332867894 330579997 326825022 322596326 321589161 320656409 316797346 315860591 315752486 313420105 311585661 309310465 306936967 306389542 305699480 305477065 302054923 301017003 300499682 299877095 299315950 293309731 286958614 284475690 282094684 282018896 281428542 279519940 277045735 276268248 273360127 272395807 269226783 268514415 267629025 265452700 262322001 262098162 261957485 261866630 259302291 255240514 253975023 252491270 252216581 252082180 251426455 250206489 248487695 246716653 245159948 243149943 242155389 240717707 234805033 234555248 233264094 231443644 231216830 228571547 227747652 227422135 225857899 217439255 217076217 216026666 215827652 214525221 208735764 207264375 204221434 200873261 199557233 198883511 196589393 194201909 188499851 183425797 180410922 178632774 177852559 175844456 174106702 172237084 170000755 167182135 166994736 166864550 165887827 162972539 162029641 160670153 160365500 158334511 158086939 155172636 153741561 151430000 150242971 149794227 149691483 147496014 146977672 145865520 142383837 140836754 140712599 140525370 139880876 138696889 138103540 136008836 135700734 134276307 134072178 132938812 132498458 132198890 125002286 122613827 120026888 118370376 116474037 115828294 112449357 111172933 108473521 108400083 108346909 107553666 102549111 99800053 99603002 97805719 97348022 96299891 95283198 93716321 91038076 81542629 81161681 80361088 76911926 76588622 73306560 70577210 70459763 68679792 67440436 66912664 66640060 61583783 59912456 58787432 56971376 55138284 54461260 41515574 37985073 36773085 28272548 25154670 23570385 20770322 19254430 18897427 18503947 14613096 14186923 14169246 12876029 12393610 10498261 5483095 3667994 184277