optimisation de cherchermin
authorDralagen <dralagen@dralagen.fr>
Thu, 5 Dec 2013 16:40:57 +0000 (17:40 +0100)
committerDralagen <dralagen@dralagen.fr>
Thu, 5 Dec 2013 16:58:43 +0000 (17:58 +0100)
Makefile
permutations.txt
src/ChercherMin.java
src/ClasseUnion.java
src/ClasseUnionCompress.java
src/Coll.java
src/Paire.java
src/Permutation.java
src/Prog.java

index c555462..8658b32 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -9,9 +9,12 @@ all: $(EXEC)
 intCommun: $(OBJ)
        mkdir -p bin
        $(CC) $(CFLAGS) $(SRC)
+       @echo "launcher : java -cp bin Prog"
 
+.PHONY: clean mrproper launch
 
-.PHONY: clean mrproper
+launch:
+       java -cp bin Prog
 
 clean:
        $(RM) bin/*.class
index 1276588..194cad8 100755 (executable)
@@ -1,9 +1,5 @@
-8 (6 2 3 5 4 7 1 8)
-2 (1 2)
-3 (3 2 1)
-4 (2 4 1 3)
-5 (3 5 2 4 1)
-6 (1 3 6 4 5 2)
-7 (4 5 6 2 1 3 7)
-8 (5 4 3 8 6 7 2 1)
-9 (5 8 1 3 2 4 9 7 6)
+5 (2 5 1 3 4)
+10 (2 10 3 4 6 9 7 8 5 1)
+100 (93 70 64 47 65 57 30 79 67 91 68 7 74 88 18 84 94 33 76 82 32 37 60 43 53 45 21 80 86 98 56 8 26 9 85 11 96 19 24 28 10 14 20 16 2 36 29 5 23 100 90 6 72 22 25 46 75 69 83 13 49 73 4 63 31 51 39 58 99 1 52 38 48 35 54 78 50 71 55 12 87 27 66 97 34 42 40 59 62 3 15 41 89 92 44 95 77 17 81 61)
+1000 (717 430 788 294 487 114 293 676 789 314 426 539 560 900 622 280 86 316 414 355 249 258 975 669 135 603 276 247 16 763 259 211 731 226 898 839 750 938 44 654 775 686 784 339 691 321 35 45 696 961 372 822 461 212 844 471 108 379 231 308 184 124 473 858 876 20 400 644 352 101 727 47 842 998 219 297 798 948 396 874 981 859 144 665 927 227 181 221 544 957 448 178 309 245 161 349 374 313 59 275 967 366 478 903 896 492 536 740 786 70 899 222 604 452 972 449 304 291 551 57 567 53 137 867 488 821 322 703 739 640 545 824 748 8 183 454 43 514 818 481 330 271 943 628 720 4 894 94 737 671 795 3 855 307 771 643 860 600 646 299 662 489 780 68 204 172 736 364 46 411 661 769 381 939 484 777 752 336 596 979 707 507 952 495 494 909 913 288 466 853 290 677 354 666 985 361 232 815 370 460 498 382 358 954 959 710 521 576 518 399 930 871 82 937 195 116 228 65 50 54 778 79 301 268 96 934 99 480 647 106 198 895 76 870 850 738 163 905 865 828 705 169 263 852 138 813 119 74 102 800 36 651 601 383 919 206 201 609 341 947 955 606 327 617 753 73 295 914 394 670 342 911 279 971 66 812 884 809 901 194 14 807 112 220 732 593 67 186 912 103 925 767 863 1000 782 548 664 401 591 93 167 872 456 719 586 237 565 69 37 794 502 388 367 986 706 607 17 419 618 472 762 85 749 635 885 223 497 368 80 829 408 207 588 136 160 776 462 425 176 360 121 704 328 229 552 393 897 170 614 300 594 113 346 687 353 814 504 877 270 602 659 553 319 733 781 566 441 840 527 889 474 390 915 801 286 673 587 405 542 493 620 819 992 861 757 58 836 199 555 260 802 610 983 152 433 133 91 760 146 636 585 491 34 482 682 558 650 892 799 571 933 615 269 838 577 906 217 951 418 284 547 835 337 744 89 190 335 243 581 631 434 893 109 756 935 141 537 638 272 910 111 797 283 668 87 320 345 7 557 15 242 421 721 129 236 479 516 597 989 806 648 282 499 718 218 230 725 285 171 632 883 932 303 841 528 779 695 621 182 917 177 445 235 965 735 944 166 264 422 9 332 940 117 501 953 611 902 833 988 142 155 625 873 292 931 515 168 165 262 891 711 147 837 483 590 407 324 626 257 326 200 386 525 424 469 444 459 728 340 519 105 225 78 810 928 716 645 714 255 658 132 238 402 63 447 19 467 792 179 958 630 363 918 936 761 465 29 582 281 652 847 697 311 862 41 941 415 357 436 639 432 649 534 192 329 879 273 500 64 175 88 274 629 115 486 745 62 369 751 765 463 605 318 140 42 942 395 984 214 125 692 26 333 95 550 856 578 475 993 154 157 700 523 584 699 966 139 127 529 423 376 978 787 187 924 973 83 634 512 963 693 825 417 672 663 49 683 233 562 995 713 61 98 678 522 843 990 694 413 878 538 715 325 389 30 808 2 926 23 251 100 888 248 306 496 531 149 831 33 642 397 520 145 148 412 887 56 868 655 344 734 759 197 164 991 428 21 208 595 773 742 490 568 22 362 287 907 962 437 563 5 77 241 39 790 31 162 350 916 60 130 875 754 524 772 126 25 834 458 375 347 338 191 180 570 746 343 660 968 517 980 608 55 261 921 583 404 741 442 848 827 278 377 882 234 724 256 923 690 371 997 317 774 960 443 196 380 698 864 143 11 637 252 513 156 680 250 546 173 150 679 240 420 384 97 18 75 158 890 572 612 982 298 949 392 266 817 996 51 239 90 331 12 580 277 675 747 589 826 246 453 804 509 866 569 427 409 10 974 406 684 123 535 722 633 564 385 289 554 849 820 729 378 701 755 964 854 470 254 104 540 510 455 709 929 189 712 999 574 950 310 530 224 956 312 543 6 653 592 845 994 681 431 215 987 416 351 28 213 766 210 946 559 599 84 758 120 323 770 32 71 118 830 188 598 657 296 485 533 468 624 202 438 627 40 373 267 216 886 783 359 945 356 656 526 796 579 477 532 685 159 823 908 315 265 122 348 508 450 688 203 869 27 391 440 476 805 13 131 970 674 81 881 403 708 505 209 457 110 541 48 977 451 851 726 880 92 305 573 151 920 128 623 365 134 446 793 38 803 244 791 832 613 464 969 785 334 153 768 410 976 549 253 52 816 689 435 904 616 185 857 619 429 72 503 439 387 723 174 730 24 561 846 743 107 506 193 764 1 556 205 811 702 511 302 922 667 641 398 575)
+10000 (4083 4030 572 1798 6321 1069 2730 9564 1973 4421 6239 4973 7984 1354 9932 7375 6261 7237 1657 7363 6268 5348 1027 2225 5660 3594 2936 7405 1510 7206 8659 6748 8867 5079 7799 1695 5706 752 6962 8297 166 4104 1252 1139 7430 8427 5249 3221 5885 1010 6564 7746 3623 8367 2944 8246 9010 2360 6361 377 8864 4858 122 3184 2955 8299 7355 3568 9937 2306 7755 5453 4505 66 329 9760 8496 3403 9217 5046 4293 9839 8699 8865 2849 8440 8100 1084 8979 6103 8347 7201 3529 2511 1766 4403 5817 7956 1019 4821 7171 8606 8060 5347 2551 8780 1391 7935 682 1379 5573 5624 3079 9638 2717 6948 6531 9071 1071 6553 5196 5487 8706 3857 9803 4211 8383 6380 3617 2697 8145 9307 555 7542 8879 851 1339 9778 7558 8715 8244 7269 7439 5497 1534 9239 8348 5824 9512 7242 7694 5566 4564 7964 3477 2975 8418 8872 449 6951 5050 1983 5081 4254 1209 6652 4524 9841 7967 9146 4439 5548 7604 700 8809 9479 6417 9162 2399 3752 6554 5055 9939 3762 7726 165 8438 8974 7975 658 3756 7070 6751 2313 1116 3110 861 9726 8199 8447 2506 9007 3719 9831 6943 7974 3584 4319 9881 6877 172 3739 7248 7587 9050 4788 2950 4451 2179 8066 6045 2339 1456 4514 9704 2314 4618 5695 2227 6669 1210 3465 574 1131 6894 5773 3968 8615 5059 281 8874 9485 5031 8324 8260 6160 115 5810 1986 1507 8422 821 7531 242 6242 474 1945 9057 1295 7662 5288 395 7932 9929 3392 8242 801 3775 7942 7121 5927 7741 3001 7581 1304 4948 4112 2167 1467 9079 1262 7041 79 7181 4590 8404 8309 2715 957 2591 6915 961 8614 7570 310 2075 3246 3839 2248 1731 5239 1462 3247 7953 4722 5955 9158 5917 7042 834 3641 1150 6280 2711 446 5836 5743 5613 9409 3891 3373 7122 7112 9393 2156 2612 8572 7845 4425 4016 301 4259 8032 9964 4759 9928 2420 4115 7349 5068 4155 3435 1616 1344 8793 7743 4771 5179 2835 5504 5638 3492 8101 3426 7087 9150 569 2335 4047 6148 4316 5658 4966 3003 5320 6974 7696 1356 1452 5650 4241 2328 3328 8724 9545 6903 2058 3933 3181 690 7148 5345 802 7524 1487 7163 3434 8233 8302 1404 1834 4028 1110 9035 120 178 7254 2353 4098 7590 398 6325 2599 9722 92 9984 2914 5137 8822 3431 1964 9707 2700 5483 7937 2513 3346 7407 89 3831 3049 9345 895 6789 9969 4126 5581 6519 2329 8231 5545 1291 3650 982 1278 5148 3915 3941 4869 4286 1308 1489 6579 306 9361 6141 3178 8341 9933 8982 2802 6207 2588 3850 6684 9767 4091 2911 5531 3806 7510 6851 4522 6764 8988 816 4792 139 2026 5385 1484 5839 2652 6907 8452 9860 7901 2041 1194 6254 7594 9023 3618 2579 5750 5662 492 7450 7373 8170 2830 1048 3787 9145 8590 7280 8464 8515 3449 5693 4415 9876 922 1007 4664 1245 2956 4207 3076 3129 3543 9033 7494 274 9547 3104 1868 9195 8577 747 3734 414 5344 2246 7052 1912 1442 8204 9132 9603 4616 3716 5292 701 9129 2798 9037 6377 6245 7368 3592 1630 2616 4065 6195 9353 5532 5017 9527 2886 8163 848 2164 5009 5526 6739 8997 4976 7737 1846 4718 9751 2495 6054 2628 1555 3766 2870 179 8976 1590 6497 8236 4558 1623 9371 7208 7576 2207 1332 3130 3834 669 6369 9429 9568 9558 1832 3702 9219 8025 4987 4974 8884 6781 4243 226 588 4646 9530 8508 6746 2742 7366 9791 3264 1274 3261 7692 296 3519 3310 6672 388 1514 1989 1940 2708 1147 4872 1998 3690 1478 4688 2831 3242 3748 6670 6014 4253 6710 2035 6658 1267 3902 1396 7391 5190 8719 3439 7467 7790 2290 5151 5013 8448 6891 8807 7655 6612 6232 6882 7086 3988 6270 8557 7722 3819 1949 6629 8986 143 4647 1917 3005 8966 4844 9935 3888 3078 873 8012 8036 2743 7123 117 1853 5672 3409 9197 7854 7106 3293 7334 2706 1075 1411 4866 9382 5057 597 409 1599 8929 5490 2055 6387 5152 5363 4009 6272 7780 1390 6608 8102 4812 9048 5805 3353 8037 1988 4377 5916 8493 9816 8905 466 189 9827 4193 2132 787 6719 6163 3332 2629 3055 4967 4097 8075 4289 7008 1191 5132 1887 451 9377 2419 407 8378 5350 6797 4004 5124 779 4291 7649 1491 7304 6020 5160 8463 7174 3458 486 6413 2427 3896 8220 8294 8783 3175 2585 9068 1563 3722 1857 7625 7190 1649 9753 2791 2442 4147 9046 6085 127 2219 186 269 459 829 995 1371 4021 2757 1307 4951 7969 647 9366 4826 7769 9279 4499 5800 4621 8792 5762 9338 1828 8047 2737 3540 4799 2127 5827 5021 8618 9148 5491 4530 2332 5259 736 8751 4805 2477 9796 6728 430 7411 3042 8398 433 4743 2901 8431 4049 3117 6581 9298 1902 3327 9379 9292 9549 5760 7099 7425 6829 5149 6914 5394 2686 4007 8035 7536 4123 6080 1159 1715 2542 5485 3518 733 9404 7928 7734 2537 4432 8043 1394 1206 7136 3957 5777 7260 2459 2034 8955 4195 4013 2441 3249 5062 7837 3648 7161 718 7040 232 2749 6100 3725 3025 2615 5914 6568 4740 9438 7614 9411 6130 8863 359 6468 4519 7095 6844 2430 4186 7999 3311 5100 9798 1774 4335 3441 4730 2779 3189 2300 3971 5482 4879 3986 4569 8594 9507 2208 145 5420 7943 7383 7283 3093 4264 9773 4787 4873 986 4637 3390 7923 1282 6875 4652 238 1140 9114 5617 1533 1477 4223 8215 1483 1082 6425 2471 1706 9598 4067 6058 1792 7628 138 4071 204 2596 7674 5611 9755 985 497 2349 4891 6343 9680 3786 8548 1352 6248 8908 4918 7863 6634 3103 6440 7038 7097 6854 8451 2935 9844 2670 8104 9995 5856 7178 6240 2753 5285 9607 2965 5393 6008 2604 5585 3643 2454 872 5319 7635 3462 1778 1812 2462 2163 7924 763 9000 333 6964 9734 8766 9954 7389 8178 5429 4074 4438 6295 5546 2036 839 7151 1968 1739 3461 2324 5217 6706 4754 2174 196 2906 8837 906 8056 638 7339 6524 6515 3659 4904 5913 8030 6194 1263 3691 1595 9209 5454 6551 9425 4471 8019 5044 2485 3664 6990 2281 9241 2999 4884 4381 2054 431 4462 9892 7449 2203 1965 6348 9730 4350 7259 7877 7962 4653 8995 4219 5407 7176 9428 8192 6783 3094 9870 6267 7169 7836 1681 7735 9504 7144 8151 5313 3317 9245 7652 1382 5789 5744 4165 1100 10000 8563 9930 6530 6145 6400 965 2490 1950 4413 410 5359 2171 5656 6399 2503 4661 2501 3715 4503 9789 4167 5232 4648 4657 6833 8716 5493 1279 1863 1527 4287 1538 9202 4039 513 9385 2317 8258 612 9743 6832 4808 1675 8078 4913 72 300 7707 3119 5896 2813 2067 3268 2309 6971 9321 8267 5987 830 308 4420 5048 61 1202 1038 2363 677 1768 4724 558 2725 1085 5687 5787 8361 9903 8287 4485 999 7810 6595 819 4842 715 6754 8973 5382 1752 7695 7940 6149 9848 8063 3349 6299 5582 5901 975 5264 5921 7088 5189 7039 2426 6780 5634 5550 845 850 8620 1526 418 8849 3345 1994 6220 1233 6913 5150 7189 440 3259 8573 2649 4342 2774 1218 2303 3629 1671 4199 9710 7608 4639 5785 4816 3482 5973 6088 6476 7850 5590 4347 3729 6356 2369 4666 9331 2553 8641 3517 2878 5852 4615 4893 7272 3397 5106 9588 6401 2113 95 5717 9126 7872 2709 9246 7244 3960 8540 8556 4353 4148 8057 6493 9452 6449 6458 211 2066 4166 9164 5869 9980 5339 2893 54 1283 4180 6744 5669 5301 7660 6976 5422 3297 7718 2261 5509 1785 9600 2674 3536 6241 777 112 1266 639 8585 5063 9222 8340 2124 1772 526 116 1053 188 7022 2891 8133 4501 8269 9085 1522 2545 8889 5329 5282 3350 1413 3186 3753 6893 5718 7787 2096 6585 6201 3826 5795 422 1063 7390 3730 7677 7324 5115 4464 8314 6238 4971 6668 6968 8801 6209 1180 9975 9650 8140 8116 9025 9354 3798 6841 2738 1215 6353 4835 7094 4283 5875 3223 9963 470 1015 8695 3083 5451 3928 2455 5630 8141 8820 14 4620 4325 7027 4676 2102 265 7310 4649 1813 7364 424 3232 1642 9902 7978 3997 9919 4755 2076 4984 456 6482 4317 103 293 4136 5808 3550 7485 374 6125 1250 4585 3484 7702 875 7724 3785 4513 9602 9790 3949 4643 8434 5364 7069 9562 3885 58 1435 5434 1068 5657 2032 1992 5985 5435 849 3943 4544 7394 7261 9962 8023 7869 5710 7397 1343 5488 1916 9003 1757 7319 8169 6311 4062 9359 8627 5560 1800 9554 887 976 4633 3749 3389 2953 4436 3306 1383 8103 7404 198 2356 7704 9097 2484 5512 7947 9996 9283 6501 7130 3262 8892 7413 5464 8876 2924 1996 7309 9370 8040 6805 3100 3010 1743 71 1351 1132 3002 8401 2942 898 815 2445 9815 155 9416 9768 1569 6091 3789 5823 3714 9891 8106 4820 3195 871 4231 4895 9563 1064 8511 7920 1170 8735 3534 1143 7623 6352 3964 721 1137 8639 8990 896 2680 8993 3637 9716 1094 9357 9593 5627 441 8415 1773 4020 9432 2161 6434 5284 3813 4721 2233 1330 9518 4862 512 7200 5029 7441 3706 9997 1258 1669 2007 5862 3004 8588 2846 3416 7 5433 9044 1141 59 2082 5643 7193 7156 2543 24 5792 5940 6692 1644 2998 7292 4856 5644 1905 5473 3996 7554 5049 7337 602 3068 1166 9047 4684 9658 6174 2573 9519 9973 6807 4194 6626 7561 7775 2158 6583 9502 5943 1885 8797 6880 3642 412 9620 8122 185 2541 9252 2478 7145 9596 7476 4031 7687 4173 467 9694 1437 3352 8787 8798 8323 7024 8748 1760 9559 3758 1984 479 8007 6197 6688 4680 4935 3567 3066 3967 5142 2538 857 5621 5447 6306 8206 7632 5480 7059 2845 1991 6461 8977 1573 5295 714 8875 7406 6523 9124 7646 215 559 2735 4758 9857 7613 9458 2435 5012 7246 7096 5212 3340 9952 1221 3437 7563 9577 2267 8374 7560 2785 2741 2991 9544 2927 3918 3948 8017 4141 4735 2232 4370 6548 9735 2449 6358 7342 4745 4550 4184 4349 7557 6172 2323 7621 6752 6526 1756 1990 6204 2584 9662 2733 5729 969 5067 2613 5166 8513 6326 1575 5924 1334 6857 298 1645 7728 1830 9985 8420 3999 2824 4529 1790 1337 7093 8957 8810 6229 4205 6096 1515 3385 8389 3654 2489 4848 8351 5606 2226 4234 3962 6793 3113 4336 773 4266 1251 8274 9304 5066 3107 2444 5417 5136 6370 6246 4055 8335 25 7733 1133 4827 9336 8885 9067 7477 8098 5538 8778 594 4398 2675 7267 5340 421 8871 9784 776 705 856 2879 1128 1050 3559 4708 5071 9987 3357 2320 7461 1927 7090 2877 4341 8945 6910 1208 5045 7045 6711 8385 55 9105 6631 169 6177 3248 6597 3600 1797 2881 2088 2429 9312 6024 9199 2470 7291 8791 225 4400 1930 1749 7432 4407 8474 4269 9456 2010 7527 8927 1398 3884 3692 5798 390 2231 9826 9746 5607 6453 9063 2318 3278 4798 22 9565 2533 9302 4088 7434 7933 4487 4631 3667 7525 2808 1958 2259 3895 5950 7887 3071 2943 3868 1839 6170 4309 6445 1306 9036 8327 146 1033 7747 2594 7828 3161 5659 9407 8826 7797 3608 1708 2285 7216 515 3265 1558 5086 4395 1422 1444 5494 9155 6757 9384 8985 3652 7586 7179 9093 8813 9656 6958 5811 8013 9248 7063 5087 8346 9877 4406 2578 4567 9297 2570 5727 5986 4753 7798 9938 2855 67 3574 4087 7994 9495 50 5649 2186 2519 5215 7271 3934 835 9916 5719 3922 9961 3436 1755 732 3281 1363 6828 3757 9674 6137 6281 8944 7851 4911 1077 9175 5568 9347 1668 7505 2 6804 2967 8967 6598 7642 2017 5918 6339 5604 8847 4591 6095 6742 8328 6978 1578 6092 7610 8393 8835 2567 7727 3059 5519 6460 6 3377 6778 9887 5818 3367 3006 538 1613 553 7454 3733 6013 392 1198 9688 3784 8571 9309 6645 2852 5782 5728 7736 363 4910 1410 8239 194 2307 5835 1836 5673 674 4962 2293 1471 7115 8074 8729 5664 4070 4975 1611 9106 2249 7183 799 888 7645 7475 5252 9882 9462 4903 9944 4244 3908 2871 8899 3906 1703 4389 9075 5472 228 4804 1640 4990 2475 6205 9169 4278 6329 4064 6076 5317 7760 3438 9170 914 1769 6060 8691 3498 5890 6363 1632 8319 7927 4110 814 4610 5501 968 605 2019 2582 4552 3098 7448 2154 1045 6144 3398 4131 4811 7077 5722 7067 6066 1741 7279 8200 7676 7282 1545 3157 9792 2783 3526 877 5391 9617 2800 1893 2266 6362 187 4963 6952 8550 5116 4551 2287 5589 9489 8296 3520 1910 2025 4240 1540 6439 3388 2676 833 5731 2523 4916 737 259 5887 9108 9372 6815 729 1305 9381 1018 5261 9807 7387 3772 1550 7498 46 9476 3687 96 4042 8895 6697 5514 8928 7006 858 5263 5291 2984 4533 282 5107 5783 4090 7013 1405 5147 140 4045 9572 8339 2333 6620 2136 581 5595 4075 9982 7591 6537 5683 3744 8081 6862 4376 1214 3193 2111 1248 124 8388 4228 389 3990 3899 1175 6541 3863 1012 6997 8805 8789 8251 8211 4783 4107 7972 4467 15 9532 295 7791 928 3192 3620 2682 1380 3420 604 6489 3047 4236 454 4129 4677 7691 5481 6217 2354 1386 5423 7422 9408 2640 822 8830 4005 6459 4738 1412 4881 3843 641 5028 1565 864 3013 5555 9972 4409 3581 8465 7255 8714 3487 134 10 620 56 1431 3391 6383 3257 3644 3056 5099 6021 6475 6487 8127 8730 4448 3970 4274 4815 6136 4793 908 8205 5125 5655 7663 8592 1847 3675 6341 6908 746 4707 5039 49 504 5398 9491 1377 4970 8555 782 3303 2751 6839 820 3697 4776 7855 8721 2780 6349 6398 9136 8595 9419 1615 4307 6755 8279 8806 9728 5370 500 2724 2368 6388 8016 5221 7207 7680 4185 6283 3873 8660 7640 7228 6836 5988 7436 1160 6941 2626 3445 9343 6135 3952 8268 5191 40 4364 7082 3669 8998 5489 7909 7533 9178 6481 3165 9236 7100 4394 3191 9459 4773 7341 4210 8658 781 1461 3809 2726 2348 3364 5138 4999 7164 2169 5791 6641 1707 7629 5195 8350 2184 378 5397 852 7593 3036 1866 1474 1294 4692 9201 5871 5390 855 347 5919 3842 6467 8622 1213 1385 2262 8934 1134 4374 3183 921 9285 2106 3579 6720 7973 7447 101 3657 1089 7611 2701 9717 7819 4685 4594 2061 8509 8433 8449 4036 9330 9689 6950 9286 2918 9539 3188 9720 2777 2817 5610 7709 6571 4271 6426 1127 5868 9960 5707 7388 4006 3417 4750 6525 8338 3226 4284 6477 3173 6292 8146 6920 8570 7685 6123 7459 6759 9783 104 6323 3507 3703 5833 5200 6050 4902 8487 6749 485 946 6606 2172 3660 5874 8501 7546 6161 4563 7215 5517 7501 1362 6954 7540 8525 9243 6198 6260 1920 1326 4523 2586 9782 5275 5499 8446 6381 8028 1924 5088 2039 4073 123 1918 832 3783 1937 3889 800 5623 9001 9418 2376 5813 7708 7697 7534 4072 2951 7502 9091 542 6188 8093 6359 1729 1021 6897 5759 6820 2326 5296 5569 1486 4565 405 6647 4548 7322 2550 7902 6094 940 711 8014 5276 6682 3532 7620 5580 9698 6120 6732 8344 1368 6071 5535 712 8284 9434 5387 5460 6872 5609 348 9022 912 3162 8289 939 2093 3742 5300 432 3381 6931 7222 1962 8470 4679 4613 3115 9970 8275 401 7298 3503 12 3279 3636 4161 3168 7016 3527 943 2833 2366 7945 1232 9482 8755 1393 9514 341 1109 8195 3097 7530 2768 6319 4324 8326 3017 5536 3978 5898 7795 3485 2033 2848 8704 884 5156 6615 3202 1899 1345 5375 4275 8203 5830 7818 1502 3993 3023 9441 8652 6871 8519 6186 5161 7331 3127 19 5416 3224 1105 5895 3704 8357 9534 9875 7633 1969 687 4371 5246 686 2178 2645 3874 1955 1938 5651 3573 8373 4630 8532 8896 8485 3696 8916 6251 4612 23 7960 4607 4404 1759 36 6422 2012 4824 6430 4705 8914 2107 6578 1200 4280 7756 321 1603 5867 8072 4296 8549 9993 6698 1551 2888 5520 417 5876 6105 517 1241 4481 6470 8736 2632 9989 5506 4080 4554 7879 3040 6282 4731 9092 9258 4813 4265 2217 9986 9709 5685 8919 4150 4079 6340 9861 7152 8962 2381 3393 516 617 8975 7048 6218 4843 445 2100 1389 1865 384 6212 6287 7023 9890 8888 7882 3815 7265 7852 3841 3494 8684 6146 402 7651 971 3958 766 4496 7959 722 3720 7486 1738 8148 4025 5082 9346 1978 6101 3907 75 453 1661 5054 5332 6520 817 8853 1726 2234 2190 6182 6667 4546 5637 9327 6866 8419 9830 9896 4995 1974 1448 5877 3523 6715 8428 9207 9270 6393 2330 2678 544 8723 8784 5277 5427 1622 7785 3981 8825 2120 8466 5971 8821 9571 4669 7989 6048 6456 9977 7757 656 4116 5466 2018 5597 6888 6700 9643 4650 6143 7028 649 3289 2952 8222 3921 5170 5026 983 4386 8191 8841 7445 5101 7421 9299 609 4461 3904 3528 4281 7293 4174 3556 2060 4463 7395 6733 6960 652 738 4489 6665 3211 941 1425 3586 676 663 8185 1788 5525 8731 8607 7823 994 1793 8619 3075 9665 2160 6221 5022 7081 173 7348 8085 100 4450 7134 5980 434 1285 7905 7076 841 2938 7930 8969 1725 2114 970 203 6660 4673 1464 4442 8628 7017 366 5819 4012 4988 1324 9909 1895 9579 3569 8153 3852 6036 1178 9764 164 212 5953 9494 7313 7481 530 6561 1684 5230 6587 8882 6034 4977 8744 4502 2321 2273 4510 8883 2895 5647 9510 2994 2627 9794 2712 7833 4015 6981 9264 1811 6848 1020 8416 9852 8665 6509 3679 9697 7715 1235 9699 3137 4836 2443 6681 7991 2176 6073 2213 3160 8158 2810 4459 828 3900 4081 5771 4645 4019 5691 4853 8234 8951 3583 2561 5974 2762 7805 3901 4969 8949 7243 5194 4222 6455 6831 3219 1665 1977 1384 8546 2807 4429 8069 783 8611 8436 1521 8114 8992 2595 1081 2312 5379 1948 1416 1619 4757 2940 745 8862 4575 208 7556 6486 3358 1699 7626 3925 175 5831 4597 7914 9731 6344 5976 974 2898 8257 2253 836 8096 3239 5910 8838 335 6930 2440 5908 9601 3781 590 4949 30 8517 7129 249 7102 3463 8090 9799 7154 3131 9295 4178 9660 4301 4338 1626 9609 5680 4017 5844 9426 1744 5097 3712 8502 7338 2864 5688 3037 1564 4860 7784 5203 7822 4384 3773 2996 9077 4985 4125 193 2748 9250 9496 2667 631 4423 5882 2863 7670 7842 810 6317 6975 9471 3282 2549 4882 1547 1093 268 9642 8503 910 920 8298 9668 6297 9629 7457 9863 471 2229 6064 8860 4469 7458 2247 7764 8693 4782 8238 1904 9904 1102 1892 6738 9708 4390 8154 1224 4206 8003 7946 5354 7146 5294 4360 7278 2729 993 8160 984 5486 9732 5528 3500 6113 8662 3737 1698 629 240 4922 5421 8280 1029 8734 1423 6159 205 7356 77 9820 4203 8000 6478 9334 2930 4605 1647 3128 9917 223 4687 5326 9142 5642 726 2977 522 8256 419 3091 2820 5832 7108 16 614 5726 8305 7318 8764 1070 9223 200 1316 1601 5023 5377 2074 6320 9311 7929 6192 2922 4540 1433 6972 5368 3614 6824 7412 2406 991 3402 2974 4051 2986 3598 1418 4053 3760 8621 6796 2336 7409 960 6234 7683 29 1397 3871 6005 3086 328 716 3315 241 7110 7004 1179 3190 2773 3102 5449 271 3459 3893 8984 2362 9477 5879 3378 5654 8229 3386 7579 8702 7915 4634 7600 1310 8844 7898 8254 6918 5593 340 3112 6171 9712 3300 1518 509 1888 3493 6900 498 4391 5730 2396 7249 5463 878 496 2778 7367 806 3089 9102 8021 7602 6574 31 5563 7950 8004 1879 4651 8956 8756 4412 1886 2979 8208 9420 651 5674 9733 7582 8746 6273 825 8816 4706 5801 367 670 9196 5790 2600 4434 385 8745 2716 7816 4940 3203 8315 4410 97 761 8281 584 8767 2500 9529 7699 9924 6183 2636 9255 1780 8924 167 685 9936 1763 6646 4018 7955 1072 6126 7487 9869 4795 6769 7768 2605 627 9847 3015 4217 2496 7398 2191 1841 45 5592 9599 2094 4145 2531 5652 6375 7114 7285 3179 3213 7165 4663 5608 1289 4139 6290 7793 4343 8582 3814 9524 8247 5888 8855 611 7321 5056 62 8779 2053 7867 5579 1829 1182 9014 6664 6868 882 8044 1784 5969 2976 2431 9867 8045 502 6394 2904 2250 8720 6395 2937 7631 7335 4002 2961 3288 3330 5500 740 2483 9615 7890 5931 4715 9121 7442 9454 9551 9756 2453 6870 6801 7541 5529 7650 3613 4385 8212 7316 9628 3582 8459 6899 7340 2623 5748 8521 8092 7033 1840 6087 1621 8644 3044 1814 3547 8372 4719 915 9555 8687 7745 8667 1825 3777 8423 9247 370 8499 7451 2398 2340 4789 5095 42 7891 7170 2620 2819 2180 2410 1328 9931 8190 6766 2704 9872 3432 4054 2685 1926 6745 9994 9590 7252 3551 1835 9821 5006 3640 2528 4599 8318 4263 3101 1087 4983 3379 6114 5297 3320 6099 6492 9472 4587 5521 9809 3421 5556 1277 6038 4000 2601 7573 3468 5309 3530 39 9376 692 8417 7840 1694 2108 1733 9360 2565 2405 1490 1322 3444 3864 436 7057 4224 6988 8009 1651 727 41 6659 7120 6549 5694 899 8167 4328 8184 546 9846 8394 5735 8119 7493 3356 6397 7963 3750 699 1929 695 114 7104 6616 7133 2256 7500 2117 3139 5015 8471 7992 5139 3521 988 5408 5909 9691 7706 8726 7523 9874 6508 2242 1447 1453 1195 7196 5697 4100 2386 8538 4256 5008 3032 493 1426 8666 7074 8980 1302 8741 3148 2143 8320 3088 6635 7875 9032 1145 8673 8996 5653 3571 5961 1560 8759 9678 5886 4392 2030 7084 9779 6814 1655 3754 9233 1765 5977 3443 997 4190 2926 8241 2092 2590 2197 7113 9541 334 2718 6922 4655 3063 1427 3504 6762 990 6131 171 160 6158 4367 6312 4978 7997 3973 1312 8223 934 1246 780 7821 3490 1939 7034 5185 3622 2000 2842 5227 3058 545 6924 9332 1900 9082 6335 5572 7464 9948 9027 6391 6703 2765 591 1024 1718 1870 1596 7511 8670 4247 8304 9289 435 2425 4625 275 8823 2152 6011 2415 5357 5990 4169 6225 5321 8300 743 1122 6396 3525 251 958 5870 38 5964 2263 2452 7881 1585 3333 7693 6119 7807 2905 2534 7021 5614 3920 5891 8786 7725 8881 233 7297 3158 9979 6044 2205 180 5629 4784 7861 1966 527 6630 126 8583 2666 2237 7504 8376 5457 6818 4716 2988 3412 6331 9702 7184 2539 1301 7054 5461 5954 933 4839 8866 992 4458 9713 9769 2805 7815 7549 63 3254 3200 9569 5245 2493 9402 4255 589 6858 3764 5140 6604 8216 1710 3073 9386 3322 8727 7849 6642 3050 7841 4411 4318 128 947 4220 1700 491 8983 7307 4114 3440 9955 9173 9276 8689 5078 7311 7584 7555 6231 9654 664 6633 5035 3910 681 5228 8407 5677 3821 8435 5158 5060 5764 1667 9646 8543 3280 7210 6414 8439 2098 1858 4261 9221 8359 6593 6768 550 508 4814 8159 2002 1443 4751 2189 1953 1871 6837 798 4727 2767 6987 3522 9348 6350 7327 7603 2029 4497 4675 926 8333 9261 8112 3695 4797 4050 6959 2825 1366 3590 7011 4149 5721 3331 5737 9028 404 3338 1212 8293 7552 7667 9687 5169 6923 68 827 2754 8781 5605 5316 8728 3912 5164 2423 7801 5024 3225 7284 2073 9251 8473 5306 7286 4980 7020 4189 7720 1513 8273 9690 2792 2648 4314 7941 9540 1571 109 4578 1169 2786 7128 7528 1517 9814 1663 9879 2665 236 9016 9090 3022 7979 7908 9054 945 3685 7362 5859 698 9696 1297 8175 8048 4188 8494 3991 9133 1204 7731 8971 3553 1692 2244 6291 1810 6584 1875 6181 4689 9005 9081 4303 2238 1921 2634 43 678 7314 8531 4960 5746 4875 2540 9410 1944 3836 6555 2466 6540 7329 5905 6909 3045 3924 6677 585 3531 4672 5085 2858 7813 8972 4632 6618 2325 9950 8186 26 227 3319 6800 5577 4744 2775 4120 5998 2417 8738 3602 7380 277 9570 2254 1852 2056 6043 1269 2389 8815 9580 3591 8880 302 3740 600 1805 8166 6499 9583 5444 2752 1690 6657 6819 7444 1683 5474 5310 9644 1911 1485 790 2563 6640 9813 1381 1323 4474 7609 5926 4957 323 4818 8055 2365 9659 3433 8526 8176 9965 9461 6532 5591 4791 2903 7400 2125 9824 9291 7418 8382 580 3944 5431 3069 1340 9448 3474 8923 4156 199 9435 7788 9253 846 8718 9492 8584 3898 8917 4870 4953 4479 6835 91 2077 8283 8760 1272 566 9692 5231 4373 4044 6000 1099 9958 5578 4674 9401 9095 8460 1016 7251 7423 2305 909 1781 8537 8342 2206 283 3689 2939 6107 6588 6334 1046 3446 4248 6093 3632 5851 2983 9403 8188 5802 8068 9080 5884 735 70 3797 3376 4272 8717 5957 567 5753 8488 1787 2138 264 7630 4874 6392 2301 4678 9171 4418 3272 2736 2481 1880 626 1196 7159 9538 2614 4138 1789 8316 2989 1284 9647 8249 6412 1446 8117 7250 1207 2112 8310 6885 9581 1365 1941 5994 4441 8950 4598 3241 6599 1243 854 1376 6002 9455 5596 6336 5788 7926 919 8547 1954 7916 6817 234 5618 8514 3230 6223 8713 7158 5399 6086 5123 9172 3903 244 1824 1823 2103 5712 8018 7235 6474 4996 9469 3855 3705 4890 5968 7226 9442 8472 2311 4488 7585 4221 9856 5989 7911 5603 4942 5108 1017 1826 20 8052 2610 4959 4691 6117 9060 2770 886 8179 842 4863 2240 3796 5092 9622 6168 9672 9453 5619 8089 195 6255 3505 3250 2382 8070 9907 4368 2126 5933 1598 1672 8958 4626 8282 8836 4396 7347 2384 7101 2856 8697 3847 625 7886 7012 7213 1896 7543 3501 9991 7455 7379 7155 6767 280 7748 7988 9287 7061 2625 8369 9024 7396 548 1643 1299 4614 6327 3822 8337 7453 7744 8952 9220 9383 838 1257 3255 221 4917 7657 8861 7001 8808 2690 2479 561 4172 7750 3170 7605 3980 5374 1227 4698 6042 2090 5661 1658 7299 5981 666 3603 2668 1935 2684 3824 8617 528 482 2327 749 7109 1165 7428 3244 6906 7107 529 3661 8915 3792 6921 5758 6980 260 2393 290 587 490 6998 349 5779 4992 9188 8645 8970 3210 8201 5714 5436 3508 324 5834 3514 5495 680 7470 8544 2361 4056 1914 3124 237 7371 6025 8380 9193 7480 9742 9464 6575 4946 2527 2474 5923 4362 3610 8008 601 253 4142 5982 2488 7766 3187 2395 3053 6982 8250 904 1641 8581 5542 149 5930 1142 2694 2228 1975 9303 4427 2370 4654 6364 3708 4277 7753 1253 5507 3108 4449 4986 2638 5267 6521 980 7431 8624 6761 190 5405 17 9776 2414 9898 2987 279 3731 3630 6690 3033 7277 3292 4711 4329 3012 1247 5797 8131 2744 3152 94 3845 4235 262 8482 3335 108 8854 8076 9536 2486 1579 9608 5690 1309 8105 472 8545 1633 2960 8321 6937 7529 2239 3427 6236 3456 8492 5462 9901 6269 8362 2971 7919 6560 4855 523 7075 9446 2929 5018 7539 4498 5640 3923 7826 5096 8959 7648 7537 5904 1597 2890 6154 5767 5372 1932 7896 8782 6068 4702 2504 8384 8698 7326 8467 3154 6784 4456 6407 2781 1629 5234 4623 1693 3593 2769 9693 4952 5213 8303 8077 5001 7682 5257 162 3382 9271 7492 8329 764 6298 8354 2932 9793 7305 9412 5235 4356 7883 5358 1124 4014 1006 2338 1783 3840 3746 5705 4140 3544 6850 86 6939 610 9466 1148 7295 7783 1044 2894 3009 8754 256 9981 9087 460 2494 1934 7617 1115 5738 784 403 6431 1026 4915 1414 866 3699 1035 6304 1420 255 9968 844 6490 2993 9679 5118 5214 628 6451 7433 2175 1296 3936 759 7263 9836 9096 5803 2972 4354 1549 2344 5899 1588 224 9465 8291 5043 7907 5666 693 2651 927 1172 2995 7966 5146 4810 8002 3227 7671 3655 6354 6517 632 3214 552 2458 2827 8 9685 5820 7125 3343 3077 5861 2869 2641 327 6654 3913 8770 7730 3298 7219 8015 9575 8334 8575 3539 4470 1537 6565 9473 6485 503 1287 2968 5080 1908 7868 9315 4026 1981 6535 2165 7689 2925 5153 5752 3156 9635 2583 28 2923 8623 2515 201 2851 1705 5256 9631 4430 5247 1520 6522 9625 4378 2618 121 3351 8491 3709 1459 6729 420 1000 901 7565 8108 4122 2571 4933 4682 6300 9714 4491 2980 2260 3838 9211 7595 1455 3486 1203 1987 6372 7350 1226 9316 7774 4358 9992 9200 648 8457 1933 6834 5328 3467 1721 6429 4584 7147 9013 4541 2297 944 1275 9006 9351 9781 1450 8655 5250 2433 6528 6859 7317 9486 2015 3475 448 9711 9012 4938 4923 6984 7897 2695 9038 2964 5515 9645 3212 3916 8083 442 2274 537 1891 9804 3646 6150 5130 2884 4560 1627 8024 380 5240 3878 5620 7820 4728 2866 292 3856 4417 796 6957 4452 2187 8682 3883 2530 8197 9300 5508 755 2544 6689 3914 5732 6104 894 9634 5574 1625 4570 8831 4786 8817 1685 7124 4399 2391 1801 8301 5322 7690 8355 2696 8358 8832 6213 3372 2607 2023 1254 9949 7116 2947 8107 6373 4232 7089 9745 1219 2147 9837 9099 2547 5804 7567 6653 1736 2532 8217 4683 372 6139 2011 5467 1271 7503 7166 1429 5763 1268 6632 2720 7742 1025 744 6162 9443 7723 4069 2230 3626 9144 7167 8484 2377 7471 7135 8643 6379 7904 9829 7773 5478 7132 7336 8123 3276 583 9240 6226 9439 6210 8500 9673 2252 2771 2480 8752 966 7408 9070 6765 4582 7229 5641 3370 1696 795 1415 5692 2966 9378 2837 3570 9257 1791 7424 876 3624 423 1104 6628 3776 7401 3472 5204 959 2722 6722 2688 2194 5475 4937 9591 7659 3235 1687 1154 2182 2654 6028 8353 364 5837 771 1375 6718 4105 9808 5175 5784 1098 4909 7515 6473 4603 6940 9868 5058 653 6883 5188 8512 9463 9278 8631 2473 5679 3132 2251 8654 5102 3404 1982 2044 7535 1481 263 911 8411 9853 5075 2497 2745 6794 4838 4359 5946 4752 869 9396 9123 5159 4011 5911 6046 202 4580 4761 2635 2841 4961 9058 6033 642 1536 2149 2508 6286 1358 4076 2110 5723 4592 2104 582 2739 9883 2270 9943 619 9074 5173 5089 6822 2062 6067 1901 4290 6175 6074 7957 9522 9526 4545 4781 1167 809 9655 720 2609 361 9889 1506 3743 8567 5540 3558 3334 3149 34 1401 2740 353 2763 1073 3628 9417 7217 4825 2789 7871 2631 5576 6263 4465 9156 5418 3313 3563 5941 206 9953 83 6450 3451 6332 4532 7157 794 3387 1346 2872 5030 8542 903 8478 5492 2295 7885 3562 158 8088 5963 4027 2465 3966 1956 6929 32 6675 3495 1856 8252 3853 1249 7532 8603 1609 4008 8430 3171 4151 3549 2832 8910 9775 6572 8920 6986 7574 6753 2985 5242 9927 1113 2814 4865 8152 4387 2183 9661 1260 7050 1493 540 8906 7894 4830 6861 7548 1441 3316 9186 4876 5544 1120 8651 805 9854 6586 3597 3197 8129 9467 8255 5967 8286 5799 7443 8497 8948 5551 9125 1479 9517 7290 5219 9263 9505 343 3236 5937 4622 5355 3016 6663 8262 141 1602 4119 1300 931 9475 3014 1238 4443 7517 4896 7968 2928 3735 5599 8757 9667 3585 4518 7239 4369 4382 2299 6504 4348 113 9585 3140 4919 481 5198 1101 168 3169 7281 2070 635 5815 1593 6271 6328 6896 6365 5469 9350 4493 2982 2450 3595 6179 3533 7240 6792 688 2662 9225 8332 7607 4187 2840 4901 2286 5949 1114 8965 1664 4851 8964 1228 5781 4920 3975 9747 8424 2084 7489 8285 6996 3663 8237 9234 5724 4506 8207 6865 7473 8360 9552 6503 4849 9611 932 87 4713 524 1130 4531 5945 1737 1313 2302 1653 3538 9161 6454 6638 9832 5154 8750 57 5047 8409 5038 5010 2581 7876 1468 668 3090 4242 4934 3778 560 5281 4543 4366 7427 6264 8162 7572 3299 2854 1843 1480 2409 7378 7119 8214 6712 634 8408 3252 534 6097 3870 3811 4748 9657 9249 719 1877 7478 6603 9484 2038 8049 3969 9537 7180 6284 4154 8136 1080 8381 6118 2880 7019 6795 5120 5703 7202 6816 1129 5025 2505 4536 9294 3266 2637 427 1002 7300 6199 8939 8762 897 1528 1074 770 184 3374 5279 9508 900 7562 6378 1353 9557 913 7416 7996 2535 1758 3631 1570 9597 9424 8848 613 6676 804 9718 1190 9040 245 5201 9422 6019 6055 9618 4982 5906 8033 2672 1176 1592 1476 905 7330 9915 6153 488 9224 8680 4538 9925 1054 3450 6277 4181 5849 6694 2619 8413 8840 4214 4121 6791 150 7717 3537 6324 9314 7143 252 5311 7160 3546 5455 5843 5126 4029 5845 3726 8064 461 7079 7767 8027 9109 5477 3892 5182 6355 5716 2221 9706 1042 8522 6747 6151 4780 8692 3876 5991 5167 579 4249 7105 1701 444 2574 222 3998 1065 3425 3371 5439 8637 2214 2439 250 8890 3027 1242 7384 5564 4168 7700 1943 8587 3566 8656 9390 929 6932 5902 368 5007 8156 5144 6483 8445 9797 8363 2027 1400 7777 2546 5041 3125 7995 9066 6773 9389 6809 2562 6275 3984 1061 8371 9177 4099 332 4435 608 4393 9666 9817 2298 3245 284 3039 962 5880 3216 8506 170 8183 1440 1636 6591 4954 1504 2008 3736 4078 9724 9190 6613 1638 5841 2069 1716 645 3718 5181 6874 847 9062 7435 6946 8722 3805 8913 5356 4515 6173 8533 7268 5786 3931 3105 2282 6390 4003 6216 8224 110 5165 6367 4809 1730 7512 7065 8288 3145 5734 3747 1670 7253 2788 1634 5459 3400 2776 2555 4059 3951 9959 1223 9865 2021 7672 2140 2834 6057 2761 9574 2875 9855 5996 8814 7032 9900 8878 5027 6385 1234 6259 9015 3810 4476 5222 7622 6128 4509 3578 623 5498 8390 1409 4829 2556 2137 6115 624 8375 4542 1255 400 2759 4164 2859 808 4600 3862 704 4179 3561 4877 4774 7770 2408 6847 9293 2013 4101 8672 3182 1509 5682 8649 2129 2755 2603 521 438 2611 7507 633 6293 6650 4931 5979 5177 8370 5155 1822 8071 3172 6651 2146 4589 7615 5406 3368 2109 3360 2350 6949 3041 4484 9922 6685 7976 3084 5286 6318 551 1688 3833 1264 8851 860 3502 4237 4060 1872 5586 9117 4932 7859 3324 1325 859 2492 6289 393 902 450 8245 8277 1406 9104 4912 5003 8518 8541 3497 6466 102 5900 1717 3457 1095 468 4887 8243 2782 6876 8599 2876 458 9256 4133 135 7903 2049 1469 3609 3828 383 7245 2900 4690 4419 5776 4700 8534 355 8981 6605 8325 7162 4500 3780 7345 9301 1848 4668 3134 2784 6018 1674 5846 6404 637 8414 9651 3751 2521 6902 1090 1205 5689 1417 5352 9206 4840 3095 565 457 5639 37 595 2897 6827 8856 5072 8636 7990 8405 5237 6063 2031 9990 5369 7111 697 2702 883 8674 4747 5715 950 2829 8818 7127 5740 8026 9342 7664 1488 1498 207 8578 5002 4468 7225 756 5510 1311 9149 6052 5409 7578 6228 5210 4929 4320 6867 7358 5807 576 8142 7758 5330 6309 3136 5207 3723 6405 5312 4914 7789 6338 996 8038 4262 4103 60 9020 76 157 5143 7266 3678 8343 8600 5456 4579 3516 2051 7230 5262 9737 5351 989 6465 9531 4521 6032 9828 6955 6219 9639 1347 4581 6072 7346 7198 1505 7209 3488 4052 1691 5403 793 4822 9143 3677 9288 3859 8403 9041 9134 7998 7566 8164 3304 6469 288 305 1808 7440 1584 6342 1764 1951 7873 7658 2491 9230 8922 2882 13 7288 6889 3305 1355 2920 7917 8168 2048 5557 5756 2099 5702 6594 8174 9373 5892 3365 9031 9349 963 9566 7256 8397 8458 1138 3341 593 9543 3419 7714 9652 2656 5626 3123 9888 4658 3741 8498 7173 5972 1125 1740 4048 6589 6529 2902 1919 5570 8669 9833 786 105 9648 6662 5774 7513 1349 5775 9664 4475 4573 7053 4282 4337 599 3118 4644 3995 4323 7141 5549 7832 9273 9326 2028 8747 2822 7182 9369 5755 1635 3524 6740 5952 2580 6447 7474 9818 3837 1318 5211 3844 568 1855 7376 573 2931 8456 6944 5293 7029 5709 6936 478 246 9107 2022 5646 9364 3290 3062 8080 2001 3151 881 8210 2957 8686 4494 6037 3260 9624 3818 9337 785 3415 9284 6656 4478 3552 8442 5938 209 6165 2304 4537 6985 7140 381 2288 6673 9323 7294 5741 6374 1971 6787 4566 1237 9610 7839 5543 6346 5995 1659 3638 6919 1529 644 9834 5371 3394 425 156 4128 129 9115 6214 2355 9864 2498 2269 5809 1770 1559 1952 5747 1767 2268 1614 9780 7831 2115 5236 1265 6811 5229 5975 1083 9308 5632 7150 9128 618 691 4312 6112 2446 2912 4304 4968 4095 2921 4998 4852 9185 3185 5280 7058 3738 1086 1230 7168 2816 7046 3790 1628 1185 6436 8213 3963 5440 3823 507 6448 4686 3286 3405 9131 8987 2727 2276 2071 7544 304 9785 6873 7258 8953 5248 1809 6777 7522 2345 1530 9183 2198 9363 2279 6569 3937 1821 6274 2347 2119 6967 5866 5105 133 7468 7740 5065 4428 1660 8596 6926 5266 9344 3724 5176 4033 5583 7944 3354 2602 8708 8157 4063 3064 2559 2509 5751 8058 2621 5425 694 948 622 1216 5305 8869 9762 6966 9621 7925 1572 9474 5208 7703 7043 2264 6623 1359 356 7247 3905 4426 3359 1047 5562 1192 2650 8053 8486 9265 3312 8221 4699 9262 6625 724 7880 7808 4313 8937 707 3323 774 4944 2959 6543 8450 3233 8932 5315 2359 3284 5838 8613 9180 7417 6644 1714 6510 8349 4845 2185 8630 429 1775 6756 6428 6215 4760 6736 3355 9619 6315 9951 5157 1519 219 2958 5822 6416 6890 7986 2862 4801 5251 1546 3399 8954 9497 3080 1851 9002 7223 549 6062 6536 9942 2337 9470 6614 3065 5558 7765 6262 7985 3599 5561 5932 1030 1723 2460 5907 2517 6227 2457 7569 7514 2148 3138 5944 7192 7303 8911 7071 8426 8138 6843 9637 9842 229 4832 7205 4321 4511 2105 9440 5238 1319 3460 3287 9895 9341 9838 3894 3483 3700 547 3074 8468 6661 2548 4925 297 2422 9319 1889 9478 7437 1399 9130 3201 1680 2899 3926 6184 2687 6953 8194 1177 949 3953 1531 8811 8788 6802 3564 396 578 7354 7981 1497 5522 8845 3945 9771 4024 1820 9167 4043 1818 4218 3309 8483 952 197 8454 6721 5171 2803 9084 2383 7185 9212 9214 8737 7351 4593 153 9451 1881 1066 1135 3043 9616 4010 6023 9873 7035 7495 2101 543 8742 4175 3126 5414 3588 5806 9908 9116 9194 730 3939 7103 3238 713 2978 9205 741 3258 9612 125 1342 9822 5992 1181 473 1092 867 6164 1096 5109 7186 1512 3194 2655 6081 4703 3616 2257 1156 3489 8132 192 3135 5133 3321 3342 1472 82 74 9766 6933 8653 6826 174 7681 342 7778 4227 3018 8634 7083 7589 7669 1 2331 1161 8505 9754 6010 3848 6463 1503 978 8479 9029 6333 2510 7010 8276 9210 4604 7068 6965 338 320 3030 4871 5812 3296 3054 3880 266 1331 6774 6570 2091 7002 9845 3347 6009 4245 6935 8230 4888 9561 7665 4660 6691 317 3989 7172 9140 3869 8711 5168 6887 3466 3007 6539 8041 5883 2412 231 9858 2843 2861 8551 7580 2200 4508 1794 3513 2145 514 475 2397 5174 4769 1222 1144 6106 916 4135 9614 3267 6969 7846 2992 2089 176 2948 5496 5128 8149 4437 4170 8113 5255 6737 4089 3950 21 3019 4517 2892 1709 5272 7325 1586 3147 2507 3028 6687 2357 1845 5336 8758 8648 4964 4642 3653 889 319 7056 2566 5098 3774 3199 1290 9516 3026 1293 3793 1317 3153 9490 4480 5696 3979 7686 6601 1979 5426 7142 7538 6686 344 7550 428 5119 6898 4127 8528 9967 7009 7564 6423 8441 3693 5428 4334 2265 9101 3159 5343 7370 8593 5878 5389 8994 373 5400 3206 5053 2212 6649 6506 9966 1854 2284 3897 3867 742 7044 8187 8120 5458 6731 7792 7844 4270 5645 3985 9272 2373 7479 7596 7721 4725 5448 5202 4495 5502 6983 230 6600 3407 1187 728 2155 6222 8552 3858 6140 9920 8857 5739 6307 6723 6133 9649 4733 5966 5052 2887 6016 2970 6938 5070 9770 6347 2793 9111 1997 4066 7372 1735 3442 6479 6415 8308 8520 4355 3707 9894 3325 78 9329 484 8794 4001 1882 6193 5033 7619 942 137 1183 1387 4197 9641 6252 5575 501 4993 9045 2801 2141 5129 1037 6110 3237 5826 6961 9740 8410 8683 9676 5484 7865 4344 9501 667 6993 938 5042 5016 2144 8050 8365 7892 3196 9235 1678 1604 8226 5299 2606 2390 9069 351 9153 5083 2954 2216 6750 4756 4557 3545 3430 2418 382 5341 1976 3011 7118 2448 6053 731 9627 9113 6590 2037 6547 2790 1554 6446 9430 2416 4285 2647 6452 8219 9483 8739 7414 967 6433 6111 3087 2639 1666 2468 142 2721 5960 4444 33 7729 2747 9533 4906 8772 659 577 9700 1898 4785 6442 5765 3827 9043 603 9884 4117 3635 4408 5860 9525 2310 5424 1606 2664 1842 917 8429 9296 9141 365 4365 2732 1561 4440 2380 4279 3383 7221 9758 9774 3542 3835 6622 2558 2873 3029 5258 3429 2933 6402 6152 5380 326 6544 3887 6514 4153 6945 8124 1320 5443 8566 2153 8921 7800 2122 8828 870 5588 2243 8565 9078 6788 4742 9260 9051 5920 2707 8688 5598 1329 455 2659 655 5093 5084 8940 3384 3142 9163 6047 1395 6798 3471 5020 218 4861 239 4202 1544 4327 447 4778 7949 8635 6006 7066 3375 3 4907 6189 7369 6480 5894 1542 3318 4118 1543 823 7357 4847 5772 3035 1676 4196 6035 1107 1819 6265 7575 4084 5437 3877 6059 4068 1959 3051 6031 7952 9630 8819 2086 2679 5183 4212 6840 9333 4041 5446 5076 6142 8989 9449 7496 2064 7794 5304 6040 2437 6637 8437 1535 463 1833 1432 9437 5793 9871 415 3782 7490 1532 598 2040 762 9886 4311 3803 2342 7910 5468 4239 7410 4841 3807 6845 6420 954 2598 7014 7713 8307 4806 3779 1004 2787 3615 956 6083 3085 5754 6790 8139 303 5074 2157 998 9521 3560 6075 9340 5224 1837 803 3554 4720 5206 3143 4191 4192 5090 9055 8311 2133 3024 3625 1761 9374 5699 9535 8171 5951 7273 1524 2867 7030 2316 8290 9414 2569 9192 5091 7466 4208 2811 7484 7138 416 9065 4315 2731 9004 1288 9921 148 1117 5534 9750 3205 213 6176 8761 8272 5665 2919 4379 7939 5465 7377 4152 3680 758 3645 5663 6849 318 8128 4894 7446 8773 1199 6576 4900 734 2683 6558 8005 8172 9862 2828 6208 5396 9849 936 696 6294 5103 2151 132 9009 5274 3649 1229 2079 6602 220 9269 8126 6542 9368 2464 6734 6278 4431 8678 8824 930 2564 6134 5780 654 5122 5362 316 6004 6511 1348 1963 9592 6717 1786 8963 3048 1682 1184 683 5077 9810 1980 8523 3511 1581 3955 8753 5069 4886 8387 3231 7361 6206 7296 5104 6683 7878 6758 3339 5253 615 4057 8345 2536 352 9181 7518 18 4794 379 4361 2514 9072 9317 7080 5410 8894 6279 1197 7051 7073 6771 7977 8322 3658 3755 6030 1795 3344 532 9899 3713 979 2844 7716 4739 1373 3605 767 3396 9137 7980 4357 1281 9835 5847 8271 3326 7131 8850 7072 7597 907 8261 8663 7195 3314 3294 7698 2909 640 8444 1303 1620 1350 9971 4483 4092 6727 4383 7893 7830 7811 7684 257 4636 6994 5334 8597 4576 85 9213 9356 5997 6928 6187 505 1028 6007 3121 5671 8733 1607 5037 6382 5036 9542 2413 1372 6942 5635 4831 6911 8943 1782 1859 1211 8265 357 4512 6502 1434 8646 813 9511 5381 981 7231 5631 6237 4534 5684 6098 7938 7835 4213 9139 2826 6853 2210 9165 6285 2587 1686 9786 2557 5745 3656 7806 9788 4528 406 4671 5720 8137 3820 8598 5270 9914 1673 4276 924 7085 299 5325 5962 9218 9738 2795 6124 3052 3150 5061 3961 5430 3860 2758 2818 3651 2572 554 3555 5936 9008 9030 1776 9421 217 182 5983 6116 2162 8082 7856 9553 3911 5034 1511 1499 7862 4765 6609 6619 1231 3930 4930 7197 6243 7983 8539 1580 9073 4267 6992 2192 3983 5667 4549 9926 1475 6577 818 3727 9445 4507 4433 9431 6484 3215 5552 8507 8530 3454 1508 8264 9191 1720 5327 3423 9866 757 4331 5308 7616 4596 2078 4268 6472 2296 2024 4143 6864 8235 8278 8897 3854 7469 2255 6627 8774 5302 6230 8193 6617 7568 536 2853 9582 1746 9670 3413 7641 2388 2874 3694 5537 6122 9905 7782 6912 2006 824 5725 3307 7639 3802 6247 8336 5419 1906 9395 2081 8564 1831 3240 3927 7921 9444 5864 6302 2130 8115 2341 2271 6041 1003 9736 369 6724 3954 9983 7874 8868 8679 9811 2520 84 2042 8710 811 7499 4994 4034 1557 2128 5412 2204 5587 7333 6886 831 5121 1123 3114 5298 7177 9941 9328 9064 5452 6438 3509 3155 1928 6917 7365 7749 345 3464 7194 4941 9840 273 5858 254 7452 7838 673 4198 3849 5199 3096 661 8218 3164 2624 8909 4460 708 1600 880 1495 643 3061 5145 4397 2085 5335 3596 2469 6441 93 2181 840 3816 1057 3408 8591 6266 3572 531 8490 3008 9184 8232 6345 4201 9151 8198 6582 8785 4609 1463 4332 3512 9049 5816 3917 9392 2622 5225 154 210 8843 9119 98 1408 9640 330 4061 1803 191 4878 3166 9320 650 118 8562 6065 3448 4595 4624 5761 3366 7934 4340 5331 1151 6810 6916 2794 2432 772 9358 1055 1240 4939 1589 4665 1153 3601 8477 1936 1454 8392 8306 9355 1713 2245 7761 2969 1850 3982 1039 2642 1051 452 6556 4351 5615 1742 5005 9945 2646 7301 6191 3109 8087 6513 8560 754 1617 5850 1270 9277 5503 7199 9367 6830 1244 3619 5318 3639 1470 4258 289 5533 3671 6015 1827 6389 9851 3469 2910 2121 4144 868 5814 9589 322 8858 6879 8527 3480 11 1961 6546 1103 6157 6823 4466 5553 4401 4251 9812 2083 6812 3992 6860 6376 7705 8947 9083 5828 69 1751 6838 5178 1424 2315 5565 7971 8771 2209 5386 5956 3577 5742 4979 7913 3994 3336 99 3208 8799 437 8936 6360 7343 8062 1013 2809 706 7688 5768 7864 6178 9397 3021 8489 1815 9684 8834 3800 3688 4486 3808 325 248 3473 5584 592 4177 7612 5554 6562 2705 3977 9187 5505 6775 7392 6855 6012 1582 1460 7802 5260 350 4943 9305 3875 9946 791 3765 6069 7212 3081 8664 8968 5547 7936 7776 3506 287 646 1360 3976 8625 7091 4640 8399 1217 2949 1034 1056 6533 5342 5948 8400 760 4310 387 7344 2522 6305 9039 4226 9400 4892 8676 1168 892 2963 8612 7786 1903 8524 4790 5172 4641 8125 2196 4763 2593 5134 7656 5513 606 3133 6211 8795 6249 9906 556 7308 4182 1364 4846 9683 2885 2403 1610 4828 9487 4108 5527 7812 7117 1361 7224 9375 5378 3176 2434 1430 890 2202 5432 510 4339 7241 2294 6027 8705 8775 4956 2193 2568 360 6648 4447 1155 7732 4559 2698 5524 3759 8891 8094 8006 443 9208 3510 1576 3589 27 8886 5184 8099 1164 8292 3470 7472 3401 8668 4710 51 7772 4160 4424 4453 8749 4659 533 1449 1878 2917 6636 8504 8356 6785 8930 7526 4130 7238 4958 5999 1188 1679 671 7302 4492 6947 3761 8657 1816 3851 5928 44 3120 5704 3174 5367 4955 2821 4997 9825 235 6491 4972 6424 1556 7853 2166 2291 1957 8480 9802 3144 2097 6716 4380 7315 9912 9503 5934 1011 5825 2371 6708 8165 2346 2839 6550 9823 9405 4726 2218 792 7843 5338 73 147 4082 9423 4454 9556 1445 285 480 8462 4363 2223 2643 477 6743 47 7906 2883 1618 1844 4899 8209 6432 1753 9999 5383 1612 4046 4085 7643 9721 3209 5051 5314 2719 7827 7701 9135 7312 4294 3770 4402 6029 1748 9520 7547 106 616 7809 8632 879 3882 8712 4504 2908 6303 3243 4038 2372 8685 4772 2394 6596 9800 8561 2222 9523 6003 5361 9059 3959 689 4991 8295 4638 4629 684 88 7374 7399 9498 2379 3428 6779 6704 9232 5757 1091 6725 8227 8022 8368 7739 5471 564 8086 1174 9719 8961 675 6500 3207 1314 6494 4216 9669 8147 9362 6102 8605 8412 8469 2308 9094 6403 4556 2981 2400 8225 1732 4921 679 362 2838 7429 1173 9546 2669 1779 6895 5187 586 2150 8034 7965 3606 1745 3665 4252 2797 4779 9757 119 3825 2424 6770 9499 8877 7598 4817 8768 4628 1118 1967 6713 925 2358 3447 8647 9725 7889 2170 2436 4333 4834 657 8829 2589 2658 6444 4553 2907 7636 8396 5442 2945 4527 3721 247 9 4520 3217 2463 5180 3745 6772 2280 843 8904 2072 8031 3092 8616 1890 3499 1239 9493 7804 9859 1280 1862 3565 8703 2080 4927 5445 5019 703 1652 130 426 7858 3038 6129 6056 7751 2118 4163 1884 4330 1999 1058 1031 6256 2663 2451 439 8259 6905 4857 7762 2973 5539 4535 8331 7289 8143 5094 4701 1171 621 765 4113 5903 5708 163 6421 9237 7018 9306 7520 5633 3302 6563 8559 5713 1060 2123 2421 5893 3116 307 5942 5476 1552 4800 5346 9682 3481 8833 7287 1734 9695 4032 778 4611 9018 9513 9878 3932 7559 7583 2014 5872 6077 6701 7661 7779 8421 358 6559 8196 8330 8377 7220 8870 8144 3788 8516 1838 5616 3676 5415 8395 7015 4837 1378 3099 8671 8978 8177 7049 9053 7203 6471 6518 7719 3369 636 9584 2375 8042 8352 1605 2334 2131 6552 9413 7912 9947 8675 5840 5384 8097 6337 2456 2168 9701 4768 6419 5970 4158 9168 9198 7126 1392 6127 3557 4737 7323 1273 3795 5842 5216 1771 4405 9976 9112 2392 2554 1369 3180 4681 5571 1654 1562 2772 6592 1728 272 8054 1909 7386 5778 3308 525 6505 6495 3253 9705 7814 893 4477 4880 723 7359 1341 6155 6457 725 9578 7402 5889 1970 8029 1656 853 2220 3141 9147 2135 3060 4807 4306 6567 9380 3348 5220 4238 3301 7218 4854 9587 4555 4936 375 1036 8701 276 8529 6808 9387 216 3846 9843 9548 1566 2009 2322 1946 7060 6705 5701 7236 6167 3496 4260 9280 8690 2806 1008 8253 1624 7139 6418 6017 6782 3865 9282 8925 7627 6904 702 4482 7666 7491 4037 7592 2608 1335 8240 6973 9056 5925 9934 2275 1719 2915 7037 7551 4445 955 5269 1005 4162 8902 8626 1451 4093 5700 2756 6132 465 8039 4694 5365 1915 2941 5929 1697 5733 5530 7092 6001 6224 9741 9433 5141 9325 3769 6607 8938 7895 1001 3947 662 5567 2201 8580 9748 9729 8067 4924 1374 5218 1186 1516 7521 1436 8084 4525 6411 3424 5112 2401 8790 2699 7025 9805 9918 1867 371 7637 2472 1062 8425 5912 3218 1298 1108 1158 7606 2283 3633 7257 8901 1807 951 6925 9923 2116 8046 2653 3541 5668 152 2691 6989 3698 9076 6410 7829 4077 7824 8960 9675 4693 6090 6406 1225 3647 487 7420 9765 7426 7482 3414 7382 9238 6427 4292 3672 2487 3791 8020 1553 1162 2681 2351 520 739 1922 1111 9406 9671 2411 6190 4574 7270 1136 4606 6863 8681 9399 9606 9632 4796 5897 6169 1220 918 7638 2526 4662 8379 7191 2728 3909 386 3455 64 2529 2913 8608 8694 337 7624 1119 2378 261 1067 314 5404 6409 1541 3861 7577 7031 5113 4775 7848 3965 2385 5287 2278 9157 1494 181 5711 2211 5131 8079 7618 9322 812 2502 9427 4096 4146 7817 8931 8386 3728 5681 7508 4308 9604 5438 8161 1523 1639 8887 4656 7403 5323 9204 1897 8941 5192 53 3271 2404 4868 9605 8642 2177 7275 6244 8677 9391 7545 789 7306 9560 1722 2518 6026 3866 1942 2050 6516 7497 4926 865 4257 7234 6786 111 2482 9042 3106 7866 3422 4446 5241 1052 9110 9636 7264 7948 3362 9166 5268 748 294 2476 7005 3273 9957 4040 5303 2447 4767 7803 6639 8709 4472 9026 3295 1402 5965 161 5205 7754 541 1163 4577 3575 6386 2020 4905 1587 937 9978 9118 6821 5243 5186 4305 1539 2799 4302 6330 6534 5 4490 7899 8638 9159 4414 5749 8180 8743 8535 8946 9850 9727 3082 6671 9122 6611 6082 3478 7601 6991 8553 4171 6678 9801 9100 7653 8602 4298 8366 6202 4134 3666 3717 4109 4945 9267 4712 7328 9274 6443 4346 8935 3612 1367 3410 8707 1078 1152 9324 9893 5854 3411 570 874 6498 1646 9653 6679 3799 596 5337 1256 1525 5307 3710 3229 5163 987 3670 5947 6995 8453 9179 4764 1315 6538 1496 6956 3270 4215 3607 8777 8568 7463 5612 7462 7465 1157 8317 9595 1648 6203 8263 9681 1236 315 9216 7599 7712 5853 8011 5193 4372 2850 4561 1501 4176 2865 9103 8475 3046 2292 6799 8061 3611 5622 1883 9313 9415 131 6022 8852 7385 136 7153 2277 3067 5110 2644 4111 6039 8579 5450 717 1357 8109 7456 7360 8455 4288 1796 1711 2760 4297 2224 1259 5470 6351 6963 8873 462 4246 4562 4908 8495 3548 7320 3234 339 9567 4770 6842 9275 2139 3198 5349 1568 2003 5678 1403 6507 9885 6310 7918 9576 9203 3686 5769 6884 1032 4588 4833 4635 4762 6901 2889 5000 397 2597 3956 8740 8432 5289 4225 5117 6147 9339 7796 1960 8095 6258 4950 81 5401 8650 9509 2387 8001 7634 4601 9749 575 3732 7393 7763 3673 2860 5636 5993 1336 9290 3361 3263 518 2195 6695 2723 8725 1146 4183 3684 1438 2896 9335 4741 8827 6089 539 5670 923 4086 399 7483 7673 1750 4729 8804 8802 7519 2199 8558 9227 1009 1689 3274 4023 885 9663 6580 3491 6803 750 2005 411 3395 6693 5648 8073 5271 4132 8010 2823 8406 5064 2836 6235 8903 7353 3222 6702 1677 1876 6156 2815 5922 9623 8933 408 4455 2796 8443 562 5413 2746 5865 1762 3872 2057 311 5984 9739 4897 4022 9795 3681 5004 1041 3919 3974 5959 1388 6763 3476 5366 7233 3804 8586 3363 769 2188 9154 3587 5283 1126 8574 6852 7954 4416 9447 1631 1076 3662 6138 4572 7007 394 1023 506 7752 6726 4273 5829 9182 837 2710 535 6070 1439 4734 5032 511 2575 8732 7834 5516 6051 9880 8800 6384 3072 2402 4777 5541 8536 3801 1338 2499 1913 1193 8228 2804 80 6512 3711 9229 3111 5857 6545 4619 6435 8270 3337 607 3942 6856 4035 1567 4457 4723 1473 630 494 9594 2577 4571 5226 214 3220 489 1482 6464 710 9974 4928 8266 1333 4233 1869 8391 9281 7232 826 8918 1985 6776 972 4094 6078 1594 3380 8803 3972 7036 4823 7825 5518 6979 4388 5373 7187 65 953 5559 9613 5523 9052 3627 3057 6999 8900 3830 2095 6462 5602 6250 7711 4803 9174 3701 4766 9911 9215 413 2633 144 3879 1993 1548 5273 9772 775 6825 2142 3929 4326 6643 3987 9127 336 4375 3580 8135 1189 6735 2990 6180 6288 5686 1947 5135 2766 4617 4850 2764 2657 1261 7047 1097 807 1995 7460 8111 7679 8589 7958 8926 6760 4106 4885 8476 9940 3621 1327 2946 1428 8461 2592 5736 1861 1923 6314 7003 3946 291 3938 2617 6371 9744 2068 1577 2438 9398 7922 8633 1421 2812 8150 7588 6624 9394 1043 6437 8554 6934 499 7026 6666 5935 8763 7214 331 2016 7262 495 5392 8842 1637 4352 7982 9318 4717 7987 7931 9715 5915 6166 2258 7738 5388 2241 7710 9189 2407 5628 7274 9310 3070 6610 6200 9228 3767 2934 964 1931 4300 9254 1804 7647 8696 9819 7951 5698 7506 660 4422 3256 9088 788 3890 3452 9506 8846 2364 8912 6674 270 9488 267 5360 2847 2343 2045 90 768 5511 1407 8121 7509 7062 5395 3453 3683 9226 4568 5376 312 6496 4299 159 6357 3935 6049 4608 8769 2374 9806 9515 3163 7438 8110 7781 2052 6813 9388 7204 6276 7870 6699 3604 2087 9897 8839 5278 9120 9528 9777 4889 9450 1492 7771 935 1286 9550 9266 9910 6869 2516 8907 3886 7352 8130 3832 8202 6846 4137 4883 6970 8181 1727 6108 2713 3329 5114 665 8604 7078 672 9021 8601 8182 5863 3515 5441 1799 5011 1777 5625 151 4583 2065 2367 1106 3283 6709 8999 4696 1712 7644 6296 557 1149 8765 3406 5821 9752 2236 2692 4709 709 4058 7961 1704 1049 4586 1754 1500 4670 5855 4667 346 797 1292 519 5796 3269 6196 571 2046 1040 9703 9019 1806 3418 3000 4859 9586 35 2235 7188 9988 8091 7675 258 5197 6566 9500 7516 6257 4209 4102 5978 7970 5353 1276 4159 1817 1608 6084 1574 6109 4802 4867 6977 3682 6680 2272 6741 177 183 3034 4695 2714 973 2560 4204 7857 7419 2004 4981 5402 8610 5223 4697 7884 2962 4714 7064 2693 6308 5290 6313 1088 4473 8629 563 1747 2703 3020 5073 8065 3812 5411 9913 3940 2512 1873 4124 8991 3881 9481 5881 9763 5873 3177 8155 3668 5848 2461 4736 2043 1201 2319 1121 483 3674 52 5244 6714 6806 6366 1370 2467 9723 1419 6696 1014 9098 9352 2868 4547 4819 9061 5675 2671 1466 7900 469 2916 9268 9468 9152 8661 5162 7227 243 5939 2173 7668 6878 3031 1650 8173 5676 4157 4295 6707 8893 3829 9138 4539 862 5770 8859 5766 2215 2576 9761 1724 5111 3291 309 4627 9244 5333 8776 48 107 9436 8569 3285 8812 4746 1591 5594 6488 9242 7847 1662 7211 354 8248 9034 3277 9759 1457 9626 9998 464 5265 7137 1894 8898 3228 1112 7276 6557 9259 4947 3275 9160 4864 2525 6881 2159 4704 3771 3576 7175 6368 4345 4749 7055 3122 5127 8942 2734 1583 5601 8134 2857 4965 7381 4732 1079 4322 1465 3146 863 5014 891 1802 278 8364 9677 9956 7678 2428 2059 6121 7415 6322 2047 1874 7993 2630 1972 6079 2660 8510 8118 9460 8313 2673 2352 2289 2661 5794 977 1864 7888 5233 7759 9176 2063 8640 5600 6573 3763 9011 7149 9089 3535 9231 1925 5209 1860 6527 7000 4 6892 2677 9086 751 6185 9686 7488 2134 6233 7654 2689 286 2552 4989 2750 3794 9633 9457 7571 3204 9017 8576 6061 8051 6730 3768 8481 313 8796 2997 753 3479 3251 8312 9573 6253 8189 6301 9365 6316 5958 1321 4250 5324 1907 5040 6408 7098 5479 8402 1458 4516 4230 391 4200 1059 7860 5254 7553 8700 1849 4602 8609 8059 7332 9787 2524 9480 4229 6655 6927 476 3817 3167 3634 4526 6621 1702 4898 376 1022)
index 336329b..baaf614 100644 (file)
@@ -1,27 +1,31 @@
 import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.SortedSet;
+import java.util.TreeSet;
 
 public class ChercherMin {
        public static int comp=0;
-       public static int[] CURang(Permutation P, ArrayList<Paire> R) {
+       public static int[] CURang(Permutation P, SortedSet<Paire> R) {
                comp=0;
                int[] mins = new int[R.size()];
                /*
                 * Coll : ({},id)
-                * 
+                *
                 */
                ClasseUnion C = new ClasseUnion(P.getN()+2);
                // calcule dans la classe
                comp++; // calcule param
-               
+
                comp+=2; // init  + test
                for (int h = 0; h <= P.getN(); h++) {
                        comp+= 2; // test+ incrementation
-                       
+
                        int ph = P.getElts(h);
                        comp++;
-                       
+
                        comp++; // test
-                       for(Coll c : C.getColl()){
+                       SortedSet<Coll> setC = new TreeSet<Coll>(Arrays.asList(C.getColl()));
+                       for(Coll c : setC.tailSet(new Coll(ph))){ // on récupère tous les éléments dont id >= ph
                                comp++; // init
                                comp++; // test
                                if (!c.empty()) {
@@ -31,69 +35,69 @@ public class ChercherMin {
                                        }
                                }
                        }
-                       
+
                        //calcule dans union
                        C.add(ph,h);
-                       
+
                        comp++; // test
-                       for(Paire pr : R) {
+                       for(Paire pr : R.tailSet(new Paire(0,h))) {
+                               if (pr.getB() != h) 
+                                       break;
+                               
                                comp++; // affectation
-                               comp++; // test
-                               if (h == pr.getB()) {
-                                       mins[Math.min(P.getElts(pr.getA()),P.getElts(pr.getB()))-1] = C.classeVal(pr.getA());
-                                       //System.out.println("Min("+pr.getA()+","+pr.getB()+") = " +C.classeVal(pr.getA()));
-                               }
+       
+                               mins[Math.min(P.getElts(pr.getA()),P.getElts(pr.getB()))-1] = C.classeVal(pr.getA());
+                               //System.out.println("Min("+pr.getA()+","+pr.getB()+") = " +C.classeVal(pr.getA()));
                        }
                        //System.out.println(C);
                }
                return mins;
        }
-       
-       public static int[] CURangCompress(Permutation P, ArrayList<Paire> R) {
+
+       public static int[] CURangCompress(Permutation P, SortedSet<Paire> R) {
                comp = 0;
                int[] mins = new int[R.size()];
                /*
                 * Coll : ({},id)
-                * 
+                *
                 */
                ClasseUnionCompress C = new ClasseUnionCompress(P.getN()+2);
                // calcule dans la classe
                comp++; // calcule param
-               
+
                comp+=2; // init  + test
                for (int h = 0; h <= P.getN(); h++) {
                        comp+= 2; // test+ incrementation
-                       
+
                        int ph = P.getElts(h);
                        comp++;
-                       
+
                        comp++; // test
-                       for(Coll c : C.getColl()){
+                       
+                       SortedSet<Coll> setC = new TreeSet<Coll>(Arrays.asList(C.getColl()));
+                       for(Coll c : setC.tailSet(new Coll(ph))){ // on récupère tous les éléments dont id >= ph
                                comp++; // init
                                comp++; // test
                                if (!c.empty()) {
-                                       comp++; // test
-                                       if (c.getId() >= ph) {
-                                               C.union(ph,c.getId()); // calcul dans union
-                                       }
+                                       C.union(ph,c.getId()); // calcul dans union
                                }
                        }
-                       
+
                        //calcule dans union
                        C.add(ph,h);
-                       
+
                        comp++; // test
-                       for(Paire pr : R) {
+                       for(Paire pr : R.tailSet(new Paire(0,h))) { // recupere  tous les éléments donc la paire (a,b) où b >= h
+                               if (pr.getB() != h) //element trier. donc si pas egal on ne regarde pas les elements suivant
+                                       break;
+                               
                                comp++; // affectation
-                               comp++; // test
-                               if (h == pr.getB()) {
-                                       mins[Math.min(P.getElts(pr.getA()),P.getElts(pr.getB()))-1] = C.classeVal(pr.getA());
-                                       //System.out.println("Min("+pr.getA()+","+pr.getB()+") = " +C.classeVal(pr.getA()));
-                               }
+                               mins[Math.min(P.getElts(pr.getA()),P.getElts(pr.getB()))-1] = C.classeVal(pr.getA());
+                               //System.out.println("Min("+pr.getA()+","+pr.getB()+") = " +C.classeVal(pr.getA()));
                        }
                        //System.out.println(C);
                }
-               
+
                return mins;
        }
 }
index aba1704..d50abcf 100644 (file)
@@ -1,26 +1,28 @@
+import java.util.Vector;
+
 
 public class ClasseUnion {
        private int[] p_; // tableau de père
        private Coll[] ens_; // ensemble de paire correspondant
        
+
        public ClasseUnion(int t){
                p_ = new int[t];
                ChercherMin.comp++; //init
                ens_ = new Coll[t];
                ChercherMin.comp++; //init
-               
+
                ChercherMin.comp+=2; // init + test
                for (int i = 0; i < t; i++) {
                        ChercherMin.comp+=2; // test + incrementation
-                       
+
                        p_[i] = -1;
                        ChercherMin.comp++;
                        ens_[i] = new Coll(i);
                        ChercherMin.comp++;
                }
-               
        }
-       
+
        public int classe(int i) {
                ChercherMin.comp++; // test
                if (p_[i] == -1) {
@@ -30,7 +32,7 @@ public class ClasseUnion {
                        return classe(p_[i]);
                }
        }
-       
+
        public void union(int a, int b) {
                ChercherMin.comp++; // test
                if (classe(a) != classe(b)) {
@@ -41,32 +43,32 @@ public class ClasseUnion {
                        ChercherMin.comp+=3; //affectation
                }
        }
-       
+
        public boolean pasPaire(int id) {
                ChercherMin.comp++; //test
                return ens_[id] == null;
        }
-       
+
        public void add(int id, int val) {
                ChercherMin.comp++; //affectation
-               ens_[id].add(val); 
+               ens_[id].add(val);
        }
-/*     
+/*
        public void creer(int i) {
                ens_[i] = new Coll(i);
        }
-*/     
+*/
        public Coll[] getColl() {
                return ens_;
        }
-       
+
        public void toStr()
        {
                for (int i = 0; i < p_.length;i++)
                        System.out.print(i + ":" + p_[i] + "    ");
                System.out.println();
        }
-       
+
        public String toString() {
                String s = "{";
                for (Coll c : ens_){
@@ -75,14 +77,14 @@ public class ClasseUnion {
                                s+=",";
                        }
                }
-               
+
                if (s.charAt(s.length()-1) == ',')
                        s = s.substring(0,s.length()-1);
-               
+
                s+="}";
                return s;
        }
-       
+
        public int classeVal(int i) {
                ChercherMin.comp++; //test
                for (Coll c:ens_) {
index 02ffaf9..3164073 100644 (file)
@@ -2,24 +2,24 @@
 public class ClasseUnionCompress {
        private int[] p_; // tableau de père
        private Coll[] ens_; // ensemble de paire correspondant
-       
+
        public ClasseUnionCompress(int t){
                p_ = new int[t];
                ChercherMin.comp++; //init
                ens_ = new Coll[t];
                ChercherMin.comp++; //init
-               
+
                ChercherMin.comp+=2; // init + test
                for (int i = 0; i < t; i++) {
                        ChercherMin.comp+=2; // test + incrementation
-                       
+
                        p_[i] = -1;
                        ChercherMin.comp++;
                        ens_[i] = new Coll(i);
                        ChercherMin.comp++;
                }
        }
-       
+
        public int classe(int i) {
                ChercherMin.comp++; // test
                if (p_[i] == -1) {
@@ -32,7 +32,7 @@ public class ClasseUnionCompress {
                        return cl;
                }
        }
-       
+
        public void union(int a, int b) {
                ChercherMin.comp++; // test
                if (classe(a) != classe(b)) {
@@ -43,32 +43,32 @@ public class ClasseUnionCompress {
                        ChercherMin.comp+=3; //affectation
                }
        }
-       
+
        public boolean pasPaire(int id) {
                ChercherMin.comp++; //test
                return ens_[id] == null;
        }
-       
+
        public void add(int id, int val) {
                ChercherMin.comp++; //affectation
-               ens_[id].add(val); 
+               ens_[id].add(val);
        }
-/*     
+/*
        public void creer(int i) {
                ens_[i] = new Coll(i);
        }
-*/     
+*/
        public Coll[] getColl() {
                return ens_;
        }
-       
+
        public void toStr()
        {
                for (int i = 0; i < p_.length;i++)
                        System.out.print(i + ":" + p_[i] + "    ");
                System.out.println();
        }
-       
+
        public String toString() {
                String s = "{";
                for (Coll c : ens_){
@@ -77,14 +77,14 @@ public class ClasseUnionCompress {
                                s+=",";
                        }
                }
-               
+
                if (s.charAt(s.length()-1) == ',')
                        s = s.substring(0,s.length()-1);
-               
+
                s+="}";
                return s;
        }
-       
+
        public int classeVal(int i) {
                ChercherMin.comp++; //test
                for (Coll c:ens_) {
index da950ac..d6bfa2f 100644 (file)
@@ -2,7 +2,7 @@ import java.util.Iterator;
 import java.util.Vector;
 
 
-public class Coll {
+public class Coll implements Comparable<Coll> {
        private Vector<Integer> ens_;
        private int id_;
        
@@ -53,4 +53,8 @@ public class Coll {
        public boolean empty() {
                return ens_.size() == 0;
        }
+
+       public int compareTo(Coll c) {
+               return id_ - c.id_;
+       }
 }
index 66fe982..894a8d4 100644 (file)
@@ -1,4 +1,4 @@
-public class Paire\r
+public class Paire implements Comparable<Paire>\r
 {\r
        private int a;\r
        private int b;\r
@@ -40,5 +40,25 @@ public class Paire
        {\r
                this.b = b;\r
        }\r
+       \r
+       public int compareTo(Paire p) {\r
+               if (p.b < b) {\r
+                       return 1;\r
+               }\r
+               else if (p.b > b) {\r
+                       return -1;\r
+               }\r
+               else {\r
+                       if (p.a < a) {\r
+                               return 1;\r
+                       }\r
+                       else if (p.a > a) {\r
+                               return -1;\r
+                       }\r
+                       else {\r
+                               return 0;\r
+                       }\r
+               }\r
+       }\r
 }\r
 \r
index 38dfe78..253b9c5 100644 (file)
@@ -142,7 +142,9 @@ public class Permutation
        {
                int r, tmp;
                for (int i = 0; i < n ;i++)
-                       elts[i] = i + 1;
+                       elts[i] =  i+1;
+               
+               /*
                for (int i = 0; i < n ;i++)
                {
                        r = (int)((Math.random() * n * 10) % n);
@@ -150,6 +152,7 @@ public class Permutation
                        elts[r] = elts[i];
                        elts[i] = tmp;
                }
+               */
        }
 }
 
index df30a0b..f2e8e7b 100644 (file)
@@ -1,6 +1,12 @@
+import java.io.BufferedWriter;\r
+import java.io.FileNotFoundException;\r
 import java.io.FileReader;\r
+import java.io.FileWriter;\r
+import java.io.IOException;\r
 import java.util.ArrayList;\r
 import java.util.Scanner;\r
+import java.util.SortedSet;\r
+import java.util.TreeSet;\r
 \r
 \r
 public class Prog\r
@@ -86,31 +92,44 @@ public class Prog
 \r
                for (int i = 0; i < p.size(); ++i)\r
                {\r
-                       System.out.println("Permutation " + (i + 1) + " : " + p.get(i).eltsToString());\r
-                       p.get(i).chercherMinPremier();\r
-                       System.out.println("Solutions :");\r
-                       int comp = p.get(i).chercherMinPremier();\r
-                       System.out.println("MinPremiers    : " + p.get(i).minsToString() + " Complexité : " + comp);\r
-                       ArrayList<Paire> paires = new ArrayList<Paire>();\r
-\r
+                       SortedSet<Paire> paires = new TreeSet<Paire>();\r
                        for (int j = 1; j < p.get(i).getN(); j++) {\r
                                paires.add(new Paire(p.get(i).indexOf(j),p.get(i).indexOf(j+1)));\r
                        }\r
-\r
                        int[] mins;\r
+\r
+                       System.out.print("Permutation n=" + p.get(i).getN() + " : ");\r
+                   System.out.println(p.get(i).eltsToString());\r
+\r
+                       System.out.print("MinPremiers    : ");\r
+                       int comp = p.get(i).chercherMinPremier();\r
+                       System.out.println(p.get(i).minsToString());\r
+                       System.out.println("Complexité : " + comp);\r
+\r
                        mins = ChercherMin.CURang(p.get(i),paires);\r
-                       System.out.print("CURang         : (");\r
+                       System.out.print("CURang         : ");\r
+\r
+                       System.out.print("(");\r
                        for (int j : mins) {\r
                                System.out.print(" "+j+" ");\r
                        }\r
-                       System.out.println(") Complexité : " + ChercherMin.comp);\r
+                       System.out.println(")");\r
+\r
+                       System.out.println("Complexité : " + ChercherMin.comp);\r
+\r
 \r
                        mins= ChercherMin.CURangCompress(p.get(i),paires);\r
-                       System.out.print("CURangCompress : (");\r
+                       System.out.print("CURangCompress : ");\r
+\r
+                       System.out.print("(");\r
                        for (int j : mins) {\r
                                System.out.print(" "+j+" ");\r
                        }\r
-                       System.out.println(") Complexité : " + ChercherMin.comp);\r
+                       System.out.println(")");\r
+\r
+                       System.out.println("Complexité : " + ChercherMin.comp);\r
+\r
+\r
                        System.out.println("**************************************************************");\r
                }\r
 \r
@@ -118,29 +137,53 @@ public class Prog
        /**************************************\r
         * Généation aléatoire de Permutation *\r
         **************************************/\r
-\r
 /*\r
-               for (int i = 3; i < 80 ; ++i) {\r
-                       Permutation pbis = new Permutation();\r
-                       pbis.setN(i);\r
-                       pbis.genRandom();\r
-                       System.out.println("Permutation    : " + pbis.eltsToString());\r
-                       pbis.chercherMinPremier();\r
-                       int comp = pbis.chercherMinPremier();\r
-                       System.out.println("Solutions      : " + pbis.minsToString());\r
-                       System.out.println("MinPremiers    : " + comp);\r
-                       ArrayList<Paire> paires = new ArrayList<Paire>();\r
-\r
-                       for (int j = 1; j < pbis.getN(); j++) {\r
-                               paires.add(new Paire(pbis.indexOf(j),pbis.indexOf(j+1)));\r
-                       }\r
+               BufferedWriter out = null;\r
+               try {\r
+                       out = new BufferedWriter ( new FileWriter ("./data" ) ) ;\r
+\r
+                       String s;\r
+                       for (int i = 2; i <= 1000 ; ++i) {\r
+                               s = ""+i;\r
+                               Permutation pbis = new Permutation();\r
+                               pbis.setN(i);\r
+                               pbis.genRandom();\r
+                               System.out.println("Permutation n="+i+" : " + pbis.eltsToString());\r
+                               pbis.chercherMinPremier();\r
+                               int comp = pbis.chercherMinPremier();\r
+                               System.out.println("Solutions      : " + pbis.minsToString());\r
+                               System.out.println("MinPremiers    : " + comp);\r
+\r
+                               s+=";"+comp;\r
+\r
+                               SortedSet<Paire> paires = new TreeSet<Paire>();\r
+                               for (int j = 1; j < pbis.getN(); j++) {\r
+                                       paires.add(new Paire(pbis.indexOf(j),pbis.indexOf(j+1)));\r
+                               }\r
 \r
-                       int[] mins;\r
-                       mins = ChercherMin.CURang(pbis,paires);\r
-                       System.out.println("CURang         : " + ChercherMin.comp);\r
+                               int[] mins;\r
+                               mins = ChercherMin.CURang(pbis,paires);\r
+                               System.out.println("CURang         : " + ChercherMin.comp);\r
+\r
+                               s+=";"+ChercherMin.comp;\r
 \r
-                       mins= ChercherMin.CURangCompress(pbis,paires);\r
-                       System.out.println("CURangCompress : " + ChercherMin.comp);\r
+                               mins= ChercherMin.CURangCompress(pbis,paires);\r
+                               System.out.println("CURangCompress : " + ChercherMin.comp);\r
+\r
+                               s+=";"+ChercherMin.comp;\r
+\r
+                               out.write(s);\r
+                               out.newLine();\r
+                       }\r
+               }\r
+               catch (FileNotFoundException e) {\r
+                       e.printStackTrace();\r
+               }\r
+               catch (IOException e) { }\r
+               finally {\r
+                       try {\r
+                               out.close();\r
+                       } catch (IOException e) { }\r
                }\r
 */\r
        }\r