A Simple Measure of Gene Order Similarity

In “Enumerating Gene Orders”, we started talking about comparing the order of genes on a chromosome taken from two different species and moved around by rearrangements throughout the course of evolution. One very simple way of comparing genes from two chromosomes is to search for the largest collection of genes that are found in the same order in both chromosomes. To do so, we will need to apply our idea of permutations. Say that two chromosomes share nn genes; if we label the genes of one chromosome by the numbers 1 through n in the order that they appear, then the second chromosome will be given by a permutation of these numbered genes. To find the largest number of genes appearing in the same order, we need only to find the largest collection of increasing elements in the permutation.

Problem
A subsequence of a permutation is a collection of elements of the permutation in the order that they appear. For example, (5, 3, 4) is a subsequence of (5, 1, 3, 4, 2).
A subsequence is increasing if the elements of the subsequence increase, and decreasing if the elements decrease. For example, given the permutation (8, 2, 1, 6, 5, 7, 4, 3, 9), an increasing subsequence is (2, 6, 7, 9), and a decreasing subsequence is (8, 6, 5, 4, 3). You may verify that these two subsequences are as long as possible.
Given: A positive integer n≤10000n≤10000 followed by a permutation ππ of length nn.
Return: A longest increasing subsequence of ππ, followed by a longest decreasing subsequence of ππ.
Sample Dataset
5
5 1 4 2 3
Sample Output
1 2 3
5 4 2

Citation

Adapted from Jones & Pevzner, *An Introduction to Bioinformatics Algorithms, Problem 6.48.

http://rosalind.info/problems/lgis/

解题思路

本题就是求解动态规划后的 多条最优路径输出 问题。递增/减状态转移方程都差不多，唯一区别就是增或减。
状态定义：Longest Increasing Subsequence - 图1 表示以 i 为结尾的最长递增子序列长度。
状态转移方程：Longest Increasing Subsequence - 图2
状态初始化：所有以自己本身为递增子序列长度为 1 。

  1. from typing import List, Tuple
  3. class Solution:
  4.     def lengthOfLIS(self, nums: List[int]) -> Tuple[List[int]]:
  5.         n = len(nums)
  6.         # 1. 动态规划
  7.         increase, decrease = [1] * n, [1] * n  # 初始化为 1
  8.         lis = lds = 1  # 必须是 1 而不是 0
  9.         for i in range(n):
  10.             for j in range(i):  # 最有开始
  11.                 if nums[j] < nums[i]:  # 关键1
  12.                     increase[i] = max(increase[i], increase[j] + 1)  # 关键2，+1 操作与自身赋值
  13.                     lis = max(lis, increase[i])
  14.                 if nums[j] > nums[i]:
  15.                     decrease[i] = max(decrease[i], decrease[j] + 1)  # 关键2，+1 操作与自身赋值
  16.                     lds = max(lds, decrease[i])
  17.         # 2. 回溯路径输出
  18.         def backtrace(idx: int, dp: List[List[int]], cmp: "Function(x, y)", path: List[int], res: List[List[int]]) -> None:
  19.             path.append(nums[idx])  # 选择状态
  20.             if dp[idx] == 1:
  21.                 res.append(path[::-1])
  22.             for j in range(idx - 1, -1, -1):
  23.                 if dp[j] + 1 == dp[idx] and cmp(nums[j], nums[idx]):
  24.                     backtrace(j, dp, cmp, path, res)
  25.             path.pop()  # 撤销状态
  27.         # 3. 遍历找到 LIS/LDS 结尾
  28.         LIS, LDS = [], []
  29.         for idx in range(n - 1, -1, -1):
  30.             if increase[idx] == lis:
  31.                 backtrace(idx, increase, lambda x, y: x < y, [], LIS)
  32.             if decrease[idx] == lis:
  33.                 backtrace(idx, decrease, lambda x, y: x > y, [], LDS)
  34.         return (LIS, LDS)
  36. # n = int(input())
  37. nums = list(map(int, input().split()))
  38. lis, lds = Solution().lengthOfLIS(nums)
  39. print(lis)
  40. print(lds)

上述代码是输出所有可能组合，也就是所有递增/减子序列，遇到下面测试用例会跑很久！但是实际上机器只需要我们得到一个最佳结果即可。因此只要上述 backtrace 操作找到一个最优解，我们就停止搜索。

  1. from typing import List, Tuple
  3. class Solution:
  4.     def lengthOfLIS(self, nums: List[int]) -> Tuple[List[int]]:
  5.         n = len(nums)
  6.         # 1. 动态规划
  7.         increase, decrease = [1] * n, [1] * n  # 初始化为 1
  8.         lis = lds = 1  # 必须是 1 而不是 0
  9.         for i in range(n):
  10.             for j in range(i):  # 最有开始
  11.                 if nums[j] < nums[i]:  # 关键1
  12.                     increase[i] = max(increase[i], increase[j] + 1)  # 关键2，+1 操作与自身赋值
  13.                     lis = max(lis, increase[i])
  14.                 if nums[j] > nums[i]:
  15.                     decrease[i] = max(decrease[i], decrease[j] + 1)  # 关键2，+1 操作与自身赋值
  16.                     lds = max(lds, decrease[i])
  17.         # 2. 回溯路径输出
  18.         def backtrace(idx: int, dp: List[List[int]], cmp: "Function(x, y)", path: List[int], res: List[List[int]]) -> None:
  19.             path.append(nums[idx])  # 选择状态
  20.             if dp[idx] == 1:  # 找到就终止！
  21.                 res.append(path[::-1])
  22.                 return True
  23.             for j in range(idx - 1, -1, -1):
  24.                 if dp[j] + 1 == dp[idx] and cmp(nums[j], nums[idx]):  # 倒推成立条件
  25.                     if backtrace(j, dp, cmp, path, res): return True
  26.             path.pop()  # 撤销状态
  28.         # 3. 遍历找到 LIS/LDS 结尾
  29.         LIS, LDS = [], []
  30.         for idx in range(n - 1, -1, -1):
  31.             if increase[idx] == lis and not LIS:
  32.                 backtrace(idx, increase, lambda x, y: x < y, [], LIS)
  33.             if decrease[idx] == lds and not LDS:
  34.                 backtrace(idx, decrease, lambda x, y: x > y, [], LDS)
  35.         return (LIS, LDS)
  37. # n = int(input())
  38. nums = list(map(int, input().split()))
  39. lis, lds = Solution().lengthOfLIS(nums)
  40. print(' '.join(str(num) for num in lis[0]))
  41. print(' '.join(str(num) for num in lds[0]))

测试用例：特别长，特别大！

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