1000000 100 10 /\\\/\///\ \/\\\\\/// //\\\/\/\\ /\\\//\/\/ \/\/\\///\ //\\\\/\\/ /\\/\\/\// \/\\\//\\/ \/\\\/\//\ /\\\//\\// \\/\\/\/// //\\\//\\\ ///////\/\ /\\//\/\/\ \\\\\///\/ //\\/\//// /\///\//\/ /\//\\//\\ \\/\\/\\\\ //\\/\\/\\ /\/\\\/\/\ \\//////\/ \\/\\\/\/\ \\\/\//\/\ \//\//\\// \/\\\\\/// \/\/\/\/\\ /\\\///\\/ /\\//////\ \//\\/\\/\ /\\/\///\\ //\/\\//\\ \/\/\\\/\\ \\\\\\/\\\ \\\\\/\\\/ /\//\\///\ /\\\\/\\// \///\/\/\/ ///\\\/\/\ \\/////\// \\//\//\// \\///\\\/\ \\\/\///\/ ///\\\\\// ///\\//\\\ \/\//\//// \\\\//\\// \\\\////// \/\/\//\// \\/\\/\\/\ ////\/\/\/ \/\/\\//\/ \/\\//\//\ \//\/\\\// /\///\/\/\ //\////\/\ \///\//\// /\/\\\//\\ /\//\/\\/\ /\//\\\\// \/\\/\/\// //\/\\//// ///\\\\/// /\/\/\/\// \\\/\/\\/\ \\//\///\/ \/\/\/\\/\ /\\\\///\/ \\////\/\/ \\//\\\//\ \\/\/\///\ /\//\\/\// \\\\/\\//\ \//\//\/\/ ///\/\//\\ /////\///\ \\/\/\\/\/ //\\//\\// \/////\\// ///\\///// /\\/\///\/ /\\\\//\/\ //\/\/\\\/ \/////\/// \\///\\/\\ \\///\///\ ////\/\\\\ \\//////\/ \\/\/\//\\ \\\////\/\ \//\/\\\\/ /\\\\\/\\\ ////\////\ //\///\//\ ///\\\//// \//\\\//// /\\\\\/\/\ \\\\\/\\\\ \\/\\\\\// /\///\\\\\ 779888 889536 776184 240727 301194 763549 549577 781741 757929 892343 328321 595634 117156 699473 226033 891316 975146 878753 28291 148403 296828 806162 529649 969892 813616 451714 58252 592686 795568 367429 958454 248304 55609 588512 786088 962745 80157 392078 692781 159119 600065 163711 459621 924969 400159 815380 597187 846517 167237 932196 805392 822355 493013 254843 524070 697943 255427 320789 225525 333131 40922 35431 550465 924010 852535 780823 314977 736743 194572 268287 291714 491748 312543 573038 129059 333627 103112 1126 553815 758393 989878 914079 499974 465438 815019 729091 186091 516254 205692 617968 452055 121507 590994 765689 154477 467656 587755 280037 979364 981279 447385 678319 101640 370029 939202 577220 456378 506537 301854 548808 671595 510016 219965 470929 696805 188884 191102 612586 675074 53624 657049 656722 54195 413814 575382 540859 559290 233865 479636 648651 413104 376227 411587 794078 111808 207400 388906 808578 936106 488241 298082 816633 678913 682699 282648 938107 64749 47477 369103 161393 379818 894309 795676 498299 853319 880516 362472 281323 578600 272429 930610 195016 608645 760434 283914 501964 655465 715287 343255 276774 598835 814293 185106 444281 797464 732760 217865 74907 95775 363330 279389 622871 935011 856934 284292 575404 558741 829325 117128 561931 500152 827957 639685 998236 638499 12044 673519 488890 580547 991097 232074 609330 48406 223444 350192 697097 528496 621801 574351 76659 667834 185594 684648 522844 9134 457018 83793 246563 29277 739474 195252 507610 876905 722911 80590 897608 489803 518258 37617 675815 744654 738639 120642 770470 504978 922607 786171 530535 580106 719230 350954 400834 829182 682013 900593 852289 431626 763105 434052 734626 582877 387410 124654 414744 459643 882477 12 361482 461116 375587 440208 436947 221194 867544 481471 51456 227559 838436 460212 19861 552997 538133 434395 590025 522412 152619 989878 712645 688823 642587 197212 837544 747159 879501 586677 447814 700911 851166 799999 151652 863414 413599 979852 806718 474424 978067 728898 973826 554325 435893 791321 268562 472193 710704 94945 385286 580354 91493 293689 948136 464053 166697 135193 173814 314506 727684 253641 585443 40259 582067 650471 680790 190329 626854 69670 958633 983639 345859 899849 413291 28445 388257 563628 709599 359326 832846 94396 229179 883522 941194 268281 956970 786053 549385 432251 105226 281334 964917 432426 417903 214329 777322 448837 417566 438534 181305 59740 825171 798823 338981 186070 701563 95230 458728 116652 267963 756861 260335 954796 829863 937579 255002 598135 840587 370086 23166 209283 241574 387036 432802 315225 539178 806480 7173 355672 526206 892636 984534 803568 425340 433961 629243 476584 546547 613688 724427 550554 216293 522204 180372 817009 147978 821950 547093 95537 660492 282520 835909 660656 76169 411003 932107 162517 931157 675465 735619 658208 442613 657531 704767 900258 897892 863964 420100 514432 879634 611595 193609 652020 848864 195518 787963 800460 608101 523002 266044 264873 141484 481307 86495 332098 591412 676115 4078 341854 124014 605539 169957 747293 221955 843235 510132 608880 438412 392384 109120 889885 428376 345912 92706 845372 367145 534560 906726 574076 339767 464223 894030 559583 412331 24304 930445 750841 143717 993124 484045 306741 419256 322205 485417 413904 336616 99989 492723 541404 274611 613269 50159 124287 873477 902206 621846 956913 561666 48771 686549 582849 807360 827181 278475 369617 832330 60886 884430 23829 328350 484078 841831 124377 866096 232954 480849 659832 413861 9935 209278 874149 212953 669339 849810 189670 592857 831517 425894 846099 694826 455720 801222 41948 605120 61220 159156 588481 160264 332237 394403 880791 232350 113778 995004 456906 275671 571447 735196 155349 484921 803092 649364 617547 845630 594067 734760 66194 947093 882965 937041 517795 497569 555598 45627 870924 215480 650437 935623 192494 663077 936405 628682 929662 505830 215727 286412 983560 985454 430614 205259 14823 463012 648545 558965 21839 538083 189628 419953 979652 469112 573223 586199 83232 835879 221558 124787 171665 960487 621007 76102 1688 702881 475951 323461 47563 720500 184741 496408 907923 347444 231510 636700 186607 941671 35511 111970 133680 643463 76630 903854 376955 956162 135826 203512 192202 480509 347102 108014 230379 374413 642690 985392 826047 666748 722138 812307 502652 995338 207381 724639 727980 527658 235127 804049 792108 582144 819863 815322 887022 711978 826594 628957 254263 475124 14230 401141 795041 607202 320264 814509 572378 606314 393119 658438 500644 218807 415062 416180 352595 347623 679550 7073 620050 908430 112121 569065 989662 740337 247808 276253 745609 548940 47135 466176 364537 643597 537268 517901 133926 475798 766899 769070 125599 122431 983972 976134 805318 900241 849827 442217 727567 348556 884128 177311 654469 996642 162269 543909 273798 693050 415347 497899 773378 683758 194125 905302 903039 496909 92266 452800 273176 49050 845983 141683 534649 877066 884371 618546 192869 496842 301186 375153 674737 804472 766331 251928 728774 324453 788450 310659 640546 113625 654830 485380 690263 27279 495724 172960 221195 136436 452602 868942 634679 72044 242317 579900 779816 236814 143340 844169 627585 533411 710578 140492 897143 732394 724816 158604 113171 322455 784264 170373 982836 973520 472755 309737 98634 484591 430012 780829 547548 141123 69411 216568 470275 912462 239996 720135 998189 962312 768685 297548 54171 470298 579251 396410 16227 295397 661277 320059 53934 605753 281616 790506 641147 327646 420161 623001 453595 478798 502462 439501 358835 858040 406630 976765 399549 212095 63020 700118 333959 779833 237080 987514 387570 378673 340485 943484 504564 977510 507172 188325 349207 8266 368120 671859 665336 326659 682905 724885 347336 785261 10801 34992 214415 783573 487233 583645 547300 225920 54365 448744 537718 781474 645996 139730 639110 638632 517097 542609 787626 964719 107429 798731 380300 997258 588674 456350 302633 518847 457977 710235 514515 254731 558101 993350 419695 309850 913078 600664 93944 586703 560720 742269 842362 704002 72489 87447 254231 327229 53470 972473 851078 649663 530078 361708 40143 873913 387117 111469 331984 298195 584355 351725 754107 518760 273515 834000 321174 453829 43908 939503 115897 815470 240003 655702 335444 616666 264527 103558 207910 17458 858404 615412 705415 879446 139089 595336 173151 699287 718138 310943 348332 60094 365334 577098 526592 28036 813938 728589 257089 218008 248492 61600 367272 798876 691576 429874 679042 207528 805535 527777 373106 677318 855035 583042 303341 420148 513533 964512 969020 464549 289959 891829 230526 684480 518930 563442 770211 344480 894826 509821 583346 611858 927596 751406 954372 675162 494639 331025 582598 758126 808472 833511 875451 406137 516196 589348 432312 801178 303714 879922 685095 785250 360630 55917 619460 62298 662552 829478 374435 51130 430163 905632 5 1 2 4 7 8 -1 2 6 -1 8