2000 1000000 3
501 2999 2219 2658 1670 1654 761 2229 17 1823 688 1294 1770 1629 926 2734 281 451 1103 1885 994 969 8 1578 1233 332 986 599 1287 625 1362 856 105 1208 1976 2828 285 566 2793 2050 2910 846 107 2354 304 2839 2014 2560 127 1061 74 1886 1643 974 1735 436 2654 864 289 2572 111 2899 1188 654 2310 161 459 132 2452 2908 633 1182 1354 921 852 31 2026 582 1438 198 2975 1040 2934 1184 1326 1807 2482 1271 2628 2337 2904 2297 2544 934 1321 1868 213 1305 52 1723 1783 2237 1594 54 1513 2615 311 409 1787 1964 28 1039 1051 2772 339 885 575 1496 1903 79 2369 1913 387 252 199 1534 1970 2636 2121 2962 2426 295 1618 1952 713 101 177 1333 2611 971 527 461 1132 2905 2209 660 922 830 1424 1820 131 798 2556 1191 976 137 1777 1764 2340 579 1725 1981 768 248 1259 1865 2074 1054 679 69 21 1507 344 1909 2938 783 1774 379 2064 2022 987 1201 3000 1018 36 1577 2631 2406 819 2113 1309 12 1876 2806 742 2547 2399 1672 2296 848 619 672 342 73 2743 2205 977 803 1152 2078 2513 979 1883 1802 207 604 216 1532 1800 747 322 2346 1954 955 2309 2218 833 2468 2539 2546 2316 2527 858 2992 1755 816 1045 1501 873 166 1832 696 1606 2140 1298 1937 2357 2477 2012 1925 1175 272 2179 2178 376 1587 2829 1086 2656 1157 2130 2672 1808 206 309 2973 474 264 1724 528 719 990 646 800 1378 2889 2523 542 2322 965 1194 2028 154 2882 1690 88 1392 2991 1325 1720 1867 428 2098 2284 2363 1951 2963 2715 2398 851 1560 523 1166 1186 1656 834 381 1395 129 1095 41 1953 668 1386 588 1295 2522 283 1939 2626 1181 2496 100 755 869 2373 671 2580 2837 2293 2493 1442 1488 2263 804 2045 2370 1164 2458 2168 2884 2145 2355 2702 2042 241 754 2724 1048 1504 299 2330 263 20 749 1811 121 1174 2063 839 404 2417 870 1947 2838 227 972 2525 1261 2926 2105 204 2921 612 1986 1726 2821 243 170 2698 1454 1908 2252 981 1214 1738 305 2009 2590 2799 1742 1608 760 2002 1665 966 1660 2306 1829 1162 1781 2764 1434 2877 2473 1734 2794 9 1686 357 1625 909 297 1106 1081 1379 563 2711 847 1842 2492 11 2211 1990 781 722 2880 2553 1993 2169 2603 571 1494 1994 1248 1881 1763 1025 1280 2190 1197 1535 1498 218 2952 1828 2044 274 1567 1948 2647 1322 2795 430 1016 1628 1555 2747 547 532 1276 1084 2437 2868 793 2431 1205 1109 2372 811 2058 2576 1592 695 1693 1775 2651 1129 1024 2608 1431 620 2167 2574 2500 2701 365 2720 13 787 2639 2402 2447 959 1481 2475 1475 2865 924 1026 2213 2551 455 2646 2902 1215 1066 463 2825 2494 319 2571 2409 1894 1393 2072 900 48 2250 266 2844 2619 1626 138 2941 2288 2965 1980 2183 1368 293 512 347 2931 1041 1841 1746 246 1273 2299 1158 1500 2152 933 2936 1323 2429 1049 2021 2601 2392 762 1414 784 173 1839 1779 1429 1296 2041 1085 960 2419 827 774 2395 799 791 880 1788 2682 2204 1382 596 150 1053 329 2925 2465 2206 60 916 468 2859 1014 2052 1797 1114 1999 1260 2850 2080 601 195 113 2879 2504 2405 923 2861 340 1344 1461 192 1835 467 1712 2412 561 910 2207 2593 2347 493 2267 1324 2151 2782 397 1172 244 2866 1934 2420 2645 2729 32 868 2450 4 1478 901 2266 354 2643 1350 2575 992 1719 585 1397 661 2822 1563 683 265 491 1010 1671 1992 380 1751 142 1740 2732 536 1698 2736 1125 1750 2827 2086 1890 2239 1988 2111 1218 1792 1615 1400 1791 1749 416 97 1173 614 1090 1126 1701 399 637 673 1340 2922 815 1242 2434 482 1821 1926 276 2691 2788 627 2697 2404 2812 2117 425 453 1398 1065 1809 2214 338 2003 2472 2188 2269 535 980 298 2043 1484 225 947 1697 1710 1154 2947 2487 586 196 1887 1711 1057 835 120 2476 267 642 2323 193 841 290 2748 1112 1258 2335 126 2451 831 1929 133 229 2257 903 2722 22 556 1568 1122 2872 2037 1843 652 775 2342 1332 1558 1971 1017 40 1974 1064 239 2444 2008 2652 1275 544 1553 2088 1520 559 2988 2423 2294 57 1516 1556 1291 2614 2233 2367 1705 1590 2091 1640 1243 1849 71 1545 2543 2047 2808 1027 591 984 83 1571 1512 363 617 1002 766 1796 1931 1910 2124 1647 635 37 2595 104 2707 2133 505 658 2210 2913 47 2642 1752 2984 691 335 1528 1187 2978 769 2371 739 2995 1882 2745 2215 2436 983 1721 2339 2710 1029 2617 2798 182 911 2348 2360 1547 1108 118 1972 2583 369 2007 2858 802 2388 2862 1251 2548 1540 300 65 2136 1543 320 2629 2849 2304 541 611 1343 510 1598 1135 967 386 2131 1845 2708 1151 516 35 183 988 1636 1596 1855 821 2836 2244 2432 2291 486 1047 964 433 504 470 2508 242 163 184 2635 2930 2876 1100 1301 2739 2566 2453 1768 1793 1435 1914 790 2740 1339 1684 918 530 2313 551 838 1944 2638 2311 2510 1762 1185 569 367 1422 546 2024 2254 862 452 147 2733 616 2241 1732 168 1473 1530 488 1510 1904 1899 2384 1840 1949 33 382 2301 681 2055 2937 23 756 2445 2909 2222 1655 2236 2660 2801 366 2558 1714 2669 2953 2900 1765 2679 678 1178 2366 1761 2079 1957 2540 2716 701 931 2324 2741 279 2033 327 1080 717 1209 2433 2856 1092 324 1219 384 506 2103 1707 81 2232 1168 1399 2916 2712 777 1490 1896 1202 2609 2637 2919 2196 2051 1552 2143 1140 284 520 2194 1727 1247 214 343 1149 445 554 415 1377 2653 919 2857 2068 1492 2816 187 2379 275 2663 2584 1699 1898 1349 2251 670 515 1548 2386 667 2203 1892 1968 1897 522 2870 1102 685 2613 1743 2331 2032 1748 1799 1795 5 1819 1389 2200 1834 2848 1384 1036 2955 902 1441 639 1023 647 1439 898 2641 2929 2075 2881 1850 2673 1744 1639 1483 1612 1754 996 2106 68 1599 80 1358 1637 2217 889 110 2966 450 592 914 1031 165 2594 1133 1142 494 1055 1969 475 159 2573 497 1600 2089 2569 85 757 394 1652 280 2634 202 1857 2864 2092 1459 594 2192 2564 1426 233 2746 2753 2552 508 1319 2158 2990 2869 1872 2906 2238 2705 2440 2871 746 598 1263 2035 2132 1104 2197 1440 531 1288 2449 1292 1551 1345 2759 2792 1905 2958 1669 702 337 441 2107 2144 2226 94 2343 943 1252 2787 776 854 2479 56 2644 1884 818 49 1642 234 2731 2685 621 2303 2298 2462 141 2285 1503 1420 2666 181 1337 112 2786 1391 1479 117 1679 2605 2815 2667 1470 697 1304 2755 767 1317 2840 2997 1195 2577 500 2847 568 1531 84 125 1257 1508 2031 1134 2657 1624 217 2796 1581 653 509 407 2474 2260 2766 2557 1662 507 2749 1468 2314 2231 458 2802 2361 15 1228 1299 751 1078 1889 1866 1616 1515 2112 1675 476 431 628 805 1245 2173 738 842 389 1448 321 837 2625 529 24 1505 59 1097 1915 155 1562 346 2981 2633 2769 2442 764 1413 1088 690 2678 414 828 2101 1176 2756 593 2761 1676 99 466 143 443 2649 2888 1936 2592 2804 978 567 294 2408 2150 2067 796 61 2554 2312 2147 1217 832 2172 1255 1619 2752 944 224 175 314 810 2878 2730 2441 771 1348 2561 438 2612 1718 613 2771 296 396 1975 2455 2256 2789 2894 1989 2087 572 2129 871 2567 2235 449 876 2148 1703 418 2989 2338 426 1267 2538 1312 1423 2418 1369 2030 2587 2084 1437 135 2466 38 665 1207 1375 2076 1877 2391 1916 2935 1833 1019 2867 1474 606 2499 2831 2120 2927 692 169 534 1517 2017 465 167 1814 662 1022 2562 1805 1794 2128 1467 2886 1678 881 2240 312 1059 2570 626 689 1335 1246 2805 991 1220 1836 2728 1766 2703 2976 1179 1052 444 682 1035 1572 1213 812 545 1116 517 2940 2490 1950 920 2056 2389 2029 813 2784 2980 2563 603 1183 1658 1991 34 788 2114 2898 18 1069 1485 2160 1465 2456 664 373 1224 1585 1477 2695 1559 2352 1956 2438 1165 1401 1973 2599 865 231 2630 136 473 156 2589 1286 2824 1482 1315 1094 2424 2161 1314 2004 1285 728 1736 313 1 2376 2610 221 2775 872 829 212 2790 2318 875 867 185 2800 1502 1554 2262 2010 2333 371 288 718 1586 1681 2817 2968 2005 1430 2586 1278 1119 2036 2059 1696 27 2498 2895 91 1674 1418 2813 42 2110 2521 1412 1281 2957 306 1695 549 2478 2198 1708 2700 1371 1785 75 2461 2182 1753 282 2596 1170 1657 2164 222 2421 2943 2727 2709 1365 333 2512 1546 2852 1277 2735 2272 2616 1537 891 1812 950 364 1115 157 1680 2582 145 2176 1093 2083 2621 128 55 1410 1223 1583 1589 1079 2655 2640 1388 1633 1232 2719 2607 2738 2358 2832 2332 1455 712 615 2454 1611 16 1212 711 962 519 2125 383 2397 410 220 1682 2223 2515 203 2368 2102 2954 2289 2286 2623 2503 2279 1831 1244 1269 188 2300 2650 1623 1584 1274 605 286 2099 1072 63 1415 209 2400 2581 1928 1347 782 698 1918 859 2887 1161 114 643 1844 2777 2027 2485 2060 1405 2208 525 2351 1336 895 1499 930 485 583 2665 277 1709 1906 372 1856 1575 103 1731 2568 2923 1810 1861 2814 555 2048 1880 1352 434 1012 1070 2413 2830 2248 176 1302 1521 1256 1542 809 1747 840 2277 1837 2491 1544 1180 2274 2624 316 2526 1644 1667 861 153 2154 942 558 952 2699 2430 257 578 1060 189 2994 2901 2912 2283 2382 759 1630 1523 1068 1451 2915 245 2268 1250 1452 2109 1526 792 1009 849 2336 2725 1034 315 1942 460 524 2341 1463 2951 2243 2015 1390 1330 2767 1588 1539 1096 609 421 2726 1860 1673 2327 2295 786 1190 887 291 2134 576 2255 2470 1000 2535 385 1525 106 1270 1075 1021 631 448 1196 401 2993 2530 2598 502 1056 2874 1817 2073 268 424 1346 1159 178 1813 1822 2081 1524 1653 2781 1737 1007 2137 1858 985 2264 1144 345 857 124 194 2317 1574 1235 1216 87 1297 2983 2632 215 2163 70 1033 1632 162 2737 361 116 1595 748 1689 331 1306 1342 2834 308 368 1536 2181 2785 2533 402 1985 2221 1266 164 2282 2225 1284 1421 1569 2689 1824 499 1192 2094 2138 2191 1694 25 2917 158 1458 2851 1199 186 102 2860 2023 2261 1638 2459 1364 1472 1351 1893 240 1784 780 705 2142 2381 1427 888 2305 726 1003 1394 377 1668 211 2969 287 1226 693 1979 1411 2687 936 1941 423 1780 1940 2378 2165 1311 1293 261 172 1790 310 503 2585 457 348 1249 43 2662 2723 1111 1722 1042 1677 370 2891 2123 2115 676 1385 2977 2818 219 330 2680 1493 752 1107 2713 303 1564 694 2933 1649 1396 2960 2126 456 2362 1789 2949 1050 709 2956 939 1028 160 26 666 844 200 278 997 90 1403 260 2681 174 1221 2276 1237 2193 1704 2972