1000000 99 9 \\/////\/ /////\/\\ /\\\\/\\/ ///\\/\// \//\/\\/\ ///\\/\\\ \/\//\//\ /\\/\\/\/ \/\\///\\ \/\/\\\\/ \////\\/\ \\//\\//\ ///\\\\\/ \/\//\\// /\///\//\ \\\\/\\\\ \\\//\/// /////\/\\ \\/////\\ \\\\////\ \/\\//\\\ //\//\\\/ //////\// /\/\/\//\ /\\/\\/\\ //\//\/\\ \\/\\//// \/\/\///\ \\\//\/\/ \/\/\///\ \/\\\\//\ \\\/\/\// \\/\\//\\ /\\\///\\ /////\/// //\///\\/ \\\//\/// /\\\/\\\\ \/\/\/\\\ \//\/\/\\ \/\/////\ \/\\////\ \//\\\\// ///\\/\/\ \\\/\///\ \\////\\\ //\\\//\/ /\////\\\ /\\////// /\\/\\\\/ \/\///\\\ /\/\\//// //\//\\/\ /\\////// \////\/\\ //\/\\/\/ /\/\///// \\//\/\\/ \\\\\\\/\ \\\//\\/\ \/\/////\ \\\\\/\// /\\/\/\// /////\/\/ /\\\\\\\/ \/\\/\//\ \\///\//\ \//////\\ \/\\/\/\\ //\\/\\// \\/\\/\// ///\\///\ \/\\/\\/\ /\///\\\/ /\\/////\ \/\\///\\ /\\\/\\/\ \\///\\// ////\\\\\ \///\//\\ /\\//\\/\ \/\/\//\/ \\/\\/\\/ /\\\\//\\ //\\\\/\/ \/\\\\\// \\/\/\\\\ /\\/\/\/\ /\/\\\/// /\\\\\\// \/////\\/ //\\\///\ \//\\///\ //\\/\\\/ \\/\/\\/\ ////\//\/ \///\\/\\ /\\\//\\\ \\\\//\\\ 406223 494378 153005 225503 368550 361020 33203 213629 340885 492090 450257 366268 788187 45395 741841 979942 750890 434378 852847 810199 530473 413496 797851 380483 493810 790921 331322 682542 487124 399995 148966 386482 535058 538978 570921 722813 92321 714791 376646 268304 747822 499844 588784 872833 709270 111177 183505 611578 578477 762587 94341 818615 63800 373936 859932 962060 112498 411283 906203 731933 603467 501478 74171 554468 376612 805787 549417 421935 671636 494971 122501 179808 246374 545503 372387 239147 637017 483833 981005 752027 46239 803212 939710 39949 552542 234160 3240 46579 482418 259279 417327 899410 142441 856491 809389 318276 846661 694422 278700 991287 360830 297335 899119 297837 505149 57292 549609 518906 774562 275235 364355 612937 360064 667487 73179 796951 15260 749689 479616 601654 855537 108605 482359 984140 922030 298505 159609 726865 227766 675281 171954 5333 148575 953630 409668 192631 261300 158538 982274 399855 752179 124805 590453 495173 742224 944083 287963 191703 282160 146124 888867 611927 517999 160219 517746 33803 388827 730432 804385 398156 145462 260174 502716 853575 734903 872621 936772 184191 303498 332249 400750 280329 829772 473313 919843 283854 408143 165609 139198 147980 622044 223592 842385 908310 319404 797355 667552 677840 339246 754000 794467 931123 33029 52940 25289 591631 392391 134502 623728 762756 519551 946617 649774 813896 159659 374454 173835 580516 68798 650208 269444 219191 711647 287054 657098 850289 604777 994988 732289 710105 743977 183674 828609 589768 652195 797707 922585 642988 562574 129032 878279 929286 90963 390059 441345 940588 981586 584644 965807 468040 111196 227320 923310 492438 783866 991484 44302 611050 59045 991710 734869 981224 368716 224893 598523 886218 190289 497676 12844 828958 321932 516371 469833 794821 417606 883950 378727 635254 608127 180364 597966 574648 700842 558385 187067 698283 430828 760756 478558 628096 679200 412354 988125 39164 535573 171993 834383 813946 994510 647374 410626 746150 247425 316360 253558 872898 833177 829634 29280 805604 541685 383949 215016 354998 712422 957963 921323 462709 208373 821557 473593 152755 676698 367766 176920 855318 708358 757838 133247 937174 750234 447185 272540 742851 454574 843749 357839 862908 522379 54183 880685 169017 752625 641543 277757 147074 217618 11527 932862 134773 632597 854336 500064 600324 457108 995484 735750 444981 803614 203997 236234 566176 474550 720405 820729 709813 7122 238764 430035 589875 692636 280734 5196 251058 901493 441402 602894 689690 993005 454884 292661 708394 170060 472851 768145 620466 416909 290388 522663 329048 913821 273669 975537 494039 417184 873627 824601 540476 5165 830236 148610 435176 553933 601190 424447 993168 221568 492710 759002 116352 141047 602850 61711 582227 778459 648560 956174 697149 477125 40572 718140 375938 737028 235974 241522 519484 784922 151458 472637 311832 912063 794614 784092 951257 941277 369343 224454 156244 192594 443020 688289 652019 343473 450497 830860 914483 319617 552662 355734 904229 401404 370774 738564 724272 587665 719521 824143 868813 27875 352234 360804 316746 551561 91193 167074 967688 264972 956073 484255 369597 687339 639019 207780 777971 956250 748802 444268 468679 528830 235013 396585 49131 859187 801953 895551 360420 646534 128212 349703 230156 183292 533875 815118 415825 764873 422949 928851 306356 386842 649957 728972 980172 773772 75652 334370 930945 298034 529444 906480 867601 895955 360574 831944 655373 279657 567773 171118 749213 763171 492065 223131 883064 902563 469949 537275 394797 138305 328186 434735 86494 704071 633906 795404 726015 919924 121429 947162 567515 981561 943655 443927 390991 25598 578240 480113 786317 781726 583563 743439 708187 363046 950791 327945 352530 147674 446537 401195 107551 340401 363192 87351 67524 930068 112720 330016 611096 410339 908832 661391 215875 928240 476940 452193 315396 306241 834123 706855 959531 53202 339625 713956 937822 83665 126279 144659 82712 89761 949590 128607 294118 632855 228960 813929 648744 946240 2495 418118 258454 334233 301156 750398 607992 28949 201233 46094 414765 477275 322335 136679 519781 157062 414329 391597 603815 608867 434783 120952 929420 966710 726565 93078 25922 424373 797425 778183 433994 164811 148800 888000 722361 377815 793953 82601 280635 586922 374968 611359 831436 469133 982269 193522 588861 146617 604219 699944 388213 611868 303377 301496 640365 885979 35636 927824 823987 40842 941483 655632 929512 640246 116946 881805 254402 814428 666264 690447 896651 480111 118400 941779 728032 197270 811876 749001 173810 206315 298413 889367 583496 287741 31004 60628 770428 521039 303877 228878 307897 408023 142799 468805 485700 341055 893621 797165 571504 982056 282375 27696 492968 545762 814698 367722 520937 268726 858644 310059 605316 254684 414865 352761 370273 266117 418241 178187 89015 977234 313815 497807 452309 856794 651611 238436 103709 188328 450601 608673 559363 719483 76784 475341 164754 390533 633973 956324 683879 330093 253517 894168 167604 863309 978854 87886 465342 599156 865150 771165 442528 490596 138602 318483 317062 163221 241105 163055 412659 390577 579951 353640 509755 420630 913875 661540 71881 898007 314976 226690 595675 537659 378000 247313 491521 30781 79340 767638 807585 312138 927765 399498 121142 903238 237951 713114 507404 440071 155249 706341 679942 330968 865542 95810 554841 412792 954286 680695 490318 13976 812462 216515 99140 791521 895708 6421 935019 79596 777252 330834 858506 786631 418693 285331 625913 299511 171477 752036 803240 25200 52281 615559 397975 763871 45038 993071 944668 297825 460995 957510 204320 863497 829468 905703 140386 581598 173617 214052 104306 31770 671756 891329 66295 177516 479759 808887 682538 30263 851052 327794 518873 81105 403307 338708 543909 545669 819879 558256 456260 136913 602257 342351 550335 659497 303532 32814 717813 447922 316367 576958 265047 629064 614310 396963 317674 602296 516722 533878 651080 510150 97732 112835 532575 705129 531526 264779 333040 670154 18290 167747 915409 798857 124120 164436 980204 439608 127709 184153 108478 703710 202167 875172 735064 378805 637810 306617 5 1 4 6 8 9 -1 2 4 6 -1