Big O Hacks

• Bubble Sort
• Merge Sort
• Insertion Sort
• Binary Search

Bubble Sort

import java.util.Arrays;
import java.util.Random;

public class BubbleSortAnalysis {
    // Generate an array of random numbers
    public static int[] generateRandomArray(int size) {
        int[] arr = new int[size];
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            arr[i] = random.nextInt();
        }
        return arr;
    }

    // Bubble Sort
    public static void analyzeBubbleSort(int[] arr) {
        int n = arr.length;
        int comparisons = 0;
        int swaps = 0;
        boolean swapped;
        double totalTime = 0.0;
        for (int k = 0; k < 12; k++) { // Run 12 times to get an average
            int[] copy = Arrays.copyOf(arr, arr.length); // Create a copy of the original array
            long startTime = System.nanoTime(); // Start time measurement
            for (int i = 0; i < n - 1; i++) {
                swapped = false;
                for (int j = 0; j < n - 1 - i; j++) {
                    comparisons++;
                    if (copy[j] > copy[j + 1]) {
                        swaps++;
                        int temp = copy[j];
                        copy[j] = copy[j + 1];
                        copy[j + 1] = temp;
                        swapped = true;
                    }
                }
                if (!swapped) {
                    break;
                }
            }
            long endTime = System.nanoTime(); // End time measurement
            double elapsedTime = (endTime - startTime) / 1_000_000.0; // Calculate elapsed time in milliseconds
            totalTime += elapsedTime;
        }
        double avgComparisons = comparisons / 12.0; // Calculate average number of comparisons
        double avgSwaps = swaps / 12.0; // Calculate average number of swaps
        double avgTime = totalTime / 12.0; // Calculate average time to sort
        System.out.println("Comparisons: " + avgComparisons);
        System.out.println("Swaps: " + avgSwaps);
        System.out.println("Time (ms): " + avgTime);
    }

    public static void main(String[] args) {
        int[] arr = generateRandomArray(5000); // Generate an array of 5000 random numbers

        System.out.println("Bubble Sort Analysis:");
        analyzeBubbleSort(arr);
    }
}

BubbleSortAnalysis.main(null);

Bubble Sort Analysis:
Comparisons: 1.2492649E7
Swaps: 6339734.0
Time (ms): 185.9393666666667

Merge Sort

import java.util.Arrays;
import java.util.Random;

public class MergeSortAnalysis {
    // Generate an array of random numbers
    public static int[] generateRandomArray(int size) {
        int[] arr = new int[size];
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            arr[i] = random.nextInt();
        }
        return arr;
    }

    // Merge Sort
    public static void mergeSort(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return;
        }
        int mid = n / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, n);
        mergeSort(left);
        mergeSort(right);
        merge(arr, left, right);
    }

    // Merge two sorted arrays
    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0;
        int j = 0;
        int k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }
        while (i < left.length) {
            arr[k++] = left[i++];
        }
        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = generateRandomArray(5000); // Generate an array of 5000 random numbers

        System.out.println("Merge Sort:");
        long startTime = System.nanoTime(); // Start time measurement
        mergeSort(arr);
        long endTime = System.nanoTime(); // End time measurement
        double elapsedTime = (endTime - startTime) / 1_000_000.0; // Calculate elapsed time in milliseconds

        System.out.println("Sorted Array: " + Arrays.toString(arr));
        System.out.println("Time (ms): " + elapsedTime);
    }
}

MergeSortAnalysis.main(null);

Merge Sort:
Sorted Array: [-2144478405, -2143970667, -2142652046, -2141287145, -2140412420, -2137416176, -2137166867, -2136219154, -2135729864, -2130327344, -2127403769, -2125664770, -2125323523, -2125150137, -2123877486, -2122633303, -2122578322, -2122548774, -2120738417, -2120715348, -2120308177, -2119706022, -2119671879, -2119103881, -2114833391, -2114678091, -2113719488, -2113117743, -2111600590, -2111467437, -2110484076, -2110394849, -2109903428, -2109797744, -2109785747, -2109582438, -2108930101, -2107970661, -2107962344, -2106521099, -2106380645, -2105314521, -2105240583, -2104913496, -2104608335, -2104385761, -2104053161, -2103257256, -2100938446, -2100525210, -2097172029, -2095521921, -2093634735, -2093401622, -2091157316, -2090185123, -2089809287, -2089031887, -2085722912, -2085368253, -2082760890, -2082428989, -2082036481, -2081706164, -2081201684, -2081129201, -2080483427, -2079198386, -2078150990, -2076316873, -2073734980, -2073104142, -2073094523, -2072025870, -2071575212, -2070518358, -2070146043, -2069542038, -2069278816, -2069183896, -2068474612, -2066910801, -2066627060, -2066382874, -2066058923, -2065666275, -2065240082, -2065197547, -2064867057, -2064521382, -2063557615, -2062549013, -2062269111, -2061775044, -2061138844, -2060583345, -2059732977, -2059658847, -2059284501, -2058325397, -2058254082, -2057808006, -2057781720, -2057762926, -2057354669, -2057265167, -2056910157, -2056906576, -2055200494, -2054810616, -2054718265, -2054509341, -2053428152, -2053174495, -2052419638, -2052313096, -2051664763, -2049891656, -2048980028, -2048875932, -2048866680, -2048515646, -2047212072, -2046880423, -2046824148, -2046339362, -2043099239, -2042914894, -2042281037, -2041234902, -2040292585, -2039819007, -2039552149, -2039091659, -2038117498, -2037641734, -2037292701, -2037268462, -2037195736, -2034422174, -2034066243, -2033443483, -2032892174, -2032597333, -2031674277, -2031665893, -2031345902, -2031293571, -2030897036, -2030680308, -2029042911, -2028948066, -2027013839, -2026676443, -2025794281, -2025637839, -2025479461, -2024856003, -2024383391, -2023621765, -2022265452, -2020656231, -2020025438, -2019904870, -2019628842, -2017859337, -2016780819, -2016502757, -2016431630, -2013413267, -2012924957, -2012919005, -2012291397, -2010765418, -2009930076, -2008722305, -2008451613, -2007626174, -2007320889, -2006953399, -2005218584, -2004869270, -2003332502, -2002616124, -2001846501, -1998219141, -1997403716, -1996259480, -1994493594, -1994042711, -1994022105, -1993565739, -1992872397, -1992711094, -1989051817, -1987659717, -1987479149, -1986421443, -1985531952, -1984874851, -1983641511, -1983609341, -1983247356, -1982251672, -1982081773, -1980225313, -1979788002, -1979453043, -1977067935, -1974476802, -1973440393, -1972136705, -1971752238, -1971610021, -1969663400, -1969615983, -1969345892, -1968576686, -1967588393, -1967335280, -1966244991, -1965777427, -1965201527, -1964933889, -1963912201, -1963513980, -1963505550, -1962643141, -1960807588, -1960408941, -1959802496, -1959567258, -1959354085, -1959273107, -1957992368, -1956795954, -1955771107, -1955227222, -1953798867, -1952871298, -1951902416, -1951160606, -1951043572, -1950032022, -1949910026, -1949060737, -1949037180, -1948581167, -1948542298, -1947937521, -1947545510, -1947092721, -1946631326, -1946239342, -1945520763, -1945448121, -1945174187, -1943998739, -1943949766, -1943370922, -1941645014, -1941286666, -1938275386, -1937781496, -1937658432, -1936951140, -1936506425, -1936049759, -1935404962, -1934627461, -1933487956, -1933365111, -1932778467, -1932725437, -1929956975, -1929898507, -1928534110, -1928047112, -1924764323, -1924554813, -1924196738, -1923672798, -1923448117, -1923257814, -1919878136, -1919325607, -1918187951, -1917123734, -1916777724, -1915992318, -1915576846, -1914060709, -1913894564, -1913649809, -1912690370, -1911239004, -1910876722, -1907390943, -1906923350, -1905793456, -1905670562, -1905527635, -1904860365, -1904682012, -1903732125, -1903011873, -1900984088, -1899129242, -1896293279, -1896177595, -1895134720, -1894745787, -1894631531, -1894515758, -1894223283, -1893218084, -1893160779, -1891048556, -1890855465, -1888539026, -1887628570, -1886909790, -1886846005, -1886275701, -1886098183, -1883744256, -1883590016, -1882770993, -1878666337, -1876238086, -1875987589, -1875897387, -1875706559, -1875418839, -1874857173, -1874771399, -1873920827, -1873707835, -1873420953, -1872565015, -1872375693, -1872119866, -1872043900, -1871970292, -1871911795, -1871830495, -1871543563, -1871461549, -1870643137, -1868815711, -1866125219, -1865663776, -1865465811, -1863839761, -1863582917, -1863242797, -1862379127, -1862138979, -1861528763, -1860571902, -1859111950, -1858767569, -1858005626, -1857815511, -1856744071, -1855957598, -1855194414, -1854533768, -1854410042, -1852785970, -1852100873, -1851293460, -1849613464, -1849039655, -1848917731, -1848642087, -1848220149, -1846118751, -1845262970, -1845055111, -1842541332, -1841599981, -1841515302, -1840489414, -1840188097, -1838372023, -1836631994, -1836451414, -1836262547, -1834218626, -1833455370, -1832118228, -1830949757, -1830401115, -1828388946, -1827353763, -1826866810, -1825390657, -1825142622, -1824951670, -1824123740, -1823476115, -1823308486, -1823198045, -1822857322, -1822256984, -1822211866, -1821857877, -1821316208, -1820933377, -1820781906, -1820662347, -1819727068, -1818635732, -1816067368, -1813699887, -1812296689, -1811125251, -1810956455, -1810898292, -1809156177, -1809124820, -1808968963, -1806463644, -1805889099, -1804399736, -1803139185, -1803137633, -1801805076, -1801599453, -1800842316, -1800790012, -1798768672, -1798056135, -1797992706, -1796064955, -1795865445, -1794916842, -1793235560, -1793030536, -1792425298, -1791758183, -1791691819, -1791466170, -1789845406, -1789596671, -1789394270, -1788446979, -1787959802, -1787365989, -1786767646, -1785033522, -1783459364, -1783114251, -1783051254, -1783021613, -1781970448, -1781294470, -1780324652, -1779240913, -1779218522, -1778647625, -1778188417, -1777322838, -1773215876, -1773106027, -1771640024, -1769428331, -1769250166, -1769059246, -1768308241, -1767460885, -1766533809, -1766468161, -1765193102, -1765104368, -1764344585, -1763765814, -1763650921, -1762726390, -1762636386, -1762265710, -1759634694, -1759334798, -1758831487, -1755947520, -1755216916, -1755205664, -1755188622, -1754439079, -1753671543, -1752967880, -1752929201, -1752001483, -1751436884, -1751191392, -1750022552, -1748821859, -1746724488, -1746305280, -1745702614, -1745044228, -1744804680, -1744802295, -1742469665, -1741231653, -1741138758, -1740542448, -1740270878, -1739496445, -1739215123, -1738946276, -1738397730, -1736716441, -1735428727, -1735140437, -1734686589, -1734523654, -1733459606, -1733085680, -1733062634, -1732097237, -1730630765, -1730199388, -1729285245, -1726971494, -1726626957, -1726555370, -1725667129, -1725640206, -1724632655, -1724199593, -1722969428, -1721606054, -1721304735, -1720526528, -1718874990, -1718226507, -1717909364, -1717865429, -1717763015, -1717224920, -1716937019, -1715775755, -1714898142, -1714560339, -1714520946, -1713635406, -1712690864, -1712409164, -1712124583, -1712071758, -1710097739, -1709975851, -1708541216, -1708290770, -1706518051, -1706019719, -1705466806, -1704126407, -1701301235, -1700588279, -1698893015, -1697590239, -1696280052, -1695774289, -1694743740, -1694280863, -1693687949, -1693523254, -1692682054, -1692279393, -1690439099, -1689722372, -1689561537, -1689265985, -1689260395, -1688602388, -1688295446, -1682627139, -1679020751, -1678822631, -1678734025, -1677656454, -1677051593, -1676417815, -1676271449, -1675019832, -1672951859, -1672781728, -1671359238, -1669533098, -1669434257, -1668904218, -1667974329, -1666857167, -1662879242, -1662149773, -1661169620, -1660372251, -1659255150, -1657887900, -1656331099, -1653435767, -1653089040, -1653073347, -1651877023, -1649677647, -1648688201, -1646170973, -1643468120, -1643219612, -1642650310, -1642054657, -1641975227, -1641604184, -1640571776, -1639610258, -1639161217, -1639129437, -1638902035, -1637871069, -1636663223, -1636662755, -1632590824, -1631580454, -1630876057, -1630395486, -1630013189, -1628330693, -1627965338, -1627412012, -1627229463, -1626785010, -1624356557, -1623847425, -1623336782, -1622289025, -1620543987, -1618798392, -1617198648, -1617172813, -1616720488, -1615365819, -1614463313, -1614457231, -1614241054, -1611997593, -1611591222, -1611211028, -1611007857, -1610148201, -1609905433, -1609190507, -1608539376, -1608290019, -1606752093, -1606690529, -1606285668, -1606167143, -1604665016, -1604345492, -1603408437, -1602001029, -1601803454, -1601057535, -1600228518, -1599409646, -1598959722, -1597695473, -1597575827, -1597232184, -1596893714, -1596087447, -1595651487, -1594745943, -1594300442, -1594217776, -1593321615, -1592603559, -1592493880, -1591032123, -1590549708, -1589013293, -1585673376, -1585509601, -1585148650, -1582260021, -1580680077, -1579364448, -1579285757, -1578594048, -1578522550, -1578132243, -1577866266, -1577341432, -1577285380, -1573614606, -1573151481, -1572697062, -1572445027, -1572413993, -1572243850, -1571947231, -1571641124, -1569782398, -1569728252, -1569363834, -1568778454, -1566448358, -1566385719, -1566151186, -1565968378, -1564837737, -1563910788, -1563066723, -1563057479, -1562801126, -1561922953, -1559383821, -1558701120, -1558645484, -1558367852, -1557372830, -1557058770, -1556435343, -1555739330, -1554864698, -1554427372, -1554099419, -1553591576, -1553108556, -1552884178, -1551667176, -1551131290, -1550490520, -1550334364, -1549955844, -1548565204, -1546786026, -1546636277, -1546174309, -1544090316, -1543300437, -1541541557, -1541452478, -1540957824, -1540614671, -1540495133, -1540358225, -1539073088, -1538749227, -1538553690, -1538269181, -1538258205, -1538245241, -1537692026, -1533671395, -1530517825, -1529729725, -1528851919, -1528332221, -1528308636, -1527523274, -1526896268, -1526355217, -1526258265, -1525413595, -1525279423, -1524910407, -1523942191, -1522846367, -1521854106, -1520480334, -1519695989, -1518449620, -1517927157, -1517589848, -1517437008, -1514043984, -1512173600, -1512070928, -1510399057, -1509897469, -1509831260, -1509336493, -1508510632, -1507456836, -1507129954, -1506910223, -1504822768, -1504318523, -1503360868, -1502845018, -1502040673, -1499721663, -1499077374, -1497983282, -1496296898, -1495969869, -1495269585, -1493919166, -1493764800, -1490266035, -1490116196, -1489712257, -1489266493, -1488947869, -1487757201, -1487700440, -1486947168, -1485609423, -1483857891, -1483785532, -1483783071, -1483073697, -1480490674, -1479378806, -1478898485, -1477398858, -1476438244, -1475659159, -1474494711, -1473556670, -1473243451, -1470577223, -1470437326, -1468875912, -1468501010, -1467909876, -1467876343, -1467310349, -1461807933, -1460204145, -1459999490, -1458278779, -1456315129, -1455753498, -1455743470, -1455415381, -1454362923, -1452440069, -1451064997, -1449713782, -1448054472, -1448044493, -1447954422, -1447941651, -1447758181, -1446267261, -1445542710, -1445124806, -1444970219, -1444489757, -1444368482, -1443301464, -1442568654, -1442132434, -1441777639, -1441165768, -1440962261, -1440773940, -1440737698, -1440716462, -1439897005, -1439339842, -1437879524, -1437459680, -1436943841, -1435587332, -1435479333, -1435298228, -1435004144, -1434201062, -1433943649, -1431931663, -1430082175, -1427355358, -1426691887, -1426274735, -1425387089, -1424523194, -1424251813, -1424091288, -1423103426, -1422914377, -1422794181, -1422792554, -1418779759, -1416870579, -1416607115, -1415666246, -1413698279, -1412067931, -1411756950, -1411734455, -1411123913, -1410820811, -1410383722, -1408131873, -1407822389, -1407102315, -1406753164, -1406308081, -1405566163, -1403412062, -1403072132, -1401889278, -1401441259, -1400563329, -1400058449, -1397180229, -1394695540, -1394269811, -1393988178, -1393409097, -1393031533, -1388701181, -1384165901, -1383797389, -1383599049, -1382317036, -1382295892, -1382218703, -1382125482, -1381245021, -1380998633, -1380977422, -1377670981, -1376274498, -1375318789, -1375288943, -1374698977, -1374233423, -1373890007, -1372686456, -1372568249, -1372306271, -1372158943, -1369358766, -1369200913, -1368438518, -1366634241, -1364135376, -1363736529, -1361238195, -1360339739, -1359033571, -1358631631, -1356289370, -1355802223, -1355377629, -1355006926, -1354135859, -1354049820, -1353851404, -1352790333, -1352321810, -1350370129, -1350074997, -1348569040, -1348310602, -1344562385, -1344364065, -1344109654, -1343895424, -1342995630, -1342373940, -1341865374, -1341125631, -1340052062, -1339556289, -1339421123, -1338817505, -1338418263, -1337381514, -1336086911, -1335755232, -1335458630, -1334249629, -1332455005, -1332289427, -1331922272, -1331889748, -1330293065, -1329857674, -1327237860, -1327156631, -1326505949, -1326104090, -1324314965, -1323621520, -1323170068, -1322720924, -1322382505, -1321670213, -1321566629, -1320251298, -1319232268, -1318190028, -1316815079, -1316742393, -1315561816, -1315131749, -1312363523, -1312015772, -1310585517, -1310429845, -1310025900, -1309655698, -1307607002, -1307114533, -1306915709, -1306354383, -1305900167, -1305472598, -1305305379, -1303605887, -1303424418, -1303403110, -1303124579, -1301397271, -1300159471, -1299639005, -1299248004, -1298548100, -1296856677, -1295969179, -1295092182, -1293922055, -1293460983, -1292358624, -1291801188, -1290825177, -1290746529, -1286842476, -1286127545, -1284859998, -1284170776, -1284148485, -1281849416, -1281805834, -1279414384, -1277656009, -1276300587, -1274332941, -1274131664, -1274026941, -1272561415, -1271397039, -1265849387, -1265689067, -1259085692, -1258565156, -1257892869, -1254664839, -1253223164, -1253211722, -1250966182, -1250745582, -1248353395, -1247800835, -1246805269, -1246797492, -1246446263, -1244793439, -1244315217, -1243116795, -1243043828, -1243013603, -1242193675, -1242150694, -1239958107, -1237720639, -1236963976, -1236934118, -1236706097, -1233558734, -1233450215, -1233345585, -1232800009, -1232511821, -1231137011, -1229934286, -1229049987, -1225722865, -1224896414, -1223084249, -1222783387, -1221365417, -1221209448, -1219481288, -1217877579, -1216200297, -1215979356, -1214269638, -1212666444, -1211892062, -1211659863, -1211243507, -1210579829, -1210229258, -1209611774, -1206446043, -1205715078, -1204768453, -1204101739, -1203903204, -1202043574, -1201106209, -1200454327, -1199900286, -1199197019, -1198273544, -1197583183, -1197041889, -1196692199, -1196489407, -1195173004, -1194789896, -1194752964, -1194321163, -1194289833, -1193510019, -1193298154, -1191068029, -1189802965, -1189696800, -1189533493, -1186694529, -1186285197, -1185612282, -1184273279, -1183687113, -1183628403, -1183158399, -1182288609, -1181383446, -1181319413, -1180581947, -1180362890, -1179118158, -1178596206, -1178216423, -1178052321, -1176271617, -1175271921, -1175142187, -1174667730, -1174282127, -1174142501, -1173560646, -1172979110, -1171743056, -1171590944, -1171575097, -1170174031, -1169716497, -1168051250, -1166946618, -1166935225, -1164067149, -1160737298, -1158847078, -1158721596, -1157808533, -1156970179, -1156907520, -1155572035, -1155558342, -1155548350, -1153931354, -1152408450, -1152331822, -1151040642, -1149842546, -1149043502, -1145846756, -1145639610, -1142811044, -1142479560, -1141715981, -1140960045, -1140542773, -1139567582, -1139244029, -1135385012, -1132163959, -1131623467, -1130901582, -1130669458, -1130628360, -1130497664, -1129448130, -1129259849, -1129009014, -1129005376, -1128747777, -1128354024, -1128171926, -1124309908, -1123868398, -1122425624, -1121389541, -1119367449, -1119202385, -1118417718, -1118158725, -1117367078, -1116753057, -1115355342, -1115087721, -1114634068, -1113654086, -1113624221, -1112009043, -1111772830, -1111608579, -1110528826, -1109257116, -1108930266, -1108847760, -1108021243, -1107789510, -1106206547, -1106049793, -1105242677, -1103130762, -1102795441, -1102733913, -1102518733, -1102111282, -1101881630, -1101672940, -1101341030, -1099477898, -1099322991, -1097611980, -1095508446, -1093193601, -1093144809, -1092737836, -1090206303, -1090091843, -1088181719, -1088079401, -1085804424, -1085257605, -1084086801, -1083982219, -1083298135, -1083240059, -1081444128, -1080589651, -1079716599, -1078466198, -1076420885, -1075956639, -1075559518, -1075435043, -1075030353, -1073278786, -1073187772, -1073146504, -1073034462, -1072477387, -1071850439, -1070914474, -1070037619, -1068919513, -1066442663, -1066298226, -1066217190, -1066153291, -1065404934, -1064548254, -1062979878, -1061494670, -1061426342, -1061208884, -1061137630, -1059789918, -1059287745, -1058829337, -1058604819, -1050878014, -1049655985, -1049423836, -1049231577, -1048479810, -1048456208, -1048318060, -1047487421, -1045835259, -1045566072, -1044740854, -1043194313, -1042612676, -1042578925, -1042182388, -1040561877, -1039813418, -1038584397, -1038007832, -1037863349, -1036959731, -1035279487, -1035047573, -1035027860, -1034589316, -1033793342, -1033570486, -1033067765, -1030877008, -1030800413, -1030553871, -1030394583, -1030254555, -1030082743, -1027142159, -1027009839, -1026870609, -1025470154, -1023264364, -1023060489, -1021623591, -1021546022, -1018416898, -1017115498, -1016261718, -1013794127, -1012819177, -1012011992, -1011752761, -1011553825, -1011438120, -1010048263, -1009943845, -1009767022, -1009681321, -1009338463, -1008713136, -1007881682, -1007827952, -1007745043, -1007412207, -1007009402, -1005758474, -1005375424, -1005210430, -1005007041, -1004788693, -1004727032, -1004135838, -1003521925, -1002798953, -1001166529, -1000462916, -998636993, -998324269, -997568616, -997150343, -994062282, -993819215, -993122455, -992389191, -991517302, -991368330, -991276059, -990838746, -990492988, -989734922, -989597251, -988385362, -988333814, -987629073, -987556028, -985500091, -982223510, -981799972, -981500219, -981284747, -979497050, -979112726, -978602298, -977884862, -977750913, -976017324, -975746899, -975335742, -974612413, -973927720, -973051671, -972409447, -970002104, -967809740, -966562652, -966498937, -966429829, -964892516, -964789346, -962210296, -959036669, -958661108, -957410782, -956719286, -955808574, -955519219, -955347648, -955163032, -952421132, -951059085, -950822971, -947959888, -947548588, -946593367, -945436981, -942517719, -940984028, -939867045, -939400523, -937206189, -935129122, -934400174, -934367712, -931296945, -929992246, -929227854, -928075330, -926240912, -926177067, -923610140, -923310102, -922946576, -922857602, -922637311, -922554414, -922045542, -920064635, -920031217, -919958444, -919873603, -919564691, -918254458, -918102982, -917415803, -917230859, -916064523, -915174411, -914655479, -913811018, -913659761, -913599852, -911944080, -911469424, -911356699, -909397024, -909229801, -908646934, -908361154, -908349334, -908150867, -907110757, -906079576, -904289249, -903876833, -903490155, -903444898, -903368129, -901689068, -899781617, -899572008, -899547604, -899504644, -899254413, -899017951, -897980376, -897890608, -896502196, -895499371, -894980805, -894349024, -894188158, -894116288, -893620453, -893461516, -892841564, -892666689, -891229767, -890414662, -889312818, -888620881, -888302016, -886510101, -886353016, -886097472, -886042689, -885570720, -885086726, -884634494, -883955831, -879007008, -877983853, -877516160, -877325230, -874914343, -873946136, -869265411, -868796023, -868738271, -868451004, -868014441, -867434795, -866917795, -866635948, -866438095, -863019643, -861995514, -861148398, -860244426, -859426542, -857549224, -856010413, -855187868, -854115726, -853966013, -853744548, -851859172, -850938119, -850153235, -849787464, -849192361, -848823173, -848182896, -848160122, -847473959, -847246082, -847031668, -844655282, -844095681, -843438918, -841657121, -841569021, -841322489, -840369908, -837919613, -836414313, -836205160, -836130522, -836114116, -834232664, -834189185, -833648087, -831490889, -830126081, -829692391, -828313890, -828295537, -827891037, -826426453, -826285367, -825778353, -823829240, -822135270, -821274066, -820618964, -820416270, -818777316, -818336827, -816688861, -816386012, -816016702, -815480550, -814888867, -808754160, -808468457, -808326921, -807247544, -807038155, -806448998, -805742811, -804794119, -804239428, -803322076, -802956492, -802488310, -801449348, -801181136, -800361321, -799847057, -799429524, -799381280, -799184567, -798767369, -797873047, -797229679, -797211853, -796522711, -793911212, -792788453, -788507075, -787982092, -787314205, -787259887, -786123332, -785916053, -785098733, -784998881, -782396211, -779984632, -779026774, -777921068, -776029329, -775662592, -774785767, -773769784, -773759679, -772692264, -772419848, -771109183, -769910090, -769564300, -768355770, -768324006, -767850720, -767686003, -766557079, -765990997, -761925837, -761297583, -760996836, -758560990, -756107412, -756018216, -754969551, -754179755, -752438756, -751477338, -750982113, -750935080, -749317190, -748775691, -748604123, -747734277, -746926049, -746440785, -745310171, -742065880, -740049170, -739245881, -738768239, -738340052, -738323482, -738017931, -736443240, -735859007, -735021834, -734557398, -734057836, -733409307, -733024488, -732877413, -732523175, -731470188, -731288587, -731132290, -729127960, -727089124, -727035658, -724999588, -724829814, -723354340, -723209643, -722987622, -722937993, -722452460, -722187187, -722122847, -720792281, -720742112, -719165390, -716916039, -716237216, -716000059, -715735628, -715239311, -715092275, -714181143, -712137254, -711762861, -711577050, -711223932, -709638407, -709383572, -707924812, -707523532, -706836720, -706270564, -705640277, -705400198, -705344471, -704929482, -701876613, -701575618, -700519515, -698553142, -697728141, -696057759, -694697826, -694137044, -694003890, -692489369, -692257822, -690962788, -690801285, -690052630, -688148168, -686832237, -685949699, -685890398, -684776570, -683768112, -683688237, -683659443, -682510832, -681816522, -681142206, -678709523, -676818168, -674996837, -674924215, -674019697, -674001783, -673363610, -673058881, -671873365, -671099989, -666891443, -666158465, -666090302, -665526488, -663276694, -662422662, -661959866, -661507726, -661000979, -660943955, -660031244, -659955249, -659642829, -659358982, -659149406, -658371594, -657972028, -657300343, -656754028, -655986870, -655219648, -655188551, -654948272, -654621087, -654286245, -654234643, -652134487, -650637283, -648079208, -647141224, -645893560, -645862400, -645816680, -643249083, -640748370, -640462561, -640120067, -639070628, -638632130, -638373539, -637905415, -637821659, -637701040, -636639929, -635853972, -635375698, -634788125, -633906073, -633284606, -633253188, -631588829, -631491039, -629323955, -628992938, -628275758, -627199443, -627040510, -626468668, -626250228, -626234213, -625304744, -624738884, -623916305, -622956219, -622228606, -621879036, -621782208, -620835651, -620544686, -619035567, -616659677, -616266732, -615902924, -615327905, -614978760, -611289953, -609960145, -608802155, -608568735, -607648041, -607554973, -605307360, -603669175, -603258366, -600498893, -599488131, -599385165, -598402862, -596782578, -595606831, -595207520, -594224434, -594024339, -593969172, -591962127, -591831019, -590772561, -590012029, -589984783, -589422279, -587832652, -587746019, -586268637, -586157360, -585633263, -582096369, -580825916, -580569041, -580527951, -580125416, -576609480, -576414491, -576289646, -575583780, -574884443, -574298960, -569372313, -568488350, -567873596, -567615425, -567589101, -567572761, -566920558, -566106962, -565929655, -564521983, -563769797, -563392690, -561868098, -560837018, -560784577, -560415567, -560280518, -559731453, -559006557, -558654903, -557888694, -557142237, -553673338, -551785307, -549980835, -549917716, -549715662, -549702113, -547465269, -547388034, -545856355, -545153029, -545097426, -544722011, -542962325, -542628476, -542147001, -540556121, -539690892, -538143208, -537922747, -537183480, -536931877, -536904211, -536835104, -536126074, -535284743, -534037261, -533252319, -531519265, -531251672, -529103463, -527893661, -527125345, -525496732, -525032277, -524629620, -524499334, -523580817, -523334893, -522134252, -518523295, -517786828, -517646312, -516808814, -515524613, -514629680, -513054619, -510657864, -510045697, -508834104, -508492990, -508224568, -508108024, -505162473, -504821321, -504577348, -503007431, -500211922, -500175574, -500028662, -499069539, -498695334, -497884414, -496933511, -496367058, -496121724, -495942242, -495624091, -495355964, -493986646, -492275022, -491649294, -491251588, -488391747, -487814803, -486944057, -486304859, -484999263, -484606957, -484248301, -482118013, -481698806, -480668479, -479560524, -479099707, -477510456, -474663716, -474445278, -473381415, -470510281, -470208663, -469770348, -469356279, -465830078, -465063873, -464705550, -464430645, -464415871, -463975620, -463037877, -462561036, -461569149, -461533612, -460361323, -460289450, -459782601, -457938062, -456920205, -456635749, -456105126, -455804096, -455423800, -454034743, -453403751, -452942862, -452746841, -452723363, -449264954, -448390938, -448327815, -447596182, -445101717, -444597598, -443984188, -443346289, -442698402, -441908705, -440150820, -440144247, -440009583, -439527627, -438318633, -438247845, -435046813, -434562289, -433333428, -433326409, -433098385, -431944257, -429567833, -425541024, -425052761, -425022048, -424721143, -421773938, -419716175, -419593579, -419574883, -419270051, -419010435, -418000346, -417436684, -417365689, -417291875, -416735430, -416688205, -416133281, -415029764, -414948168, -414039368, -413457609, -412399180, -411772332, -411625853, -411243504, -410182467, -410170537, -410087654, -409938405, -409799319, -409583693, -409037882, -408360384, -407428605, -406414344, -406066726, -405211366, -404417602, -404406921, -404341218, -402063193, -401046378, -400536771, -400242520, -400056456, -398983464, -398531378, -396889767, -395063377, -394853827, -394111745, -394034914, -393970809, -393906188, -393122253, -392426453, -392341627, -391745767, -390480839, -390465918, -387576499, -385710013, -385350223, -385202196, -384699633, -384351649, -383362676, -382640881, -380206033, -378520510, -377408685, -377166670, -377100673, -376816730, -375375102, -374676930, -374309783, -373516208, -372619777, -371839139, -370934821, -369229440, -368926710, -368404751, -364832222, -364535076, -361739324, -361390028, -358361292, -358199956, -357847321, -356425591, -356394949, -355979285, -353537121, -352476609, -349810354, -347494752, -347431235, -346987711, -345972229, -345865546, -344890244, -344842307, -343966134, -340121735, -339070147, -338218858, -337953987, -337880318, -337829427, -337444738, -337421474, -336691323, -335329578, -334591099, -334123018, -334119131, -333578619, -333520422, -333362578, -332753325, -332436850, -332389505, -332344596, -329809725, -329000844, -325834944, -325743517, -325680793, -325192117, -324939869, -323964041, -322864463, -322353020, -320447853, -317981150, -317627917, -317524113, -317353129, -316584404, -316024206, -315493427, -314445697, -313623147, -312837641, -312827594, -312780286, -312550713, -311968899, -311210733, -311060279, -309875004, -309106998, -309042219, -308594781, -307714972, -307246864, -306392211, -306121718, -305325851, -304917953, -304663982, -304590019, -303883303, -302951345, -302259440, -301121686, -301031737, -300881408, -298915824, -298388656, -298375290, -298212347, -298104932, -296846591, -296729074, -295672272, -294891645, -294615998, -293916890, -293604678, -292798995, -291618950, -288621272, -285870148, -285371091, -283005512, -278702437, -278700408, -278290116, -278104701, -276577310, -276242844, -274573296, -274286461, -273697609, -273041847, -271902438, -271674086, -270232329, -270158011, -269746964, -269555632, -269544922, -269145319, -268387661, -268273938, -268107938, -267919890, -267761534, -266693523, -265690636, -265406615, -265066571, -264918004, -263873892, -261384948, -260009078, -258848883, -258693623, -258023568, -257435548, -256356679, -256111277, -256035853, -256021608, -255844921, -255681006, -254778838, -254707228, -253719551, -252593372, -250644829, -250511021, -249965504, -249503760, -249174503, -248619359, -247587374, -244368858, -242388902, -239984966, -239965753, -239539516, -236238036, -235489061, -235417527, -235239596, -235003483, -229835541, -229594478, -229447436, -226660193, -225684090, -224324267, -223979042, -223472356, -223466309, -222683303, -221551072, -219659706, -218942970, -218530398, -218525163, -217549446, -217191767, -216945182, -216694698, -214953649, -214217279, -212658860, -212597656, -211804241, -211767447, -211694715, -209857572, -209616353, -209411738, -207735361, -205706965, -203016885, -202071667, -197644109, -197383311, -196123027, -195867701, -195691414, -195278636, -194998379, -194754707, -193533962, -193039383, -192595200, -192218853, -189363471, -188184470, -186940136, -186692882, -186362146, -185904110, -183816991, -183311834, -183297582, -178853159, -178617160, -177854065, -177278147, -176871900, -176144046, -175508106, -175433021, -175296243, -174885568, -174864737, -174822800, -173797017, -173523068, -173080787, -172247095, -172053650, -171717262, -169405165, -167715894, -166499276, -166220428, -166201139, -165743676, -164737358, -163969048, -162500554, -160997524, -160146101, -160109043, -158990674, -158967297, -157889160, -157861585, -157500770, -157364156, -155317867, -153320896, -152840906, -152240884, -151836063, -151510326, -150918249, -150699589, -150063070, -150034016, -149803841, -148630479, -148082087, -147488207, -146977572, -146922265, -146275483, -145991019, -144402385, -142897725, -140773936, -138543366, -136696447, -135705065, -135328755, -135025583, -134409699, -131831144, -131060115, -130252726, -127776606, -127411945, -127202752, -126945735, -126223972, -125493121, -124424553, -123150769, -120790513, -119278735, -119056574, -118801299, -112796781, -112251376, -111855886, -110930313, -110759648, -109403680, -109124824, -108566009, -108174257, -107677379, -107196060, -107018363, -106107964, -105439569, -105089955, -105084622, -103624088, -102187431, -101949096, -101233646, -101203637, -101091351, -100759520, -100687748, -100428303, -100353245, -100231855, -100228881, -98763426, -97100456, -96479608, -96256891, -95832604, -95729766, -94636345, -94441552, -94415089, -94150226, -93581582, -92833937, -92425949, -90333088, -89556626, -89457904, -88678974, -87867385, -87577897, -87350592, -85912670, -85364479, -85288839, -85140116, -84986118, -83039035, -82364326, -80003334, -77804289, -77761942, -77454092, -76654630, -76464107, -75665956, -75647671, -74873093, -74542290, -73964311, -72959374, -72368898, -72241075, -69685092, -65792147, -64811375, -64440142, -62867851, -62646248, -58369323, -57665521, -57644288, -56646314, -52841799, -52394689, -50969513, -50958322, -50759871, -48592550, -47706256, -47497023, -47263238, -46648476, -45996293, -45938839, -44197593, -43392614, -43077363, -42927038, -41852943, -41641032, -40645829, -39932770, -39581664, -38692872, -37402493, -35079163, -34773487, -34081500, -33784564, -33372973, -32591977, -31661779, -31199613, -30111868, -29281088, -28953885, -28499583, -27966672, -27360062, -26688249, -26282043, -24822653, -24454324, -24302052, -24102298, -23848991, -23783221, -20277324, -18886457, -17965594, -17824218, -16509467, -10636811, -10423343, -9695900, -8039804, -7586347, -4481391, -4202267, -2691398, -546994, 3337076, 3596768, 4782626, 5794381, 6085500, 7065197, 7950107, 10413587, 13931225, 15555864, 16666971, 18279865, 18723535, 19521776, 19582433, 20168963, 21310185, 21898349, 22808747, 22864249, 23595169, 25979218, 26355897, 26656599, 28318590, 28517650, 29640077, 30654169, 31650188, 32394228, 34041071, 36471897, 36769478, 37394788, 38962230, 39289201, 39839963, 40144867, 40761440, 42722637, 42860044, 43125323, 43130372, 43666394, 44852527, 46858336, 47542601, 47778680, 48141871, 48723011, 49033591, 49539001, 49620846, 50631545, 50652662, 51479395, 51565092, 55590280, 57069756, 58534341, 58711866, 59227350, 61510369, 61827771, 62728725, 63013043, 64638484, 65564522, 67627230, 68424750, 69230343, 69704457, 69817271, 72420168, 73546215, 74075782, 75375715, 75443058, 75714487, 76077753, 76280539, 77298137, 77723187, 79056340, 80240964, 82543644, 83065824, 83949207, 84518384, 84706754, 86714795, 87448695, 88614277, 89687286, 91275320, 91853090, 92192331, 92703444, 93082144, 94303187, 94377259, 94709069, 96589207, 97454129, 98713546, 98724711, 99613601, 100859339, 100903591, 101474729, 101528104, 103029879, 103268477, 104508811, 104642231, 104710174, 105432597, 107839929, 108588316, 109782653, 110002811, 110266865, 110719025, 111287858, 112981851, 113860104, 114231433, 114770350, 114794654, 116442893, 116457256, 118228225, 118756461, 119986929, 119993545, 120708273, 121775514, 122719852, 123236577, 124106195, 126009937, 127072483, 129455734, 130240455, 130582607, 131291863, 131364745, 132589906, 132618155, 133674840, 134272789, 135209121, 135394486, 135832346, 136096468, 136184247, 138444932, 139727619, 140403685, 140466667, 141549439, 141794980, 142123060, 144028465, 145323419, 146267069, 148153718, 148220128, 149063095, 151925911, 153952470, 154214423, 154483453, 155564667, 156902277, 157929639, 160350646, 161066229, 162823705, 163728668, 164514249, 165141449, 166691386, 168033879, 168849123, 169016523, 169635407, 170513452, 170697925, 170800767, 173095147, 173335163, 174366100, 175070434, 176060078, 176121131, 177915490, 178161985, 178417094, 179588950, 179647929, 179680658, 179847323, 180000350, 180007131, 181007709, 181419728, 181481687, 182987681, 183385663, 183874186, 184040069, 187107810, 187611073, 188070230, 188091773, 188360290, 188948834, 189435530, 190135146, 190547355, 191107183, 191183733, 193666797, 193670849, 195408025, 196036218, 196097562, 196282954, 196322701, 196831379, 197760912, 198650348, 198720105, 198726370, 199233643, 201549050, 203182660, 204033504, 206566518, 206569666, 206787192, 207001860, 207746008, 208279866, 208513874, 208548337, 208641037, 208996661, 209043178, 211768657, 213894730, 214128994, 214442033, 215228309, 216003216, 218277872, 218494642, 219688976, 221013416, 222605586, 222657936, 222906675, 223705755, 225046421, 225645903, 227142343, 228422067, 229728902, 230601827, 230784568, 231019909, 231582711, 231728680, 233608506, 235367685, 236750812, 237165546, 237692820, 239253192, 240235085, 241321303, 241737864, 241920181, 242051868, 242408725, 243138847, 243659378, 245383177, 246067851, 246595036, 248817580, 249566436, 250204954, 251022659, 252287726, 253008120, 253035086, 253704972, 253799540, 255869923, 255892652, 255985741, 256663985, 257324224, 257510872, 258727607, 259888562, 260150160, 260158859, 260437441, 262333800, 264456673, 266955132, 267047191, 267563290, 269012248, 269543509, 269686034, 271604772, 272900177, 273499986, 273912351, 273962974, 275427288, 276124291, 277483234, 279996630, 280326565, 282107190, 282713826, 286026825, 286391751, 286964857, 287492099, 287998650, 289357573, 291288347, 292204680, 292547138, 295340277, 295774522, 296477531, 298590725, 299543812, 301267503, 303058030, 303687464, 304193572, 305413004, 306233738, 306902924, 307456560, 308256864, 309432376, 309841924, 309960998, 310073850, 311541985, 312448370, 312803024, 313539159, 314265350, 314450408, 314774242, 314802259, 315342983, 315944759, 316266347, 317572628, 320192066, 320290546, 321472574, 323952965, 325353764, 326373218, 328122763, 328506591, 329637291, 332310372, 332744192, 332909806, 336275794, 338803350, 339041117, 339413813, 340826565, 341065408, 341575043, 341976222, 344079880, 345825115, 347201183, 348007201, 348161625, 349071969, 349618262, 350221906, 350614540, 351063549, 351846640, 352467980, 352673876, 352975680, 353646406, 355737210, 356047631, 357034155, 357054060, 357116865, 359836559, 360087050, 361164191, 361866396, 364235548, 366235398, 366237020, 368598250, 368803757, 369132241, 369470390, 370178411, 370997144, 371169773, 371785040, 372141731, 372946241, 373123243, 373772600, 375302730, 375308312, 375709695, 376180193, 376941131, 377118669, 378259549, 378406136, 378591759, 379872959, 380510450, 382458247, 384353877, 386541271, 386616496, 388512407, 388602939, 389006554, 389665942, 390285413, 390572623, 391592012, 392038406, 393483066, 393627589, 393774921, 394703943, 394821468, 395179787, 395371751, 396139335, 396905968, 398944059, 399361237, 400752947, 401306009, 401704306, 401766308, 402923497, 403369580, 404413537, 405112475, 405286524, 405427417, 407131312, 407145316, 407567301, 407869061, 408141224, 410318603, 411971603, 414193780, 414250529, 416653949, 416689433, 419304700, 419921814, 420486271, 421987506, 422071650, 422167039, 422213010, 423774381, 424382250, 424711816, 425421764, 425701395, 425766872, 427393413, 427541930, 429825738, 429931373, 431014628, 431891738, 433117619, 433531640, 435129894, 439172627, 439762200, 440773309, 441039740, 441121896, 441896594, 442719668, 442887495, 443033829, 444884503, 448288570, 449637082, 449969905, 451965645, 452787116, 452847517, 453026107, 453431663, 455523665, 457648886, 457749506, 458685563, 459979230, 461884864, 462031986, 462758026, 464158687, 464539823, 464996617, 465330525, 465607849, 466538482, 466673725, 466965377, 467309277, 467649755, 469846392, 471753434, 472287236, 474016974, 474029375, 474895357, 476945450, 477836271, 478040828, 478210287, 478220418, 479564480, 481710051, 482248395, 483028022, 483631837, 483873813, 486765491, 486768349, 487564873, 487632857, 487781041, 489090673, 489128827, 489405714, 489645868, 490861912, 491518283, 493206985, 493419785, 494389458, 495058623, 495171694, 496950461, 497152822, 497680872, 498435882, 499167001, 500812166, 501769344, 502907865, 505365093, 505897015, 506638198, 507000885, 509297208, 510206082, 513250493, 516705734, 516819798, 518177398, 518837691, 518924560, 520637648, 521322802, 522501081, 522641053, 522881741, 523526833, 526079305, 526966991, 527432790, 527746627, 528879749, 529332495, 532839236, 532841289, 533977773, 534105787, 535301095, 537410072, 537699745, 539482392, 540065295, 540460046, 541176532, 541471751, 541965668, 544143338, 544767325, 547173982, 548080962, 548289577, 549075413, 556221164, 556575159, 557917336, 558504976, 559219927, 559391508, 559451797, 559696643, 560911110, 562276751, 564046020, 564852730, 565031194, 565794116, 566000320, 566230929, 567349579, 567496091, 567705147, 569973340, 570328001, 570502496, 570987425, 573624446, 574795917, 575003248, 577081143, 577912882, 579426321, 579925160, 581847743, 582115707, 583020790, 583761530, 584500889, 584816584, 585411039, 585488976, 587272874, 588764957, 589642707, 590668434, 590819685, 591905861, 592607708, 594069109, 594576284, 594638515, 594863111, 595877520, 596908102, 597404877, 597443670, 597621546, 597985603, 598227889, 599096124, 599422941, 599626540, 600485069, 600501017, 600986864, 601827127, 602047002, 602647518, 603257768, 603559626, 605121050, 605245388, 606590593, 607721692, 609090426, 609327746, 609516872, 609943434, 610078889, 610809497, 611803494, 611806096, 612423661, 614798730, 614802993, 615019248, 618225899, 619704418, 622043591, 623256837, 623633802, 624771327, 626021988, 626141384, 626473303, 626622463, 626891432, 626930330, 629119767, 630667525, 632158419, 632595195, 632815409, 632918297, 633668293, 634259598, 636136316, 636809681, 637694393, 639401621, 640268588, 641809423, 643600125, 643978482, 644357706, 645331363, 646571639, 647267785, 647404972, 647914086, 648121025, 651439333, 652278646, 653247618, 653325182, 654440138, 654697114, 655549007, 656145045, 657531008, 658381747, 659693860, 661877244, 661897342, 661967125, 663412119, 663533627, 664476993, 664523030, 666946265, 668838817, 669141292, 669278700, 670273060, 670820429, 674233272, 676820268, 677454234, 678037396, 680547473, 681082353, 681280341, 682224833, 683751536, 686387548, 686568329, 687088242, 687946880, 690691903, 691031351, 691117673, 691176144, 692192545, 692440019, 692797832, 693017071, 694409524, 695288733, 695668479, 697938905, 698839323, 699218415, 699429744, 700651647, 702591972, 703276022, 703733379, 704037854, 705756635, 706395342, 706408661, 706757305, 707791055, 708047583, 708115617, 708710007, 709560025, 709994140, 710861292, 712314935, 713754373, 713877499, 716038005, 716961071, 723015854, 724145919, 724417549, 725553236, 725607314, 726715110, 727169590, 728898566, 730179365, 731794579, 733031540, 733803308, 735722141, 736233353, 736378967, 736783885, 737818938, 738066770, 739879561, 740547140, 742505705, 745671468, 745860505, 747061715, 748122481, 750486139, 751615659, 752035829, 752460018, 753610797, 753625238, 754058180, 754153020, 757310011, 758020447, 758083566, 758237441, 759892776, 760012339, 760967077, 763709448, 764707959, 765045664, 765225461, 767287513, 767379183, 768272853, 768505145, 768546904, 768644640, 768912704, 768930984, 769154157, 769235291, 769256748, 769898850, 772199686, 772812447, 774300126, 774585168, 775034329, 775997340, 776063149, 777502199, 779060498, 779478789, 780621324, 784384785, 784456357, 786330425, 786552637, 787009419, 787849640, 789863436, 790425350, 791050798, 791749135, 793381164, 795905849, 796269926, 796384645, 796994018, 797864101, 798273007, 798777942, 799804757, 801203973, 801783768, 801990863, 806145168, 806475910, 809577966, 809847435, 809938985, 810538783, 810753905, 810979840, 811384661, 812019842, 812792311, 812808593, 813915647, 814640113, 814985397, 817307321, 818126541, 821391137, 821527204, 821780151, 822610156, 822716425, 823898430, 825227248, 825845854, 826202836, 829426855, 829492730, 831734073, 832377593, 833767989, 834834414, 835966494, 835990006, 836049898, 837081450, 837529559, 838709115, 840134381, 840463460, 841111107, 842027285, 842921170, 843370430, 843979871, 846376730, 847116907, 847240551, 847846693, 849624540, 849817388, 851958313, 852286374, 852792629, 855470337, 856118976, 856864375, 857156532, 857821385, 858731371, 859050321, 859187000, 861366505, 861599643, 861939466, 863635336, 863919294, 864529121, 864831852, 865420642, 865920032, 866859272, 866998648, 867007697, 867783578, 868373542, 869507753, 870909967, 872493141, 873317625, 873839145, 873924297, 874096151, 874523788, 875156989, 878712620, 879758703, 881139826, 881828742, 881831859, 882270373, 885611307, 885672614, 886448347, 887190311, 887511314, 887707493, 889618967, 889715203, 890310799, 890814633, 890950955, 891696371, 891885126, 892153934, 893078807, 894155166, 894311975, 894638777, 895234014, 896031547, 896845467, 896875539, 896979096, 897661222, 898268455, 899077244, 899640481, 900045409, 903743392, 903968234, 904166895, 905004025, 905476285, 905733633, 906787107, 907545454, 908280162, 908865989, 909375698, 909633577, 909762305, 911425956, 913244670, 913363888, 913637552, 914327436, 915010078, 915859900, 916355044, 916836099, 917263100, 917680060, 917737912, 917980053, 920126018, 922131770, 922176505, 922708665, 923948712, 924136315, 924202525, 924397924, 925852769, 929526463, 930456574, 930474648, 931012913, 933631490, 934623052, 935020191, 935571614, 935629042, 937452627, 937542390, 942179422, 942994656, 944008875, 944885568, 945064423, 946189563, 946338790, 946749893, 947904813, 947965651, 949882057, 950117950, 951555678, 952333455, 953145822, 953731380, 954132867, 954462163, 955256165, 956670365, 956956794, 956989825, 958045158, 958467880, 958528727, 960415217, 961238665, 962687421, 964137815, 964392080, 964506022, 964806264, 964868652, 965353004, 965497322, 967487867, 968003414, 968161489, 969463801, 970431913, 970812362, 971884858, 972041608, 972672867, 975286872, 976172180, 976767069, 976893994, 976974057, 977116191, 977508654, 977805165, 978457417, 978634724, 978997349, 980652411, 982424309, 984986703, 985280711, 985647370, 987114902, 987461992, 987655825, 989862245, 990103082, 991239590, 992554853, 993103590, 993230134, 993505206, 995440760, 995796407, 996175698, 997022277, 998891316, 999125897, 999197551, 1002289333, 1002702347, 1003183815, 1004633327, 1006173798, 1006520170, 1008321402, 1008924057, 1009317310, 1009635766, 1010745452, 1011248116, 1012756682, 1013422558, 1013840044, 1014019614, 1015150513, 1016448988, 1016460534, 1016858745, 1017363750, 1018021532, 1018048794, 1021008954, 1021305250, 1021441942, 1021505771, 1021811293, 1021923604, 1022995625, 1022999206, 1023561645, 1023800416, 1023878912, 1023917511, 1026780480, 1028467316, 1029285818, 1029424418, 1030225751, 1031150097, 1031169889, 1032099962, 1033197044, 1033750923, 1033962813, 1034156920, 1034574877, 1034749441, 1036812860, 1036842098, 1039167319, 1039440422, 1045889674, 1045917718, 1046980656, 1047854966, 1048346391, 1048386143, 1048524453, 1049304489, 1050457728, 1052918660, 1053333603, 1054513198, 1055924037, 1056221097, 1056793901, 1056899119, 1057775250, 1058616140, 1060074254, 1061056644, 1061147106, 1063606436, 1063779260, 1065160705, 1066380735, 1067296717, 1067376009, 1070820822, 1071318904, 1071641462, 1071811385, 1072221720, 1072397945, 1073941925, 1075063377, 1077722391, 1078886572, 1079122298, 1079546490, 1079968110, 1080073385, 1081811046, 1081856689, 1082046456, 1082069528, 1082365242, 1083114765, 1083473392, 1083873742, 1084235609, 1084757426, 1085163390, 1086007634, 1086471847, 1086589487, 1088318146, 1088534306, 1089319580, 1089834909, 1090972260, 1091210883, 1093193671, 1094330975, 1094706185, 1094779794, 1097391916, 1098365067, 1099395072, 1099492742, 1099847095, 1100704618, 1101018182, 1101560586, 1102499171, 1103484254, 1103724247, 1104433356, 1105348713, 1106249184, 1106366299, 1106791481, 1108045598, 1108381916, 1108917553, 1109678485, 1110015458, 1110318115, 1111916769, 1112102167, 1112541657, 1113402448, 1118271160, 1119116498, 1119383467, 1119608805, 1119783905, 1122053475, 1122941073, 1124356736, 1125288213, 1125839692, 1128405308, 1128680758, 1128733227, 1129059345, 1129737835, 1129867477, 1131069027, 1131188069, 1133777677, 1134038557, 1135022321, 1136208557, 1136235826, 1136256481, 1139193493, 1139871847, 1140768369, 1142788688, 1142805990, 1144554909, 1147812551, 1148450933, 1149006171, 1149049659, 1149811839, 1150266368, 1150373604, 1150986430, 1151157332, 1153636842, 1154436809, 1155177098, 1155320033, 1155585893, 1155812118, 1156127447, 1157149988, 1157278795, 1157876533, 1158125116, 1159325293, 1161606217, 1162459933, 1164070552, 1164440571, 1165393296, 1165699727, 1166328685, 1167318470, 1167835196, 1168290893, 1168852307, 1169674350, 1170793911, 1174249494, 1174789653, 1174913786, 1175406184, 1176056357, 1177263704, 1179674013, 1180773166, 1180911354, 1181222159, 1183411323, 1184159100, 1184293496, 1184367584, 1187954042, 1188265472, 1188373674, 1191179153, 1192501342, 1192511041, 1194296413, 1194916929, 1195384347, 1195585848, 1197211335, 1198482606, 1200168571, 1200777114, 1200926690, 1205478577, 1206382578, 1209073913, 1210495844, 1211651819, 1212595423, 1214403010, 1214724350, 1215354595, 1215791196, 1216995142, 1217270263, 1220168404, 1220299321, 1220627774, 1221813751, 1222372538, 1225532806, 1225987281, 1226075457, 1226362823, 1226420377, 1228931917, 1230415736, 1230421084, 1230693436, 1231406776, 1232464262, 1233916540, 1234271805, 1234454149, 1234921731, 1236027861, 1236964077, 1237021129, 1237713958, 1238460564, 1238749119, 1239298103, 1240978253, 1241109393, 1241639605, 1245457678, 1245714953, 1246160561, 1246915519, 1247741603, 1249304071, 1249861166, 1252506131, 1257483967, 1257825747, 1259711256, 1260356892, 1262950127, 1267010267, 1267076715, 1267650359, 1268759752, 1270065601, 1270402862, 1270992356, 1271180263, 1271467383, 1271752955, 1276495975, 1276810050, 1276827853, 1276975986, 1277345182, 1277879096, 1278601019, 1278867537, 1279246540, 1279985624, 1280188884, 1280195330, 1280425739, 1281365441, 1282306604, 1282549480, 1282887683, 1283428695, 1284949522, 1285809946, 1288561214, 1289221910, 1289685308, 1291331003, 1293627585, 1294593101, 1295787008, 1296722537, 1299189674, 1299373548, 1300292618, 1300328354, 1302677587, 1303678954, 1305080015, 1306616933, 1306771143, 1306834969, 1306985248, 1308168409, 1308610062, 1310396651, 1310589355, 1311130567, 1312440860, 1312705157, 1313445443, 1315168810, 1316319097, 1316951407, 1317165816, 1317194592, 1317349904, 1318656457, 1318728823, 1320920825, 1321232163, 1322149187, 1322621260, 1323971256, 1324009149, 1324859417, 1325380266, 1326150393, 1326984130, 1327124146, 1328547049, 1328616240, 1329161520, 1331520662, 1331565330, 1331736801, 1331971345, 1332963191, 1333509378, 1333919228, 1335262157, 1335599815, 1335715293, 1337154383, 1337640778, 1339913598, 1340247761, 1340611696, 1340831515, 1340948668, 1341034845, 1341282628, 1341812039, 1343894571, 1344213031, 1344611923, 1345393332, 1346372945, 1348533081, 1349032354, 1350213914, 1350950905, 1351886591, 1352431537, 1355494293, 1355982471, 1357293726, 1357999752, 1358048150, 1359767223, 1359774044, 1360128279, 1360212065, 1361530319, 1362454139, 1364174221, 1366983104, 1367068049, 1367714654, 1367855177, 1368441070, 1368479628, 1368804229, 1368837479, 1369583524, 1369855769, 1370113893, 1371185276, 1371314778, 1371778975, 1371931483, 1372029222, 1373508995, 1374865186, 1375220737, 1375926636, 1376552647, 1376922379, 1377918100, 1378544980, 1378811106, 1379839714, 1380005614, 1382074291, 1384341335, 1384688271, 1387769165, 1388401039, 1389022983, 1391792425, 1393395797, 1395045581, 1395501383, 1398055100, 1398454417, 1400466217, 1400595565, 1402703979, 1403057854, 1403895227, 1404076572, 1404462481, 1406545447, 1407527672, 1407997811, 1408086941, 1409082177, 1409862589, 1409887199, 1410428004, 1411319174, 1411374008, 1411793439, 1412815175, 1413003277, 1414083082, 1415283081, 1415350715, 1415451316, 1415847344, 1415939280, 1416026102, 1417487075, 1418688757, 1419063297, 1420323335, 1420812293, 1421622011, 1422400853, 1424663698, 1425171719, 1426152439, 1426694852, 1428207654, 1428238232, 1428637601, 1429211767, 1429487133, 1431125824, 1435354006, 1436425559, 1436932309, 1436997707, 1437151093, 1437369697, 1437425695, 1439117169, 1440260015, 1440277160, 1440322446, 1440823619, 1442011146, 1442177012, 1442783889, 1442787249, 1443722120, 1444559505, 1445411023, 1446097888, 1447597682, 1448185510, 1448293050, 1448397890, 1448399122, 1449219024, 1449525576, 1450905386, 1451046968, 1451669369, 1451677616, 1451849637, 1452762920, 1453281896, 1453887218, 1454823110, 1456586340, 1456642987, 1458243845, 1459398068, 1460098689, 1460577997, 1460812344, 1460943156, 1461649083, 1461699908, 1461765045, 1462127468, 1464974976, 1465074726, 1466245295, 1466591385, 1466659070, 1467737975, 1468589061, 1469870207, 1470965705, 1471562839, 1471729033, 1471842593, 1472850095, 1474673663, 1475140198, 1477792910, 1478221227, 1479257959, 1479935423, 1479957203, 1480182734, 1480255617, 1484202364, 1484401099, 1484466123, 1484876855, 1485311662, 1485327711, 1486021264, 1486651449, 1487012781, 1487077527, 1487911055, 1488556701, 1488776143, 1489553373, 1491172276, 1492065852, 1492570988, 1492702966, 1493205109, 1494217431, 1495648600, 1495720725, 1497048811, 1498944262, 1499522520, 1502193929, 1502662827, 1502852309, 1503419364, 1503468394, 1504605425, 1505178033, 1506033088, 1506942455, 1507152843, 1507531524, 1508597554, 1509049720, 1512088388, 1512656466, 1513699825, 1513878851, 1515525363, 1517073186, 1519511257, 1522190574, 1522281174, 1522839497, 1523181394, 1524375344, 1525037893, 1528089482, 1528844112, 1528982285, 1529844583, 1529930468, 1535399511, 1535673730, 1536144008, 1536304683, 1537391917, 1538802950, 1540343605, 1540770125, 1540900913, 1541023724, 1543552372, 1543633283, 1544145443, 1548340092, 1552634444, 1552971126, 1553235503, 1554785395, 1556322416, 1557407688, 1557688350, 1557843204, 1558041196, 1560149302, 1561636173, 1562153443, 1563589444, 1564003145, 1564417989, 1565241984, 1565855587, 1566227374, 1567719783, 1570069258, 1570711654, 1570881216, 1571201796, 1571716521, 1572550499, 1573425278, 1575772936, 1575929789, 1576831581, 1577247853, 1582862533, 1583575979, 1583868668, 1584577678, 1584702039, 1584760168, 1585466371, 1588273283, 1590096912, 1590559655, 1592177620, 1592235006, 1592245307, 1596235091, 1596774931, 1596898050, 1597403579, 1597776339, 1598493354, 1599526366, 1600665608, 1605337422, 1605571591, 1607035147, 1607541528, 1608917837, 1609385751, 1609617229, 1609693062, 1610103137, 1610819281, 1611092154, 1613404074, 1613662443, 1613935389, 1615421319, 1617076132, 1617439264, 1617468128, 1617779107, 1618662942, 1622213753, 1622274000, 1623053063, 1623217622, 1624852879, 1625138589, 1627913001, 1628459970, 1630059689, 1630746726, 1633066041, 1633380052, 1634078317, 1635563132, 1635695417, 1636907719, 1637819920, 1639509994, 1642970033, 1642978353, 1643165266, 1643731770, 1645151850, 1648162388, 1648176500, 1648656592, 1649417285, 1649820406, 1651367924, 1652423812, 1652997245, 1654018537, 1655406177, 1655547338, 1656130660, 1658194397, 1659176264, 1660065889, 1660598283, 1662464837, 1662765007, 1662782405, 1664126970, 1664181044, 1664667731, 1664852356, 1666875309, 1667542607, 1670177809, 1670562589, 1672032547, 1672207300, 1673026710, 1673670631, 1674262558, 1674517270, 1675898420, 1676173256, 1676756329, 1677107321, 1677396341, 1678056298, 1678108505, 1678378995, 1678544204, 1678872054, 1679067086, 1681415184, 1681783046, 1682166125, 1682503330, 1683163099, 1683235876, 1683848427, 1684452654, 1684502953, 1685603121, 1685769558, 1685962404, 1690015817, 1692935339, 1693780183, 1695672417, 1695967684, 1697103463, 1697173141, 1697386747, 1697589235, 1698070482, 1699222873, 1699719056, 1699805412, 1700740846, 1702880824, 1703527868, 1704695927, 1704866464, 1705045969, 1705344668, 1706090709, 1706635817, 1708280799, 1709041613, 1709360921, 1709536453, 1710110939, 1711278560, 1711697235, 1712057608, 1712953190, 1713540349, 1713841363, 1713871100, 1714226688, 1718656723, 1719129304, 1719233980, 1719332896, 1720665483, 1720968665, 1721165407, 1722814320, 1722951981, 1723303572, 1726451941, 1726649948, 1729276753, 1730902614, 1732426220, 1732784214, 1733589919, 1733628966, 1734563107, 1735207803, 1736364090, 1736441380, 1736797378, 1738106322, 1743716391, 1744392158, 1745007588, 1746048519, 1746137896, 1748348136, 1748809528, 1749580576, 1750159117, 1750197873, 1750458811, 1750954521, 1754033408, 1754514116, 1755749729, 1756446418, 1757486734, 1757828798, 1757838090, 1759815085, 1760333347, 1760436339, 1760468523, 1761284395, 1761751948, 1761753644, 1761753932, 1762064940, 1762339433, 1764164957, 1764730280, 1764777841, 1764872071, 1765219498, 1765490248, 1767617755, 1769368583, 1771494908, 1771531477, 1771888584, 1772278911, 1773011823, 1774557045, 1775643202, 1776698056, 1777123510, 1778303074, 1779463063, 1781005645, 1781536356, 1781733031, 1782448834, 1784063249, 1784628729, 1785610915, 1785840738, 1788586397, 1788636508, 1789150935, 1789351358, 1789371899, 1789624133, 1789746049, 1791172910, 1791421894, 1792276014, 1792283966, 1792569473, 1792884828, 1793452367, 1793950510, 1795156799, 1795293330, 1796326832, 1797584566, 1801086566, 1804901887, 1805372426, 1806244084, 1807095363, 1809357213, 1810661428, 1811660567, 1812295306, 1813998778, 1814354825, 1814590485, 1814671600, 1817115817, 1817263548, 1817433700, 1818232450, 1819509186, 1819636813, 1819737343, 1819902453, 1820723385, 1821557287, 1821785114, 1821965352, 1823121008, 1823484822, 1823536226, 1824722563, 1825840756, 1826248531, 1826930472, 1827215847, 1827972446, 1828495245, 1828871747, 1829216493, 1830292241, 1830762698, 1832767983, 1833269919, 1834143058, 1834752639, 1835058995, 1835149195, 1835400055, 1835828557, 1835857237, 1836704110, 1838113943, 1838315626, 1839065924, 1839238836, 1839951696, 1840579585, 1841325361, 1841331290, 1841477064, 1844238367, 1848255488, 1848539464, 1850270366, 1851447128, 1851837721, 1852226278, 1852493199, 1853815325, 1853947684, 1854340682, 1854796736, 1854928799, 1855210717, 1857087949, 1858241046, 1858567432, 1858708303, 1859193673, 1860103055, 1861125694, 1861340684, 1861859046, 1861859404, 1862038999, 1862444545, 1862818725, 1862934555, 1863333438, 1864797092, 1865152735, 1865837392, 1866152782, 1867022010, 1869948255, 1870822730, 1875645495, 1876024027, 1876501051, 1877730302, 1878421139, 1879268161, 1881032074, 1882396934, 1882532494, 1882991454, 1883392933, 1884423707, 1885700326, 1885711421, 1888860126, 1892467197, 1894414225, 1894518391, 1894828208, 1894840362, 1895195330, 1895888832, 1895898567, 1897782228, 1897985399, 1899312711, 1900185828, 1901297576, 1901554305, 1901566922, 1901634003, 1902376860, 1902579894, 1905568450, 1906479694, 1907023796, 1908837918, 1909600974, 1912651389, 1916277511, 1917742024, 1919435740, 1919603992, 1920018787, 1922232261, 1922329583, 1923094524, 1924737504, 1927460108, 1928074279, 1930421865, 1930494714, 1930823386, 1931542780, 1932217844, 1932870215, 1934314991, 1934564085, 1934676579, 1937093653, 1937642987, 1937731237, 1937844248, 1939337878, 1941422138, 1941750666, 1942015800, 1942162308, 1942606381, 1942611779, 1943212028, 1943548252, 1945955130, 1948827177, 1948940554, 1949427566, 1949439973, 1949925269, 1951573141, 1951679354, 1953680623, 1953898610, 1955800539, 1956067647, 1956620556, 1957943612, 1957974256, 1959668369, 1960039785, 1961117450, 1961386474, 1961597474, 1962396138, 1962587754, 1964079651, 1964257406, 1966340262, 1966541226, 1968446809, 1969301268, 1970256326, 1970937118, 1971326499, 1971808884, 1972210630, 1974116674, 1974645743, 1975577597, 1976552741, 1976683379, 1977121813, 1977362418, 1977471221, 1978001652, 1979082841, 1981134106, 1981982591, 1982579829, 1983843426, 1984603927, 1985121396, 1985795336, 1986296119, 1986303465, 1986586862, 1987160742, 1987244604, 1989331508, 1989473376, 1989782939, 1990626382, 1990928668, 1991034471, 1991618823, 1992069667, 1992369226, 1992536756, 1994199947, 1994210481, 1995270508, 1995398576, 1995633732, 1997408686, 1998396454, 1998900567, 2003846688, 2004045151, 2004048463, 2004478896, 2005550719, 2006054497, 2006180902, 2006545687, 2007405606, 2008341117, 2009039172, 2009122761, 2009354599, 2009801543, 2009905304, 2010063224, 2010454656, 2011153812, 2012510632, 2013243234, 2014510755, 2014668173, 2015146870, 2015230659, 2015522154, 2016922149, 2018438653, 2019272933, 2020166633, 2020555449, 2022629757, 2022681462, 2023064009, 2024407369, 2027687300, 2029462743, 2029903465, 2030358631, 2031165069, 2031860629, 2032376028, 2032582013, 2033116875, 2033240971, 2033358491, 2034272535, 2037405714, 2040450906, 2045202839, 2045628408, 2046439304, 2048256158, 2049972886, 2050066174, 2050320917, 2051124217, 2051679038, 2052020513, 2052528875, 2053752083, 2054108968, 2054337987, 2055800065, 2056446541, 2056870356, 2059458723, 2060099233, 2061714017, 2061990681, 2062721803, 2062796747, 2063161772, 2063811941, 2064044726, 2064198053, 2064331993, 2065653018, 2065748058, 2068973496, 2069621222, 2069867894, 2070898809, 2071323216, 2071414198, 2071624885, 2071920751, 2072232174, 2072486388, 2073105561, 2076102790, 2077151329, 2077790178, 2080377608, 2080994283, 2081052113, 2081868802, 2082944844, 2083433822, 2084376392, 2085986539, 2086579479, 2086912493, 2089850001, 2090212360, 2090279947, 2091241957, 2092633499, 2092662948, 2093189985, 2094247662, 2095154341, 2095583015, 2098534652, 2099003731, 2100650906, 2101797303, 2103847705, 2104268358, 2105938274, 2106417228, 2107898770, 2110201233, 2112665154, 2113068595, 2114546639, 2116728526, 2117059555, 2119307051, 2119707304, 2119729306, 2120170418, 2120210067, 2121252379, 2121387921, 2122983755, 2123265980, 2125241708, 2125605267, 2127207180, 2127415503, 2127595601, 2128200856, 2129269821, 2129720057, 2133008964, 2134015524, 2136227366, 2137128468, 2140258542, 2140321369, 2142303600, 2142787204, 2143545045, 2145213253, 2145765129, 2145780308, 2145928926, 2146143297]
Time (ms): 1.2347

Insertion Sort

import java.util.Arrays;

public class InsertionSort {
    public static int[] generateRandomArray(int size) {
        int[] arr = new int[size];
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            arr[i] = random.nextInt();
        }
        return arr;
    }

    public static void insertionSort(int[] arr) {
        int n = arr.length;
        int swaps = 0; // variable to count the number of swaps

        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            // Move elements of arr[0..i-1] that are greater than key,
            // to one position ahead of their current position
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
                swaps++; // increment swaps count
            }
            arr[j + 1] = key;
        }

        System.out.println("Sorted array: " + Arrays.toString(arr));
        System.out.println("Number of swaps: " + swaps);
    }

    public static void main(String[] args) {
        int[] arr = generateRandomArray(5000); // Generate an array of 5000 random numbers
        System.out.println("Original array: " + Arrays.toString(arr));

        long startTime = System.nanoTime(); // record start time

        insertionSort(arr);

        long endTime = System.nanoTime(); // record end time
        double elapsedTime = (endTime - startTime) / 1_000_000.0; // calculate elapsed time in milliseconds
        System.out.println("Time taken: " + elapsedTime + " ms");
    }
}

InsertionSort.main(null);

Original array: [-2142614419, 845868104, 2116254259, -36750956, -2050811831, 401788322, 609823560, -2115244501, 1846502665, 1219603475, 228963087, -1689680495, 991201697, -830432992, -2042048311, 275442493, -1995046761, 565994554, -1684374432, -1031855960, 240462022, -1272265166, -879190322, 1955764184, -1696215458, -1723707413, 1911385280, -1276959942, 1565769774, 393613392, 825116534, 803376821, 666236197, 1388389768, -391297044, 614544891, -275773931, -1950503576, 1882576958, -602199007, 27983802, 324389161, -441516216, 2138556529, -568667909, 2027202650, 1260667532, 1374989439, 1748359535, 973655831, 543179352, 691181433, -828875742, 1787300731, -2007862232, 1261148867, 279304856, 590925394, 170630984, 1585415107, 1570151441, -850666733, -1632436291, 2000457464, 1161815310, 1863090956, 638595941, 2115483729, 682205971, 1688002527, -1486596771, -882295620, -529755985, 1981202732, -1940984926, 930554108, -989850183, 249643407, -48133382, -1881091649, 1238329307, -1298778419, 1364153620, 597438703, 325168980, 1506931017, 1356051694, 1294312520, -1017564167, -2013593924, -1994523274, -1031145174, -825633156, 28763172, -523907468, 1175073199, 1151818224, -1650720003, -1423547482, -1249472768, -418365044, -1258283602, -297979348, -1679856412, -616413522, -188338362, 738883622, 1397736089, 894544675, 1560644199, -2089246053, -1817289497, 109898661, -40930430, 1035578780, 1623205233, 1544197796, -1141396924, 441967273, -1265169586, -831042743, 823629391, -936797870, -845258537, 823534775, 1732971308, -1171399135, -1599159614, 1682314643, 589354880, -682482761, -762258321, -469567546, 86545278, -1317051852, -1695048319, -184462207, -1876270435, -313571108, -1301302095, 795879553, 984390794, 649094646, -1505008674, -178509677, -1468624546, -506828553, -1368456857, 1214532186, -402727661, 1491198688, 173259453, -1759013552, -1146683852, 973940963, 1910205491, -355434486, 646783956, -1870512820, -722886120, 1218600383, 1943561920, 794813087, 1466111751, -693002230, -51191305, 1834106108, -1619639428, 372764910, 40394330, -342514229, 1864684202, 1300326683, -480803425, 1977652628, 2033127564, -2021628305, -70332277, -572012498, 436184378, -1544960321, 38642784, -1967259877, 1481060733, 412322518, 590697363, 1820526130, 1675403429, -940825155, -1921190463, 636214910, -579845223, -1056900036, 297159396, -1318571162, 65866030, -1343301472, -1163846207, 491224589, -2042337348, 301946559, 2020465060, 1669495547, 253152238, 56790073, -1666758833, -185346564, -1535926054, 1436840192, -1211718353, -2028654520, -167164591, -235811815, -1712025903, -1392253724, -1865514377, -1053251421, -1448319084, 48443207, 1572099989, 443324184, 1277115550, 1541904447, -1702351059, 1022836434, -946974189, -1045312235, -1105473202, -1763572783, 1453641604, -715307793, 608806698, 2077082811, 1213939621, -1710663563, 2025923557, -1080429277, 694605635, 334081975, 972056239, 502044685, 1843509108, -799724978, 1159555604, -85926223, -1292329201, 421045696, -1424862062, 1631219583, -63062178, -1446689239, 1726332523, -69756573, -1106794478, 2131240214, 1604387005, 1929181002, -1052869002, 814975668, 521396687, 649676771, 342422503, 67114281, 759575212, -834110039, 619556739, -57773503, 770519542, 1833519905, -1986715871, -283603123, -313276429, 856207200, -140319872, -1928633529, 159510508, -631552304, -1113764926, 1261483834, -194977098, -1447795661, 357340186, -2086498080, -1587620208, 799487462, -1058874428, -1682431092, 1441687600, -1208059030, 14222901, -648647862, 627769623, 1834716960, -1071907948, -586361276, -1884500180, 1662371923, 1307114600, -100097946, 1261183369, -685803140, -2022769519, 1483720005, 1362968207, -599388480, -1976157828, -1939952580, -102037697, 242684092, -89227374, 298971864, 378010572, -1123283067, 1532482288, -1904739979, 460485995, 649837034, -1744801955, 1543247400, 872556910, -2014403333, -1328655496, 1511494112, -1939715696, 723158990, -1183200463, 1842533319, -981674606, -1146163328, 1031908730, 354639597, -867110394, 1800056698, -1854324419, -1447459288, -1453893526, 648122869, -417661553, 228260405, 456471672, 133041343, -859137754, -1504340446, 1395589819, 1346567742, 2095324424, -2107109904, 651314277, -1546799435, 1557982853, -298556557, -899277729, -1084698170, -753466265, 1688880509, 1210067362, -748379081, 731233127, -636109509, -1709428027, -1691205128, 1388772833, -1352610338, -1779796266, -529899420, 1636479691, -539170179, -781076628, -1495689017, 701343715, 227763769, -1088466948, -1152397536, 1991011111, 778715809, 1949363819, -582434521, -1989818486, -1453522856, -1266106139, -2132803183, 2091636964, 1960793589, -449434388, 99804049, -849482967, 679080234, -1494588493, -831055198, -240871203, 1108321831, -449747028, 1899303555, -116597561, 222015808, -1011001505, 998327171, -254407964, 2132799180, -1181019779, -1400895746, -1301158754, -318493360, 1745126965, -1288458202, -965395394, 647364061, -252294715, 1716317446, -953492578, 799712950, 905133139, 363967428, -1025400287, 2136677429, 45767421, -366002138, 1378487783, 1433150446, -1755312595, 2081416535, -1463376835, -780990956, -1166177998, -1785350167, -866783917, 323580187, -1136783604, -1226353635, 955512624, -1066830945, -147115898, 1712079970, -1384344599, -269176700, 295065482, 594201627, 771147536, 901263709, -925944912, 1242634917, -968550805, 1840282385, -2101617641, -1087362408, 1891480038, 195545275, 1593883256, 768528715, 654878409, 935497938, -1816947848, 1998570141, 1859228205, 2003613834, -1900658628, -716337933, 985499308, 1012668792, -1995772606, 171692412, 1106057559, -2021442180, -349375889, 1978481851, -1201813012, 370767066, 1586927715, 2100429638, -939705784, -376722774, -1840423148, -1455757621, 812902682, -1434739854, 1137940890, 132712275, -506174503, -1859562991, -730369209, -1015872310, 1203184631, 1828523742, -1310412294, -1703136066, -837121194, -945423088, -782251596, -800919449, 585217019, 1218730591, -194636437, -1822998809, -45873407, -1571031829, -52934370, 2023448529, 590008015, -868867235, 730951977, 73660911, -895928179, -601318581, 1067324122, -593104321, -703694637, -680998431, 1668039235, -243519681, 1033439139, -1805020484, 294043985, -47199126, -431151207, -1313105639, 1492810781, 1183941121, 1447046240, -2075756754, 2074539650, -1474607858, -280152984, 634619863, -340820242, -532847707, 1845447125, -783735179, 1783380605, -72703635, 1330126522, -159413997, 110583363, -441771938, -429270906, -1031366455, 400828905, 2092294603, 2012061374, -993629083, 32667514, -552744029, -1243094804, 1138379079, -1557465986, 1813880307, -932804649, 1218465419, 457005128, 1746187438, 1643415027, 1358311021, 339422092, -2146635344, -1360954598, -1875011095, -1495337676, 437209856, -1649188996, 407454370, 760799347, 1708947797, -1424791084, -738355452, 200749081, 1303612123, 317105372, -469853012, 1704071977, 2041077302, -833230846, 1333169414, 1879551656, -1598535225, -762304676, -1651042249, 1418621111, -253005011, -2125639976, 2050060862, 896598244, -1078617331, -1983439689, 249531989, -1473748548, 1303470358, -1438601413, -319083363, 352196516, -788708289, -561202786, -649748999, 1974036712, 1345446739, -896691130, 988635705, -1476916460, 22888878, 1202297911, 2060256379, 1506005378, -991488952, 1289852361, 126933453, -1384369868, 536763122, 1239287450, -1641576937, 1671671267, 2104543712, 153336517, -1380226249, 856589399, -355416217, 1139730771, 1639016045, 951133689, 2060911110, -164123663, -586448903, 228743590, -1455889750, -631652893, 928280835, 937301445, -805478611, 486848056, -1373428806, -1114413157, -152178401, -1564921537, 2106823102, -1533477923, 190428361, 594189625, -805002046, -313975674, 758969454, -433807793, -129958547, 180303851, 121611220, 823016902, -1691171711, 931022092, -1390309374, 823416944, -576656834, 505977132, -665630902, -2094530459, 158758920, -949550430, 1759968649, -292239885, 1123735623, 1369849073, 838135981, -1078060078, -882100082, -1305538026, 1883443575, 2077379228, 1373334014, 1116650785, 12055681, -67852421, -147135508, -1635098105, -300068990, -129498589, -712454975, -550392139, 724993745, 1952284163, 370552098, 1817311592, -76280025, -1776596298, 1584116048, -540250053, 1641326504, 695332799, -1469145904, 325529089, -418271196, 1433280373, 1869534286, -1025882027, -1505484903, -308263620, -1829690947, -564712722, 369352444, -458079499, -409528637, -19278793, -1143239624, -174648905, 1220030804, 2054735646, 1829169526, -683198018, 542516892, -2065578453, 34765983, -1497868893, -246384606, 343845845, 1196892958, -2098391859, 123320106, 10417168, 1387568618, 853438759, 997399130, -575157462, 1536842179, -1680471021, -791066209, 2073408983, 1570633659, -1948457315, 127370321, -478665078, -1814865417, 375449843, -1113291372, 717263877, -1542309705, 1550249237, -1749103870, 392422707, -913210477, -322551608, -697032314, 921060917, -1509879034, -12201264, 2082118794, -996754758, -1949405648, 641892189, 1816091476, 1094779283, 197765335, -519491643, 108118189, 1927388550, -1876189778, -460930701, -1550319421, 1062279009, -1756428070, 1402660895, -1469830832, 1721290066, 897730225, 1266319167, 1330579450, 167043958, 1869593284, -1637810500, 1123062524, -2136200785, -1980292321, -828897560, -454838266, -1524626759, -382575666, 14104496, 400405858, 1073993855, -1694214493, -831666419, 1669292375, -691271253, 1245268791, 1892321984, -1075248174, 173751419, 1915446061, 2014210366, -1669355967, 486281947, 542074557, 413165032, 1121779138, -1340851281, 88157552, -2022065026, 1792103293, 1944993135, -1306536152, -44843051, 821104461, 1404884473, -1920593565, -448237624, 211667109, -1496054879, -1117066048, -1089340820, 1729429937, 2067860365, 754714305, 388275335, 17625275, 380375360, 793381841, 446797121, -100009008, 369300339, -2052270711, 567877916, -2111976798, -65576405, -1017861842, -1392725983, -1637150032, -1336679929, -355313026, -889074853, -254312028, 709079258, 2126010027, 2110348681, -972592645, -502923399, 538106791, 530993934, 1347753450, 1111831765, -862593118, 10077484, -1792023424, 1125428811, 792947920, -1001773967, 980260103, 393851194, -1724549777, -1877076368, -992320336, -694591018, -1184734200, -633668940, -1896160658, -1093741765, 702802932, -508409103, -2135122655, -376863547, 1270603297, 891832957, 2097221623, 1678106782, -1752496618, -1829652227, 1388343567, -671707241, -1368763596, 860716131, 1798850142, -1991330245, -1034497474, -1103464937, 930342102, 147484449, -710591718, -910624908, -1279574588, -959179134, 1291458264, 1984596341, 156671609, -1254474998, 462406131, 1031404463, 484197932, 2031306738, -1369190697, 610332290, -1960380898, -1100399538, -1401320285, -1849734005, 2002968575, 236520355, -1325943249, 126642012, 2073073296, -386513988, -1681683120, -365909137, -793516919, -889343043, -962861478, 2131894103, 1188998588, 1399672952, -337975322, 860727, 900087417, -197459457, 1898808020, 1561730424, 496217396, -505969031, -268704109, 1339563446, 419836517, 1018476089, -1624345185, 971998970, 1896389295, -1511820020, -760283573, -727754706, 252262212, 1083106514, 1153317824, -1546473011, 427159687, 6270287, -1204690107, -48000039, -1254859022, -1708430014, -1456488000, 297469714, -1291317703, 1442949303, -398545540, 107881828, 1282887343, -790050663, -640790485, -1279347296, 299972841, -1229783158, -1495069393, 245190255, -1048721504, -92526601, 1923319828, -1774832510, 120269787, -1008799898, -396783775, 32598030, -1652965555, 1761665810, 1984982928, 274830711, 328874235, 2004496824, -669584807, -77275829, -1612183519, 689387187, 1045138998, 578135921, 235141462, 717169222, 1065191971, -782699103, -1877898770, 1689015096, -1525278298, 976939286, 921406879, 1624782246, 887665934, 1310814082, 726338150, -129647852, 1815753215, -794277054, -1406832981, 1727184836, 537026605, 58256083, -214596189, -1444286133, -2010894746, 1982055299, -1309356555, -797701536, 211065814, -1087888533, 92346016, 2046851063, 1814624646, 777170588, -784038373, 860535694, 2034843685, 1718221719, 351563709, 2009276101, -1454670325, 1873019651, 1558027103, 1301711924, 1275699578, 1691768473, 297460543, 1545249144, 848503590, -1241623710, -1984082906, -350204273, 1508922615, -354565340, 221969357, -285174171, 1644517644, 1530634521, -387141252, 1985758382, -50395901, -283118110, 1811391732, -457134858, 1771320695, 1398603450, -1149505649, 502318837, -2046143031, 1160188910, -2042764380, 1907571752, 865345571, 2107638412, 1266873904, -587515236, -175253062, 592563546, 1856052914, 1279992076, -695562414, 1994393866, 793366869, -2121443282, 1247417863, 553011115, -1282934956, 915467593, -1469590455, 1022183265, 502958489, 35439115, -514943193, 218617944, -1756647000, 1902470552, -1384253487, 2109976053, -948005701, 266267366, -711846569, -53899442, 1756114221, -1390063545, -1748588874, 550214364, -211167717, -649376697, 217753877, -1722314385, 1536847175, 612930487, -884330933, 1938709601, 85274432, 1564339465, -1600647259, 34685710, -2137280065, -1881758498, -457602843, 1720222595, -448094124, -2072758307, -1651376244, -1859239308, 1061625665, -2016787002, 260930140, 1912866419, 1009055910, 1952326086, -1362326249, 1862808159, 111146973, -1061252084, 289193101, 237253402, -670755033, 863871131, 470064853, 669209726, -1135713401, 1073702754, 1331379162, 613249424, 415152878, -993103479, -1353289191, 1732244470, -772224873, 1314324493, 1052009384, -2058168666, 945742772, 1425026958, 2120232825, -1828806688, -834685878, 1949500775, -1716356385, 873694813, 1429062233, -250824193, 1215467346, 1071723976, -2061610177, 1023071326, 1956974702, 1433527917, 852375901, -2068518141, 394366529, 1613937712, 833714682, -663675405, -960989243, -1605459777, -1029903001, -1993499115, 365375915, -1667232501, 564608356, -231025219, 1185961306, 2037478899, -1515133502, -437844346, 373972022, 2123059266, -1462166711, 1088778340, -1967703259, 1267326939, 85966043, -15182344, 582726222, -228309454, -1580027175, 1594257958, 852841763, 1085375486, 1332175044, -726027548, 2103086753, 802120236, -699986649, 2051951957, -2048907818, 1037727254, -1541446732, 1633058581, -371980637, 1151710452, 1219917229, 1168675030, 1358254787, -472692078, -111944571, 494005803, -1135739125, 1461167939, 2126963398, 1690527395, 164790515, 1691023637, 1345050421, -1451758566, 571494484, 847021125, -1710166477, 949510730, 748437874, 813600501, -1598204571, 628380584, 1400765245, -644295652, 1130585495, -1915707539, -1914303020, -730156611, 2133909213, -1425378062, -481268407, -1469741477, 717175547, 790507584, -502442837, -249892437, -560553466, -1285100569, 726062400, 111275147, 613317962, -958079986, 188323346, -818877389, -1072749458, -265959733, -356808788, -876968791, -1160298282, -859034187, -678195163, -176341382, 254378824, 1130822838, -2016316579, 1003393958, 1601015761, 1964298789, -1182434426, 409225179, 1721320425, 277558291, 137078246, -186740762, 1248180949, -1194637596, -1407821862, -511132570, -89803700, 340973857, -1033838563, 980245442, 1984512349, -1758340979, -441300918, 1479935836, 1895095183, 1348043893, -40027489, -853651450, 433080905, -1577324212, 871497731, 650411444, -7079308, 1529327990, 824433225, -484829581, 1965141086, -1087064220, -617398602, -1805557606, -950035487, -1823161120, 1503835328, -448506818, -958691644, -857015383, -1659609832, -840650774, 2962784, 1232298818, -427137814, 1284252815, -1016698490, 2080143366, 421849443, 60738745, 928536480, -238938240, 366743411, 1507943171, -145420778, 1218076153, 324883412, -179835955, -1818923278, -740669103, 824137546, 1788397099, 332570566, -262064878, 1278192427, -1065658336, -886303795, 2077721537, 41050657, 1514719755, 1113691215, 656279928, 2118347054, 694715745, 1006299978, 1706101681, 82177264, -1167496548, 1131222094, -1801786781, -970043610, 547615346, 1592203176, -121649582, 1201107058, -1488933302, 1232008130, 1460451491, 817648223, -62792725, -1567016759, -290820178, -1220848218, -1461321610, 950811280, 1593591063, 1821939885, -1247494506, -1817576268, -1372446433, -2046215601, 1583766517, 835337471, -87769289, -1536588574, -2136364559, 446709777, -140957738, -1237564043, -1470937713, 331236412, -788434036, 1454494553, 1008493231, -2107457872, 2107517781, 1603898338, -1488546175, -270940457, 1518656050, -1727478162, -1902291657, -335588350, -1421499403, 615416998, 707073787, 1089810757, -1514998436, -1803853052, -27043805, -823538786, -471096991, 1891208596, 388622499, 352009820, -833028144, 824753405, -175948093, 655638974, 5759257, -2089910334, -234569455, 1045880793, 509373287, -680832059, 1873230744, -58518593, -1462881039, 67720205, -527109039, 285587165, 1020997519, -450789688, 23073497, 37642405, 1901410703, -782182509, 1997229924, 626072684, 714565577, -169416200, 75111665, 616765844, 1252875504, 149647415, 595378878, 409975277, 197673515, 1699816008, -134211330, 39166552, -273533725, -890769120, 1211096265, 1234284973, -391496226, -2105462221, -1915367596, 1909981662, 1948263820, 370966330, -215018399, 538531676, -1620526687, -996389323, 1930724344, 1862640313, -17279005, 836601267, -1461066921, 2114091150, 993710660, -268594863, -1684850394, -46750818, 134021171, -2125546881, -420564753, -1615186629, -976383698, -2077046390, -1136344628, -737363992, 620754075, 1192243925, -620262303, -790009793, 1901423320, -82422679, -1420450804, -206858220, -1862429808, -724990031, 1245951835, 200515547, -1428091568, 1503136637, -1875653698, -1872821690, 473823833, -565900720, -893910915, -802380238, 1036484279, 1392984279, 686427371, 533744323, 569805714, 739051702, 1107291612, 956733901, 843811779, -940586102, -310806957, -1272087435, 1965409706, -1245896149, 298432383, -1497721321, 2060355134, -1176755151, -2061863960, 1004800362, -207394460, 1081715641, 2063012325, 388885474, -735292539, -443641495, -728776367, -1362031787, -1818300326, -96525136, -2028156802, -1542067743, 1998244617, 360932434, -403362712, -1408691188, 1292260213, 788249379, 929769517, 2040280364, 1504077009, -422689518, 498345916, -1919316472, 898572662, 547676265, -817284659, -16404033, -920242185, 715427666, 1132997904, -2115654424, -2091129487, 1069215132, -802370392, -652346630, 373377318, 1193721535, -910364710, -863965714, -277357235, 2112673821, -1552330495, -462853086, -438359773, -96801910, -871342139, -358012800, 513998917, 953021966, -26246516, 1130346719, 2065556289, -1450551575, 1927445295, -104714584, 1277711721, 1188025046, -1015553295, 590419388, -140035093, -84670572, 446493100, 1752497557, 1874369054, 82973601, -2091776948, -405278549, 553598750, -922323384, -1032022399, -1386971624, 2088974490, -539333666, -940399696, 108607870, -1297735956, -1487779257, 2133238570, 2016007464, 621252201, -1220107841, 35296159, -212518289, -1507368454, 313009622, 280218068, -1790294946, -1000832277, -1492475204, 1240495764, 785055897, 594567682, 429097662, 1192957923, -2070373766, -1429443117, 890021904, 573000057, -1422896004, -49800622, -1046176051, -1826183058, -1743506468, 290672041, -1611568325, 343653937, 2072003197, -1258142132, -1369737134, -44292418, 1209502475, 1676496457, 241855102, 1301440015, -115199133, 147312612, -1765418333, -1081925421, 1302878514, 1761320803, -1420280478, 1434496093, 1431016667, -351367643, -417170790, -390911521, -42252642, 140876537, 1328740657, -1584750377, -658632202, -1533389908, -2078596332, -955003704, 1351428929, 449592291, 862627195, 48206381, -354133082, -1918808789, 90698097, 1303924394, 24370994, -1236933554, 1353826451, -446728060, 1469022532, 1928179688, -437411305, 1346453843, 667458347, -480480199, 1969476624, -390909962, 819386637, 1125562427, 396946671, 959309254, -984749814, -2109231114, -713418420, -1656650995, 417101984, 292222995, 569962982, -754491719, -894229424, 1839068847, -775934488, 365626700, -1250411134, -714738318, 1897575790, -674254058, 873958053, -1795864353, -130361274, -1917403738, -1911855718, -1899292436, -974672646, 1029611645, -5317550, -550592811, -873276402, -1688624891, -1711360075, -1614812116, -987145339, -1600766527, -349598523, 560303925, -1231692118, 1153621188, 1420639235, 1065330800, 2115239436, -996577945, 381846289, 1555973494, -1566614583, -724111050, 1102939288, -511568632, 1606043663, -697425878, -418092437, -1031026588, 553363936, 2109971485, 1798014444, 1311749594, 2106339348, 146106233, -1055354194, -1282895713, -1453912412, -1391029453, -2004549797, -209892895, 858967076, 644044791, -2047778600, 203124507, 2022368145, 1963003556, 756708262, -1526163030, 811286093, -291456005, 107106187, -1797078113, -858076570, -1785584750, -1859735183, -1668246059, -1253920482, 1732285966, 1539981, 1543504710, -1007423065, 2146561680, 1211034563, 216188314, 1360356397, -697076881, -1726031800, 282955520, -354391782, 619154984, 2099077768, 43517249, -1015887723, -1079865710, -1204504502, 963172882, -1537178038, 2134109525, 450403090, -1623550807, -1163350672, 312263068, 180762054, 1023074450, -430155513, -1853137399, -1638324076, -189827646, 142048354, -1216395031, 63631122, -831984148, 1935618020, -13106263, 763364518, -402842861, -1888385522, -989571705, -1596429529, 871871328, -1588646728, 2108624268, -198215740, -1949735372, -1689821538, -98472008, 1292962340, 1227533953, -221058786, 480428415, -1217883697, 1411970645, -1902949825, -2027968140, -875526708, -609624137, 1159146229, -916761021, 74396298, 1587136182, -789202526, -845700891, -1355283965, 834130110, 400992480, -2124374514, 1614193182, -901571283, -1332423043, -2114235672, -2130989740, 502393637, -2109350202, 1606320390, 1637398934, -975910749, 2052136968, -2070430317, 1846800750, 22355664, -1174080941, 258885577, -1357276316, -1986023529, 1681987457, -617065815, -130796638, -2118068105, -1325815946, 883865064, 1866071002, -306073959, 105249960, 1876310568, -366402201, -2005776348, 785605857, 240448615, -660997710, -1384200496, 80452163, -1677892420, -1904171817, 1362229177, -88389492, -413119425, 896435847, -1306420107, 1107632795, 332492361, -232968913, -265440920, 473058355, -262491939, -603234470, -251837098, 1647909886, 1994149989, -828975277, -1179077063, -153126445, -1085269344, 1417909517, -2123733164, -1343333061, -1475287846, -1836324281, 1684817031, 155201585, 73838942, 564307179, -1864784155, 1963727401, 296433705, -532481097, -1822265725, 1651275603, -127809824, 1774199070, -1001036398, -1371602912, 618179586, -985620368, -1283112784, 2002871556, -1449549471, 170912056, 1745670266, -1774886275, -1202591282, -541938460, -1137952667, -595357356, -1825434093, 1985016491, -2034090290, -427526365, 1683006757, -1596783189, 1887570510, -1941202154, -644222054, 561815889, -1539907501, -733437195, -1651823016, -576454659, 879540460, -800146335, 513621134, 425242596, 1592638435, -1093478819, 471848168, -374844872, 1693580048, -1776980208, 513028606, -464672633, -1361052180, 1056242120, 244980236, -1988586400, 1766978148, -177069758, 796470760, -1373377221, -805529873, -977311192, -1266961616, 626544794, 1599222242, -230032934, 1240419778, 1258901611, 680339970, 1103201649, 1056136305, -970153040, 1517491290, 268545280, 2072243444, -1618920095, -1529197745, 1377781532, 1101757217, -1854509680, -1425448207, 553672862, -2135625893, -1979617074, 313069203, 1728967846, -1864724407, -1422782003, -2022290531, -654663453, -863642680, -2126692026, 7071136, -813049326, 620722978, -1631664100, -1091065942, 217539780, 1923991167, -1201571903, -2059350309, 475469411, 2146667419, -1305510695, -758476232, 943792758, 1084754873, -1060980708, 538366910, 1889499171, 440165591, -777567872, -275099974, -776670219, -785262046, 1321236886, -1919625385, 1354721760, -1832407124, 312692019, -965378184, 958516097, -1929474725, -35745965, 228308167, 1075048105, -1233478364, 693407035, 834907150, -2002143204, 1521277049, -1370013475, 310226373, 115060373, -130074369, -1939159681, -403367957, 1649883661, 927383684, 1554510493, -1119540967, -914549956, -1652978640, 1844658446, 988211411, -430397601, 265709305, 567959142, -609959647, 851670076, -1240559780, 573379228, 137731422, 1519624291, -69622711, 1636588523, 1433051727, -756722763, -228135586, 125101308, -1946692746, -1333619671, 1738437208, 150485316, 412170664, 2103814861, -1927834170, -2069210197, -1130668323, 42882315, -724424962, 679453550, -1673055418, -534624722, -921034923, 1035010885, 870231973, 1448459555, -1764917623, 528162503, 76073176, -970902909, -121701758, 804180493, 1847625909, 1838506704, 1466398266, 139464598, -920362979, 2028943614, -1664912392, 48904298, 1451230795, 866213173, 1079572163, 286216833, -2075887251, 2074176469, -298481898, 2070528356, -1417218955, 1638078650, 1551584975, -216111852, 903409200, 1791738560, 286228589, -1447607509, -984058474, 1208826761, 594247034, -894624191, -629571740, 620676989, 1085632582, 501784465, -1415710488, 1207409170, 693914837, 620361435, -1382304741, 2141082189, -2101449446, 659559563, 917274868, 1800747911, -1675543452, 984015385, -801765382, -1272752524, -810310121, -428467021, 748435995, -1221169567, -1917043809, -241125862, 1445620156, 1645919932, 749684130, -1019289655, -397647599, 1200155865, 200815732, 1885021275, -300807763, 2054380019, -469425201, -1424149715, 495810908, 528752, -1411750461, -1033682366, 1883535408, -1460873368, -429963029, 1433741927, -1158949927, -1571873945, 2129956321, 1284153751, -1556868038, -658910350, 1626882035, -1366280288, -1093376712, 1698661192, 1608639766, -1792214779, 1819920852, 1101460457, -1059243750, 1942281254, 319679611, -1104322725, 578349087, 861035678, 1999249564, 56169643, -1369310137, -38541076, 650144123, -394012622, 2071720620, -1917843884, 290298436, -1267432423, 120630164, 800935687, 210035555, -590107362, 1657973219, 1892265601, -1550425838, 1941917591, -2137041456, -2045870030, 1463254835, -729954121, 1251358427, 1773499488, -1347598753, -107962353, 1731549438, 1173118795, -846862786, 728491351, -998616798, 1094997649, -1297084136, -534829458, -477457196, -434454316, 1366555820, 1837711775, 375200056, -376357991, -1564795840, -645883866, 1206545725, -545031309, 105965561, -1578277646, -838352110, -1372026272, -6797972, -764658773, 761568472, 947849330, -724146828, 1911223285, -1687547752, 2109362865, -1746064571, 286426358, -1841965194, 1197519935, -361991999, -1636526826, -1747280858, -1329003075, 897760266, 932954629, -1095615329, 1529372397, -1244972456, 1384768769, -1473907953, -897139048, 1551897611, -1306536103, 1897634318, 863751346, 813002243, 1168014124, -696877035, 1257446075, 716352559, -2144793482, -1274184143, 1934198375, -104543900, 1294794316, 1482638835, -754212224, 759027823, 2048125030, -831972694, -2085139957, -444398996, -253212450, 1955817940, -2006924887, -1270114727, 719199799, -286591280, -1354888384, 625540581, -784556640, -1558934056, -601796646, -979850354, 389450104, -1865125329, -1760197684, 555636202, 873655316, 300022678, -1747015398, 1341527108, -757056832, 441652995, -2024713190, 1762865258, -670554876, 796040853, 1485526614, -1424375356, -1782934489, -527450943, -1739476041, -422681176, 1116380920, -75247919, 1853244894, -1067931411, 436237771, -1869645169, -26627627, -1689651523, 428837570, -1509496003, 1866765286, 1914970287, 1838185037, -145724985, 1658652107, -1036528619, -1110280205, 1933034555, -1523850489, -110849903, 139477841, 1187788920, -1550356590, 701035502, 1188096355, -215624155, -319863621, -116691156, -369306110, 1087015909, -515921846, -355419940, 905181613, 1513771976, -2107592220, -109670226, -1174796405, 598553348, 1434968755, 1920903240, -1298526288, 797245668, -1318513851, -696335016, -470615649, -794810113, 98425780, -64458516, -453860593, -1797661523, 1608047111, 1816905728, 1952294641, 1708615607, 148667096, 786317656, 299765938, 604609613, -360503242, 2017950864, 137592765, 1925483068, -1088355636, -1883017615, 1849917251, -1145113249, -563771070, 885685893, 2071008830, -9552042, 308662755, -547001876, 1015993266, -1647658890, -1394722177, -1352925327, 573496117, -615281664, -2012958062, 1166739671, -1421298254, -269960300, -1741487195, 983496057, 1080355433, 193256935, -1237140492, 1681267217, 402302009, 122131635, -1142251696, -1505322537, 615245601, -1159926289, 1980219974, 131157197, -841934332, -430103488, 1119531905, 413939545, -1030952788, -1031572818, -52209812, 801400595, 330154512, -70127718, -1844684261, 2128627936, -382568743, -1138515217, -444507285, -1746351041, 1637596194, -2138223720, 1901672807, -1991186462, 999069311, -1837070287, 250617069, -1063758976, -505941696, -903063808, -102552432, 341805801, -549853705, -1336860378, 626657728, -1336906150, -169904074, -2039626479, 1770552360, -1384115182, 1875364253, 1083069492, -1726681257, 1327734565, 1412827667, 459044858, -910776670, -1631899761, 605792338, 1855762935, -1020736697, 1232289675, 2010547881, 1464003424, -1178748715, -1951530459, 1008154621, 939263933, -122672181, -592734450, -2038462192, 850489052, -1845086593, 878782383, -1127622139, 744931848, 1488199745, -839106176, -2024928221, -1507774341, -2081713472, 1670447513, 968951768, 1821056784, 845527467, 273081736, -1084743935, 2080249660, 1346189467, 1732334949, -364261528, 1388851519, -69788881, 1270758180, 1312401806, -1759416938, -1398267016, -1279902934, -1850384471, 1956164019, -208266600, -1896914398, -1329250065, 1560763375, 1988822949, 2049727504, -772627179, 378905279, -1312132910, -298874715, -1538585582, -766954715, 1610025680, 233472213, 1477375528, -1069890966, 532249201, -1146625626, 19380260, 2133231369, -639693681, -343510965, -227553309, 1473694958, -2033088469, 1333390193, -2020770536, 1629952224, -1665696040, 393682391, 148349517, 307334970, -1432436903, 213255716, 1169764903, 102732257, 1460194953, 1380853748, 512208109, -1917728399, 726370939, 1830705715, 855994954, 1814236601, -1212785695, 1379051182, -15668398, -1601379991, -1064396367, 1659899623, -678571838, 1764455689, 1073480453, -898151896, -156888693, -1010146003, 925397826, 1294782682, 1549016465, 746760167, 124007548, -1956263658, -16738129, 2137349500, 2102563865, 270444668, 739883518, -482969511, -499606093, 1838784323, 439016279, -300584889, 1958879299, -1592778607, 1633615125, -1474202403, 690971003, 226761741, 750862879, 1057608502, -1289739406, 2037562545, -1707431899, -1353547036, -1219043194, -1795964700, -1988329432, 404753956, -736534147, -219299897, 1861970752, 199051602, -1853746707, -239538225, 135716761, -566194785, -2107132194, -2096151917, -1262126658, -2040698112, 280456109, -507385370, -237068775, 885720425, -411629262, 714709544, -375509318, -1179217605, 1466194725, 776478169, 1183275351, 2017239802, -1014511683, 833031790, -1550335597, 316360258, 1331121561, 1223214695, -603157629, -1820717061, 175176675, 1998446753, -1592849811, 1604624331, 1824671922, 1052956904, -1531504686, 1382499532, -2090604112, 791585232, 606951086, 1342486910, -121105668, -1628159036, -157817091, 1068968703, -1806483375, -371795617, -1742713471, -1407320199, -1269437337, -2096071430, 134845378, 790433754, 333437593, 530709381, 448390230, 151603402, 978048711, 1634361498, -183818398, -800463143, -1225977987, 1344450511, 1768579936, 1968488952, -1506447788, -1303683253, -1987713502, 174021675, 1899926168, -220305509, -590972395, -310007941, -1424666069, -1166934842, -1127207990, 1791145776, -356391768, 413484190, -1844747342, 1747374143, 1946492106, -26108328, 1124030505, -1518760703, -43690993, -1601155233, -1638720587, -265418714, 1588325528, -70407836, -656749682, 8012520, 161385811, 1361051065, 728408673, -1815987582, -573735845, -974523937, -142478512, -2036703005, -771572834, -80410275, -1434693315, -458462049, -1737241665, 237664467, 1830250056, 168080421, 2022848830, 165516878, -587186283, 1727891511, 678778838, -270763300, -268234414, 1365328278, 714723366, -2026854045, 1352972024, -1850542596, -1319509101, -1849504082, 580744144, 1176045646, 38505068, -1414402360, 253802424, -194770927, -421539762, 1348440973, -1521095642, -1654680546, -1485761847, -2097688451, -1356690067, -1404947311, 10749507, -1386926125, -978971585, 1089232903, 1121559836, 227400917, -1479773326, -1846140921, -2035389166, -1317494931, 275000839, -1349646144, 1785040615, -1924301575, -999208601, 1898149876, -656083903, -932244897, -1907974162, -1459531980, -976142384, 1453783907, -628926547, 698195277, -777573451, 1576065852, -1180008085, -1145705726, 1319234082, -1768629661, 1877418989, -778625286, -367760323, -1374966354, 1290745719, -1234490116, 936751945, -97289571, -736340590, -816446375, -725708793, 1258171636, -520543986, -1831964248, -1137085351, 171381129, 1257155146, 1748428728, -1714734295, -729363873, -206744654, 696607682, 1283852936, 1505357810, 1268841096, 1913184478, -574245863, 1035989972, 1450731495, -481423688, -660129872, 1562187896, -2084286971, -1425260669, 581127221, -941387187, 892491192, -1507933908, 969806542, -621468146, 1093468219, -1138879021, -2135140291, -1987061672, -571383503, 1886371702, 355534982, 1849524860, 582481129, 265982703, -1950631724, -211328874, 849221346, 1880671776, -375690340, 2118905054, 1943133330, 2025860459, -708381950, 1143381053, 895113315, -445883288, 1546556796, 1715359779, 1660061949, 396205521, -916399948, 1200132503, 1896708298, -830802239, 1123456691, 1121773967, 1467896246, 315926813, 1623769403, 211085953, 396847414, 698870098, 1580496755, 53133113, 129992844, 1983626048, -1747430967, 2033275629, -1880296120, -1711658379, 729810963, -450992498, -1813381615, 44585374, 1403114999, -1039128736, -723578971, 1523770681, -1071431283, 2101156556, -681929187, -882100849, -514774974, -682200204, 2031038069, -1141646367, 575747583, -988667000, 1434774604, 1062176481, 470887049, -946651049, 1483913191, -771777949, 723161386, 1908181800, -1539241861, -1580100012, -1074278767, -203279541, 59211435, -1562543894, -1790859018, 17638762, -110419121, 146444317, 1849339521, -1319928796, -1227141514, -659853739, 2135956972, -2131827236, -1912112466, -1454901660, 1831744870, -1661791283, 1112049794, -249056587, 1368394682, 303269473, -581159357, -1619137594, 1020352432, 2030652099, -1686515701, -222547501, -1429550669, -1944158798, 1655921662, 1634160083, -1360536653, -479287400, -142162221, -342504025, -1326498996, 1992836570, 1555485842, -1085366383, 1340420648, -1777527439, 800840094, -495882014, -452874079, -1061948743, 1234730998, -1455832073, -1809195351, 736649865, -438362953, 1812525413, 1677154029, 972101763, 1131960805, -248346509, 1800761400, -1773662548, 1417951338, -884358456, 1348417813, -580648386, 549105245, -383385755, -1850799688, -2032375363, -129931896, 1572829396, -84226018, 1636710471, 1077960228, 174369441, 904297075, 351863344, 1188526566, 417077769, 1118315443, 1584486094, 900936510, -871533071, 1336927890, -851549296, 2040464605, 134758937, -1908442464, -1819921323, 509101432, 1827504529, 1375469480, 743253242, 147618764, 245699691, -1253663911, 2114082869, 1125805793, -1130447695, -1177629400, 1046235040, -715295087, -1402339687, 647732340, 2095431960, -792801205, -554741769, 1492583658, -1093868216, 666958868, 633883378, -1636219606, 898300800, -613063217, -1680091142, 573043626, -1676333365, -1718821187, 1027506937, -948503077, -927758273, -1757959354, 229011400, -1439173239, 899463830, -1194186503, -1647992348, 879120519, -1387621635, -1431875376, 1708428129, -2004517238, 40117036, -1276995144, 834803486, 992999765, -1286080330, -966852783, 287154745, 1053078294, -1869482591, -1533464334, -450717499, 1527940879, -958554567, 921119983, -1181439558, 1454870649, -146870239, 578276381, -1130969556, 48532388, -2020010326, -71237226, -2053742656, -225270430, -451178393, -1691626823, -1090020774, -1103340378, -1344038400, 171527028, 2034656539, 588274279, 1875440198, -1857293627, -373576054, 178217930, -1842721912, -956988547, 262481936, -193672577, -1459683804, 1231088966, 1255230633, 1478164330, -1447505824, 1835852264, -142041384, 1241787270, -942020742, -1651805497, 1761104347, 48820998, 1490040317, 280986287, 1610732064, 1303234236, 1709767509, -1470558252, 1385554167, 1711368126, 1933846693, 496867859, 1727608712, 1877836102, -388448552, -1214633602, 163308806, -2135130918, 572029430, -919553769, 202103844, -1306135380, -1294836296, -2142565926, -2053217336, 199583811, 30996317, -1522982400, -2131534082, 1005918041, 485124286, -589169534, 762355759, 1155606279, 447058080, -1513018149, -805127279, 172324127, -1875319735, 2006219538, -2083255071, 667598296, 1982647893, 1099480055, -1736317872, -585238608, 1265936073, -1570412116, -1253896518, 1269238158, -1525770136, -120930202, 267529501, 1735540518, -2077489339, 1192125301, -551448760, 370286497, 2053196953, 2109656705, -1903852078, 712346236, -1678451754, 1226184469, 811425613, -2046280017, -1588386565, -367476127, -1403878212, 1412575250, 321767466, -324684997, 2009622849, 1739345660, 1981935223, -326601625, 1544503578, 1869063725, -1138041854, -722509033, 1335276494, 1563292397, -1193078969, -1682211404, 2136800674, -1326376076, 1927774644, -180888866, -659934126, -885971060, 1171643771, -1457320783, 669950717, 892772212, 1184349353, 1607791690, -476679840, 1633252615, -63289993, 32491913, 403966535, -1905599715, -1817004064, 917723927, 2022044991, -1445286095, 1642446963, -1997157718, 477370256, -1701357244, 105948266, 557140359, -362049431, -986626560, 1594923770, 2020251976, -2013289379, -1229365473, -571086868, -1820568353, 86600718, 962864653, -1558869140, 649020890, 1919367719, 175199436, 354786080, -479180312, 1905781903, -2039338729, -534931332, 1570278555, 1486724314, -704201270, 1079334996, -1609229969, 496395267, 63772288, 284315570, 803670538, 1714496856, 1656930685, 287070697, -536750907, 1368364213, 1694774222, 1768967145, 1021411178, -41554956, 1944273838, 1807214805, 1141553727, 538706851, 637560108, 1733561298, -1639766205, 205177592, -592933623, -432071902, 997216695, 128719617, 158588390, -1235543952, 1357912543, 1480786207, 775914398, 1512039020, -1356490487, -245097292, -966827792, 1072921498, -987643442, 964631579, 1183478625, -373331353, -1711325033, 865330392, -70315680, -873232771, 1727881314, 584979216, -418748758, 2102904663, 1004402630, -512459717, -2077175056, 219408407, 1556521524, -179197673, 1634406070, 1131213975, -2044343937, 2098559711, 1273379453, -786033731, 1814053789, 1444900796, -713868252, 846406419, 403998895, 329529980, -520876406, 1379989398, -200489666, 693674369, 1918625656, -494905395, -1580643129, -411641605, 200366014, 1398670109, 765538425, -528298919, -1412445797, 1461934683, -854655428, 243600124, -459800223, -937394782, 1906043893, -2068100051, 1494582361, 2059006823, -616828152, -684147119, -23524893, 1153510602, 357670942, 1121949019, 1126587106, 501250862, -4678873, 1489013889, 2106999638, 1482181387, -1918751838, -947630287, -1129088439, 1188345858, 520043803, 1330511174, 425960431, 1090506289, -353916939, -406503818, 2103169544, 2112228552, 36094569, 1206491407, 1576150665, 512228828, 1829862862, -348651550, 529824890, -1924335749, 1061852186, 717671295, -1132053727, -440903169, -480409176, 1250661026, 1325774688, -603725913, 258049851, 1715574252, 1444661083, -615067293, -949923774, -576802091, -346133411, 612054254, 173398365, 1475351009, -1055279364, 1265584162, -2024455393, 1125581841, 568347002, -918364793, 1248869653, 342999964, 1857494126, -2037027284, 1070863623, -1027404834, -970561118, 1929573562, -932710787, 1508293776, -1095507649, -333781563, 964697732, 189856825, 15240487, -195176091, -643168335, 1278774756, 1111951010, -311182843, -616508826, -215724525, -1044585925, -1449816966, -1700172461, -1784739085, 694449644, -2075974313, 1711948352, -749458480, 1058692472, -1425121410, -1219859704, -1458906166, 1471963416, -1983207430, -1151290648, 723299273, 907911769, 856224524, 1941628921, 794812334, 689320772, -1145737597, -1542831877, -112403766, -1982694465, -2010282672, 273275731, 464084883, 2129203506, -8779687, -2002741930, -1602513260, 1476650092, -1748856691, -1559246649, 2108821669, 1263790536, -1563660744, 1374988702, 973944924, -1747673205, 732477848, 1249529099, -307632445, 1876366992, -321234769, 863411385, -212594870, -593338074, 1366691418, 739031638, 1455666943, 1886489656, 1363928738, 1980995411, 1867885308, -436894033, 424318033, 182961384, -101406177, 771988243, -79522872, -163856294, 788461056, 998203256, 1278748431, 1642741632, -1119912161, -1793507433, 869302061, -335396477, -1328471971, 845743418, 458729146, -713234460, 1060478381, -260177187, 1554121138, -1064739901, 1347508747, 1601488018, 300250763, -2124725411, -1315440468, 1497131813, -724331384, 674008022, -322609802, -1481370241, -973124785, 518753080, 826392754, -1880425393, 590219193, 1964687035, 101108223, -673963034, -589477399, 1089972550, 751232649, 1701365858, 776145055, 441620021, 1299664507, -398268402, -123701810, -371637156, 1852861873, -1150578679, 539228267, -1556955828, -1604344910, -626077916, 252735367, -1855267628, -1988063523, 260141840, -793963873, -133149494, 4413153, 1805841337, 2044887858, 1213200651, -1108825486, 1969762540, 916382612, -1534771265, 1693672505, -1455299009, -899414270, 107373025, -522515701, -539231951, 1828720373, -127338498, 862560605, -564066929, 195168699, 1517449020, 2078439415, -1723872231, 1333880386, 1218761373, -1145636888, 663119717, -1486335689, -1588042619, 527013817, -675190012, -1914810545, 1230425209, 1603170277, 1972064482, -1817073437, -1552622295, -656661881, 1792727282, 1534294722, 1995716271, -365491627, -1209712886, -949780414, -152680167, -674503476, -1705809141, -1920603496, -933332188, 837708717, 1725398852, 913234281, -841385654, -1866231385, 1898080535, 267667616, 1880879359, 1376147029, -1408280611, -1095727231, -399819722, 397501802, -657113594, 357338366, 1193722154, -1404635862, -160644987, -2144682679, 938543706, -15493093, 475740266, 1283454122, -1744577836, 1734342140, -604394800, 343010194, 1757070006, -1001349130, -1554457864, -1280358417, 1695807473, 1332900881, -883828042, -93917247, -509642928, -1260043287, -110838517, 1422487788, -246369864, -721571168, 872238867, 1419285072, 174541233, 1129479702, 2127559457, 1442210326, 1189586212, 1706600279, 2071935528, -907651764, -1805363354, -168481195, 1927034716, 1292389556, -1285183628, -2111679274, 1260096024, -247557416, 1204598400, 1966185647, 1635854849, -1301469342, -1251734868, -1043139278, -2137718420, 848423850, 1588036116, -1046688796, 1629733372, -1520794481, -1544949230, 1876423795, 1382408079, 1884685705, -962660676, 1175296998, -153037477, -265438978, 1811134129, -2019247339, 104143187, 506567125, -1152803051, 1287634012, -364027441, 1631212105, 483548121, -1570617205, -292937365, -1565797377, 180129855, 1509060384, -875668178, 427875673, -1605037155, -743989833, 1124155631, 49872908, -25643424, 296557249, 1927943667, 1745353967, -403778733, -1947928716, -863862821, -515995370, 1392849185, -1718375166, 1144333244, 634507295, 206174232, 1443617037, 1295850895, -957855797, -523714513, -621490855, -1598232629, 1269278928, 1492908874, -1388452158, 40474960, -1914101524, -1728823365, -1535385743, 2064752007, -1472851395, 38483724, 915181642, -1676391738, 2097214415, 1099969787, 1848694184, -1336804616, 842213238, 1329117893, 1645448012, -1921873284, 1415698654, -335582553, 1840239506, 1843028302, 1871264224, 1447047073, -705159707, -1501271452, 424587286, 2038996348, -1144872844, -1636197030, -809515087, 125816078, 219625765, 2114256464, -393412727, -1581696835, -2017072695, 340604946, -1524841867, 591027521, 1114399633, 1357591674, 2026119644, -692903251, -1199286847, -425240814, -1657264756, -404401745, 427520931, -1560461827, 1059308746, 330799382, -445553219, 1168125206, 922475689, -1221269612, 1934039621, 439912281, 1508620191, 444669381, 1181624532, -684393855, -1186334124, -1378329489, -2036449958, -988790541, 2108623293, -465669365, 327269970, -1944674854, -1698480535, 769143428, -1580588490, 969176978, 594311450, 323004478, -785405901, -1131826103, 543681687, -1480030887, -219715552, -1017922333, 517353664, 44971574, 827714988, 1207585310, 906818275, -2092863943, 1400099543, 516513783, -1788684467, -1446171696, -2084762205, 1680153419, 685727778, -481331020, 1524294922, 568997312, 134344048, -390698386, 751026482, -1023908891, -110089598, 667821853, -351581473, 42070423, -1030914958, -58461578, 1003523624, -1198636889, 1879197185, 2027849483, 23008365, -606925383, -1923935062, -917749809, 108210567, 350396270, -82507020, 1575736792, -715079615, 2112570309, -296870904, 1618785895, -1604343289, 1999028158, -1520112510, 1576023333, 909579741, -1998678720, -1595052917, -1436213585, 598575762, -86752453, 500989735, -353669292, -1497247692, 1412097041, 746472139, 1644573213, 294086, 1088540209, -516960462, 1723714573, -273606608, 684071685, -1432978320, -1569376343, -224326794, 29046798, 303826758, -472320839, -1105080531, -493296052, -535288136, 493269072, -598012631, -2032186398, 1921345245, 1618536714, 1820895611, 610794490, -995599115, -1296952427, 1712842394, -1522198298, 1022200000, -1621687439, 1123424479, -412224377, 1974695693, -1998545925, 1196596534, 334156530, 1392245136, 1829309863, 1392314130, 1445442383, 1532528633, -149347444, 228833697, 1144013572, 1393761857, 360604965, -1832492991, -1877647597, -153736122, -1996812203, 2004023857, 870238144, -1406440807, 156053419, 35351947, 712108663, 1800579223, 624578791, -818096783, 184608235, -1267800138, 918659005, 1936785286, 2305154, 1394169888, -401708840, 940952736, -1175754513, 474942085, 1726040353, 171796667, 694454560, -593007827, -1832481472, -2024436176, 907678555, -720446900, 47482210, -1625077723, -1041356381, 2082600345, -1978347204, 445900871, 1723981664, -1493473503, 40364112, 29041590, 2056963390, -1223733929, 1021469295, 341936961, 1278922581, 1087148144, 1754776702, 2131088083, -775030391, -1318209299, 1975440764, -1922655188, 1872973363, 2129140600, -1621639229, 718387411, 874328832, 746679796, -1992523123, -1831790774, 845094937, 109124047, 940079034, 698142595, 889005444, -1728847975, -1949568561, 1044185747, 659808969, 365797338, 307050049, -1614970459, -2055875368, -1222746849, -1175955468, -830443472, 973413929, -1748186282, -1355565571, -103000724, 1293888805, 26869851, 94839471, 1812287745, 166847684, 525801938, -2099251499, -100112639, 266873718, -949031881, 1291621691, 781915928, -1965685689, 1785925426, 1798185587, 1408283394, 1500157501, 1820121903, 340227285, 233449532, -1397701116, 1948789806, 234651847, -1442041602, -53656116, -1074332201, -1057635011, -1594679193, -2001518734, -397790000, -972063613, 1824177658, -696845091, -1173542573, 945067322, -196877240, 1383609002, 32950010, -238962785, 1940444911, -1558982389, 991712733, 1994185491, 1238139842, 388464364, 2059354334, -353226794, 687874889, -1381031081, -1744802494, 747594006, 1216212075, 644292888, 901314436, -1411222744, -986787991, -857462621, -664704667, -1422802412, -48468978, -616840138, -1091715769, 687268951, 1766831908, 1701249594, -1927953733, 2071885283, 284164906, 1564140014, -1931036584, -1282732182, -578985917, -295147962, 234106574, -1097208357, -969111696, -592415984, 793479482, 1313607212, 1469695233, -1030367143, -1079071045, 425640282, -1649699256, -1097191410, 986693956, -1211433811, -162206064, -558337563, -1148129869, 1196616256, 51533645, 664428925, -806835934, 339312064, -1954783340, -1925956924, -734269571, -1688727181, 54333132, 1464090776, 252008277, -1954394244, -404926810, -471199312, 2075725554, -1536627876, -676691894, 1331947453, -1438443858, -449843268, 440643794, 1748903116, -2139206528, -453663639, 140583163, 1428411117, 165158103, 668160159, -94366695, 591723033, -264377176, 196173193, -12051893, -198053808, 632197322, -2049139448, -409056784, -296155134, -1331992959, 1692580019, 732830809, 1313226927, 1273618775, 1847069982, -617160257, -962929199, -2027969998, 1267299679, 1072169079, -1414723591, -1991218269, 1782631117, -872058012, -2078417865, 1527154555, 971709707, -1506722900, 1941343678, 1305702820, -1839471036, -370296403, 1740864968, 1958730797, -1185366089, 87564594, -298947145, 883908774, -1077061002, 1708752097, -1861800068, 1614639789, -650133399, -1879051016, 1899788348, -1931581496, 1465459097, 1385778488, -1824736976, -530012043, 98021803, -402469344, -380558644, 1540841088, 1971476905, -1439560354, 268645923, 324613267, 251609608, -1950529150, -83916663, 433257235, -2063959834, -1436463884, 1928240505, -2144909783, -266717038, 655232040, 1491532473, 1410423070, -887975343, -1973259505, -1465263428, 1215492843, 1912766815, -1642916400, 1242440006, -1227239408, 1113631283, 54442167, -233605547, 553317796, 274614791, 1450107757, -950949057, -1104209491, 806034071, 1127347049, -1038692841, 98352305, -1544737240, 371155366, 147361621, 1903282316, 1013712843, -1410453610, -347873867, -665335676, 866022370, -900681898, -700457889, 460000922, 2080302307, 717757218, 1080530759, 892230178, -159229860, -1412059126, 1882200534, -445000810, -1043724234, 286670822, 833014730, -604147290, 15232061, -2110755194, 1892563034, -1713628270, -927576097, 307039790, -572677220, -249160516, 1329397811, 961826625, -1759899093, -1773224584, 1032246845, 1956755259, -2042255612, 1025643814, -512253584, -1718873372, 135035824, 628976003, 2002957939, -1874995262, 1352947368, 1297985339, 1647093287, -1272076082, 877061108, 184352706, -1188896535, 1884156523, -897297388, 66132067, 1687407124, -2096770669, 988185892, 181024408, 701890505, -931874221, -1371858374, -1261247076, -1659512078, 1269141880, 1415390482, -1702457025, 1328311171, 2020421002, 12404205, 1750987256, -1741458174, -1829014791, -1972279883, -1209162176, -1195495607, -2031779946, -1115459995, 1011125533, 1540804490, -790455996, -993483353, 356300284, -1218634348, -740502546, -335442498, 625670595, 258120020, -1634622789, -73633627, 1770426662, 1877275805, -1039284096, 678623608, -2057094086, 1058006315, -837592202, 880640019, -1204957369, 1429967588, -1104162772, 1610410744, 587479265, -1888672159, -1271709761, -951694475, -805350087, 426982317, -635871929, -1100376058, 265691824, -1106231988, -242757996, 1268721911, 396831661, 1916857214, -1458775015, -1845634227, -166839889, -1664248892, 847555624, 2041970151, -92691035, -1590117213, 700087647, 942370015, 353622397, 1292257703, -1312910238, 990609205, -305473798, -1937613910, -775892791, -64902482, -280438838, 1625256278, -1026876068, 578290169, 340679383, 1492618215, -1112133763, 780071188, 1276064477, -1334551499, 1332103653, -2067145747, -96900548, -488719375, -1610287469, -1549499572, -1167716338, -1588201682, -70784000, 1973375983, -1038007684, 649308707, 1210356118, 879690742, 834144845, 1458124591, -1705846941, -27385215, 1607457727, -1481631460, -2097588983, -749372009, -944451430, -1032415833, -1308105735, -9797047, 730394497, 637965376, -1536874272, 1177615127, -1286597494, -771973875, 510050400, 1308610705, 762924817, -2097069004, 1095959299, -1691439039, -29374263, 219645273, 983995500, -884163128, -28669421, -2055810203, -2134429233, -38882746, 1469296530, -946872183, -1653574750, 1672809983, -15407874, 1296523906, -239176044, -1508818886, 1933588793, -1318955234, 629514174, 526051692, -131489889, -1462530818, 48623640, 1035246486, 1136046753, -195922788, -84174035, -1353597718, -479229035, 731872655, 276157714, 916811956, 602194886, 1062896654, 871893908, 756853368, -1001655598, -644607310, 2075721392, 1153683286, -1187693003, 411729023, -15307705, 341477814, -195965408, 1989153572, 1728791313, 1549710112, -294896753, -1909981823, -1864265518, -658409365, 959531930, 238776938, -2141675572, 1485315097, -377975798, -400467030, -1794443404, -590611711, 1302439214, 340698442, -1150864280, -1314670802, 1200911599, 1260764435, -1890980961, -138826489, 1144997666, -1849686448, -59372318, 2062685871, 1011859229, 1458849240, 1795979386, 734364078, 1352156812, 797526602, 2063252522, 874150608, 1767708037, -1447799654, 1952721759, -1481403315, 266414041, -1812527924, 327665317, -638244310, 1715254188, -630665472, 400074333, -1323792162, 1611396423, 1941191853, -685384532, 135813687, -132226004, -321880527, 302645942, -1627620226, 825992554, -335277944, -441850612, -353785895, -342569165, 2034596699, 726467426, -1631877648, -2100440661, 937126717, 131192709, 943071187, 1525946626, -1016222672, 917182347, -1757034981, -361448252, -1781741459, -1926076597, 1653790543, -311046033, -1026666652, -823120625, 555813000, -1726240443, 1089997057, -1455456888, -1039657898, 1148988771, -1332438736, 934302466, 869135333, -829456365, -1284483165, -369523752, 2059994715, 1569627997, 103112658, -613471191, -613234044, 304465635, 80354627, 1779007179, -2131095887, 686402542, -129640437, 458436991, 65911516, 1406920387, 465765779, 257292390, 919050512, -172221125, 1659855263, -2012298060, 682672135, 1319682706, -1774840948, 2119875234, -934312940, -1637121922, -903846952, 652808873, -2096557501, 570072451, -1093810713, 1775065580, -1759569474, -1871055739, -1942210044, 420529653, 582231922, 496718238, -1540994139, -1923575900, -1119381519, -454604750, -1563676685, -693991069, 920929177, 678745663, 1766967432, -243768162, -297056010, -1087936263, 1454607993, 839735922, -1340696220, -1042795, 871410071, 230763427, -1033557000, 302522725, 489207794, -2084656173, 1297939105, -890759132, -1336931938, -31765519, -957534839, -1155520621, 1795511481, -1321183249, 436017344, 543912260, 4203947, 1186847671, -2066026468, -1633584203, -1405120593, 1043489631, 1518818650, -1345974369, 227860883, -1846408550, 212411528, 245962384, -1247911237, 952799090, -356048217, 747458231, -1518183317, 1776901171, 2098950795, 1382410238, -151325884, -1631339350, 405730310, -22520226, 1984402703, 808497807, 1755902277, -1833884307, 1822490297, -890823361, 379698809, 2072967483, 81338014, 2072651949, -208851015, -890116001, -828352759, -1768343654, 1203505446, 456682316, -193075973, -1808286460, 46255439, -1637475096, -987664597, 504674523, -1359049257, 812968031, -2037382834, -33502214, -631070123, 455786547, -116459624, -2126702764, 394029435, 699085463, 215195265, -562275730, 406747257, -2053280003, -1331262772, -1909258996, -1578181469, 1144295661, 622194116, -1788202961, 227955537, 1072776216, 1203923400, -32198082, -1404003322, -372173395, -117036278, 203735682, 424495315, -1022294294, 1005471891, -812392489, 1180872957, -1527892747, 1769648522, 410381984, -905254435, 1730718187, -1265030476, 1447805435, -1329796601, -1246123207, 9707582, -833059787, 1041382062, 1802508587, 1744195514, -922701184, -1236542650, -684018750, -1032810905, -1016029213, 1825520491, 1175541961, 2103390133, 1949545329, 173960961, -1326739670, 2019610631, 373609917, -1000537957, -968625283, -1773631558, 968081804, 933561888, -963814943, -556676507, -2105398324, -880387157, -67651313, 1998354018, -1323895099, 381954227, 1966092971, 844880013, -355146610, 1191383916, 698928349, -510941109, 272989377, 895272556, -1314279136, -190169139, -2011162255, -1225544560, 1043792985, 304583830, -25145508, 279709471, -906777557, 1714205754, 1562256733, -539114960, 1977259401, -78132889, -1752314077, -1994085559, 1613582476, 499445033, -1531715801, 2024468041, -896526970, -939767703, 804660187, 2124676231, 859342678, 1541556662, -1333746657, 90980922, -845822211, 1750004551, -562467080, 388255258, 237874289, 851281216, 343224963, 1558466375, 1557412017, -338294732, 1781124647, -871428758, 1696568601, 1638300651, 192631817, 1427750681, 1749824503, 863612516, -2937404, -57646464, -1159076259, -845807843, -1200072615, -1720419268, -1528562888, 386830993, -56956060, 1838047370, -385631327, -713704959, 1177837457, -1155044704, -1691494286, 1911001975, 788613197, -769276326, -946823908, 1557145095, -269454145, 585674777, -100533320, -1438613929, 716090361, 835604200, -2127968677, 1272614754, -1414170518, -1455780641, 1980082605, 798219128, -1363757417, -1014459956, 320453820, 1879779720, -2035950838, 1086768143, -931546611, 472763041, -1455742070, -1615367228, 402929140, 481113014, -1025759349, 1284412455, -1863686619, -1634865247, 379091944, 2089232180, 3427978, -1490735766, 1839226319, -235847794, -157653162, 258633416, -712599300, -2096907103, 1208684633, -556328217, 1946033449, -188013302, -406624874, -1587152533, -1932069180, 759251765, 306727186, -320808524, 856006370, 1915709511, -1106922002, 1741351523, -356854157, 137853247, -920145737, -1675983587, 541163703, 478030423, -526292739, 165507726, -658820880, 640879792, 244080674, -435230031, 1848336217, 1910067757, -1236096653, -661203635, -1161004714, 150891422, 1354012540, -975302974, 2141798636, -1002838751, -638883177, 618378501, 1932013426, -853269308, -835726138, -1103380248, -1797402744, -794300561, 235169474, -1535152226, -1344912824, 1777129472, -1324271021, 872169598, 1523934139, 290913463, -580948510, 1822853895, -99597681, -335890731, 781731148, -1159663325, -287711482, -324460417, 785712120, -2007354960, 451437872, -1432054553, 1170854955, -1231610053, 1970755163, 1633324716, 1424445338, 2053029646, -1411492406, -1703769983, -860652224, 1041945708, -1669624666, -698891251, 1247041650, 161438746, 357292337, 157162258, -111987409, 66042913, 1048198465, 1124089552, -566127172, -1883198510, -808239125, 1136134571, 2019378544, 568465418, -442485123, -86522101, -1948594996, -1582528585, 2033821874, -623536765, 1901761230, 188859546, 450839584, 99108660, -1703002234, 1378405454, 811012852, -1998101389, -1931922455, -1798746744, 1170008546, 357971113, -321901852, 2127246751, -1224326826, -140775045, 782849972, -173862321, 1615719919, -773224406, -1773169292, -1881388103, 205417517, 24087867, -1688175625, -515999059, -366431384, 2022524506, -398037545, -738500820, -1950301181, 1607200379, -1382222898, 1575435048, 1415079138, 1996986433, 674167108, 680891789, 604226584, 442061475, 348372520, -934237820, -1751453979, 23884748, -1964469758, -259914251, -565816097, 1982017091, -734876599, -2004410034, -982267282, 1728894028, 1633007089, 1918166403, -940261764, -1787662963, -551495608, 1492744277, 735942509, 1139049203, -1673698046, -1740913707, 1204382541, 1937720534, 984050578, -1534295253, 312772424, -1983352998, -292958278, -1284188269, 206797406, 1767674137, 78427493, 1827318184, 817076054, -1026058242, -566340172, 1437817573, 214770163, -205600653, 464228694, 1585548135, -1226925211, -588217666, 96392220, -1962739721, -2006195710, 58751656, -393142837, 870298696, 888346677, 1143817567, -1606269900, -1090763396, -1953200458, -1123655267, -114638206, 1315201260, -1390809605, 279453192, 1032497618, 1616663336, 1167915757, 753205724, -1361148152, 1987269436, -522988833, -1844798522, 574378464, -430881227, 1694886587, 577362707, 1118288195, 161396451, 1109040510, -1851173111, 1802395867, 856557023, -1017760283, 317335701, -997071895, 2037978575, -93233304, 976108069, -2058440363, 1870067688, -452840857, -1560727081, -1976822522, -503227212, 686641059, -1307354669, -437058956, 1677315349, 889765615, 887630580, -1263635334, -1428492407, -813595354, 477126061, 1186035312, 48389550, 1865426271, -1506695894, 348924537, -1698443768, -417889953, -505644875, -946183912, 1354667522, 1594674511, 934448987, -1217686007, -2131048398, -1187083602, -647564849, -2115148210, 396587745, -180633976, 1993524877, -742468729, -1668824375, -310651161, 669531202, 262400134, -630911456, -1216679030, -536922518, -1468624094, 899156949, -1350203948, 1915592762, 2003486539, 1293138713, -1148617721, -585659967, 319373151, 1902165792, -218993743, 1287746377, -1113231941, 810562344, -1342607514, -1263441149, 1363702675, 1161378490, 539536302, -1437474590, 341061894, -850865617, -245518527, -111979322, 1790886508, -1847614603, 1704272497, 1744323293, 1157103346, 2020729618, 1300068839, 168358470, 881839209, -602310295, 2138415249, -52229642, 2026724442, 1900739644, -512242470, 1072893919, -1076582819, -870171534, 130020636, -1054591410, -185027670, 767781913, 1929418578, 1991580564, 1202622448, -1717952339, 1190119442, 900095976, -1182928027, -1609583206, -1071530823, -1209911924, 1636432414, -840510721, 231032039, 898256685, 857570464, 1308761268, -2077628626, -204746609, 1196154294, 1396198798, 1463719173, -9493143, 1500537220, 557335265, 1538468354, -598482291, -1872535076, -1700545467, 1364601416, -1821960885, -1545735217]
Sorted array: [-2146635344, -2144909783, -2144793482, -2144682679, -2142614419, -2142565926, -2141675572, -2139206528, -2138223720, -2137718420, -2137280065, -2137041456, -2136364559, -2136200785, -2135625893, -2135140291, -2135130918, -2135122655, -2134429233, -2132803183, -2131827236, -2131534082, -2131095887, -2131048398, -2130989740, -2127968677, -2126702764, -2126692026, -2125639976, -2125546881, -2124725411, -2124374514, -2123733164, -2121443282, -2118068105, -2115654424, -2115244501, -2115148210, -2114235672, -2111976798, -2111679274, -2110755194, -2109350202, -2109231114, -2107592220, -2107457872, -2107132194, -2107109904, -2105462221, -2105398324, -2101617641, -2101449446, -2100440661, -2099251499, -2098391859, -2097688451, -2097588983, -2097069004, -2096907103, -2096770669, -2096557501, -2096151917, -2096071430, -2094530459, -2092863943, -2091776948, -2091129487, -2090604112, -2089910334, -2089246053, -2086498080, -2085139957, -2084762205, -2084656173, -2084286971, -2083255071, -2081713472, -2078596332, -2078417865, -2077628626, -2077489339, -2077175056, -2077046390, -2075974313, -2075887251, -2075756754, -2072758307, -2070430317, -2070373766, -2069210197, -2068518141, -2068100051, -2067145747, -2066026468, -2065578453, -2063959834, -2061863960, -2061610177, -2059350309, -2058440363, -2058168666, -2057094086, -2055875368, -2055810203, -2053742656, -2053280003, -2053217336, -2052270711, -2050811831, -2049139448, -2048907818, -2047778600, -2046280017, -2046215601, -2046143031, -2045870030, -2044343937, -2042764380, -2042337348, -2042255612, -2042048311, -2040698112, -2039626479, -2039338729, -2038462192, -2037382834, -2037027284, -2036703005, -2036449958, -2035950838, -2035389166, -2034090290, -2033088469, -2032375363, -2032186398, -2031779946, -2028654520, -2028156802, -2027969998, -2027968140, -2026854045, -2024928221, -2024713190, -2024455393, -2024436176, -2022769519, -2022290531, -2022065026, -2021628305, -2021442180, -2020770536, -2020010326, -2019247339, -2017072695, -2016787002, -2016316579, -2014403333, -2013593924, -2013289379, -2012958062, -2012298060, -2011162255, -2010894746, -2010282672, -2007862232, -2007354960, -2006924887, -2006195710, -2005776348, -2004549797, -2004517238, -2004410034, -2002741930, -2002143204, -2001518734, -1998678720, -1998545925, -1998101389, -1997157718, -1996812203, -1995772606, -1995046761, -1994523274, -1994085559, -1993499115, -1992523123, -1991330245, -1991218269, -1991186462, -1989818486, -1988586400, -1988329432, -1988063523, -1987713502, -1987061672, -1986715871, -1986023529, -1984082906, -1983439689, -1983352998, -1983207430, -1982694465, -1980292321, -1979617074, -1978347204, -1976822522, -1976157828, -1973259505, -1972279883, -1967703259, -1967259877, -1965685689, -1964469758, -1962739721, -1960380898, -1956263658, -1954783340, -1954394244, -1953200458, -1951530459, -1950631724, -1950529150, -1950503576, -1950301181, -1949735372, -1949568561, -1949405648, -1948594996, -1948457315, -1947928716, -1946692746, -1944674854, -1944158798, -1942210044, -1941202154, -1940984926, -1939952580, -1939715696, -1939159681, -1937613910, -1932069180, -1931922455, -1931581496, -1931036584, -1929474725, -1928633529, -1927953733, -1927834170, -1926076597, -1925956924, -1924335749, -1924301575, -1923935062, -1923575900, -1922655188, -1921873284, -1921190463, -1920603496, -1920593565, -1919625385, -1919316472, -1918808789, -1918751838, -1917843884, -1917728399, -1917403738, -1917043809, -1915707539, -1915367596, -1914810545, -1914303020, -1914101524, -1912112466, -1911855718, -1909981823, -1909258996, -1908442464, -1907974162, -1905599715, -1904739979, -1904171817, -1903852078, -1902949825, -1902291657, -1900658628, -1899292436, -1896914398, -1896160658, -1890980961, -1888672159, -1888385522, -1884500180, -1883198510, -1883017615, -1881758498, -1881388103, -1881091649, -1880425393, -1880296120, -1879051016, -1877898770, -1877647597, -1877076368, -1876270435, -1876189778, -1875653698, -1875319735, -1875011095, -1874995262, -1872821690, -1872535076, -1871055739, -1870512820, -1869645169, -1869482591, -1866231385, -1865514377, -1865125329, -1864784155, -1864724407, -1864265518, -1863686619, -1862429808, -1861800068, -1859735183, -1859562991, -1859239308, -1857293627, -1855267628, -1854509680, -1854324419, -1853746707, -1853137399, -1851173111, -1850799688, -1850542596, -1850384471, -1849734005, -1849686448, -1849504082, -1847614603, -1846408550, -1846140921, -1845634227, -1845086593, -1844798522, -1844747342, -1844684261, -1842721912, -1841965194, -1840423148, -1839471036, -1837070287, -1836324281, -1833884307, -1832492991, -1832481472, -1832407124, -1831964248, -1831790774, -1829690947, -1829652227, -1829014791, -1828806688, -1826183058, -1825434093, -1824736976, -1823161120, -1822998809, -1822265725, -1821960885, -1820717061, -1820568353, -1819921323, -1818923278, -1818300326, -1817576268, -1817289497, -1817073437, -1817004064, -1816947848, -1815987582, -1814865417, -1813381615, -1812527924, -1809195351, -1808286460, -1806483375, -1805557606, -1805363354, -1805020484, -1803853052, -1801786781, -1798746744, -1797661523, -1797402744, -1797078113, -1795964700, -1795864353, -1794443404, -1793507433, -1792214779, -1792023424, -1790859018, -1790294946, -1788684467, -1788202961, -1787662963, -1785584750, -1785350167, -1784739085, -1782934489, -1781741459, -1779796266, -1777527439, -1776980208, -1776596298, -1774886275, -1774840948, -1774832510, -1773662548, -1773631558, -1773224584, -1773169292, -1768629661, -1768343654, -1765418333, -1764917623, -1763572783, -1760197684, -1759899093, -1759569474, -1759416938, -1759013552, -1758340979, -1757959354, -1757034981, -1756647000, -1756428070, -1755312595, -1752496618, -1752314077, -1751453979, -1749103870, -1748856691, -1748588874, -1748186282, -1747673205, -1747430967, -1747280858, -1747015398, -1746351041, -1746064571, -1744802494, -1744801955, -1744577836, -1743506468, -1742713471, -1741487195, -1741458174, -1740913707, -1739476041, -1737241665, -1736317872, -1728847975, -1728823365, -1727478162, -1726681257, -1726240443, -1726031800, -1724549777, -1723872231, -1723707413, -1722314385, -1720419268, -1718873372, -1718821187, -1718375166, -1717952339, -1716356385, -1714734295, -1713628270, -1712025903, -1711658379, -1711360075, -1711325033, -1710663563, -1710166477, -1709428027, -1708430014, -1707431899, -1705846941, -1705809141, -1703769983, -1703136066, -1703002234, -1702457025, -1702351059, -1701357244, -1700545467, -1700172461, -1698480535, -1698443768, -1696215458, -1695048319, -1694214493, -1691626823, -1691494286, -1691439039, -1691205128, -1691171711, -1689821538, -1689680495, -1689651523, -1688727181, -1688624891, -1688175625, -1687547752, -1686515701, -1684850394, -1684374432, -1682431092, -1682211404, -1681683120, -1680471021, -1680091142, -1679856412, -1678451754, -1677892420, -1676391738, -1676333365, -1675983587, -1675543452, -1673698046, -1673055418, -1669624666, -1669355967, -1668824375, -1668246059, -1667232501, -1666758833, -1665696040, -1664912392, -1664248892, -1661791283, -1659609832, -1659512078, -1657264756, -1656650995, -1654680546, -1653574750, -1652978640, -1652965555, -1651823016, -1651805497, -1651376244, -1651042249, -1650720003, -1649699256, -1649188996, -1647992348, -1647658890, -1642916400, -1641576937, -1639766205, -1638720587, -1638324076, -1637810500, -1637475096, -1637150032, -1637121922, -1636526826, -1636219606, -1636197030, -1635098105, -1634865247, -1634622789, -1633584203, -1632436291, -1631899761, -1631877648, -1631664100, -1631339350, -1628159036, -1627620226, -1625077723, -1624345185, -1623550807, -1621687439, -1621639229, -1620526687, -1619639428, -1619137594, -1618920095, -1615367228, -1615186629, -1614970459, -1614812116, -1612183519, -1611568325, -1610287469, -1609583206, -1609229969, -1606269900, -1605459777, -1605037155, -1604344910, -1604343289, -1602513260, -1601379991, -1601155233, -1600766527, -1600647259, -1599159614, -1598535225, -1598232629, -1598204571, -1596783189, -1596429529, -1595052917, -1594679193, -1592849811, -1592778607, -1590117213, -1588646728, -1588386565, -1588201682, -1588042619, -1587620208, -1587152533, -1584750377, -1582528585, -1581696835, -1580643129, -1580588490, -1580100012, -1580027175, -1578277646, -1578181469, -1577324212, -1571873945, -1571031829, -1570617205, -1570412116, -1569376343, -1567016759, -1566614583, -1565797377, -1564921537, -1564795840, -1563676685, -1563660744, -1562543894, -1560727081, -1560461827, -1559246649, -1558982389, -1558934056, -1558869140, -1557465986, -1556955828, -1556868038, -1554457864, -1552622295, -1552330495, -1550425838, -1550356590, -1550335597, -1550319421, -1549499572, -1546799435, -1546473011, -1545735217, -1544960321, -1544949230, -1544737240, -1542831877, -1542309705, -1542067743, -1541446732, -1540994139, -1539907501, -1539241861, -1538585582, -1537178038, -1536874272, -1536627876, -1536588574, -1535926054, -1535385743, -1535152226, -1534771265, -1534295253, -1533477923, -1533464334, -1533389908, -1531715801, -1531504686, -1529197745, -1528562888, -1527892747, -1526163030, -1525770136, -1525278298, -1524841867, -1524626759, -1523850489, -1522982400, -1522198298, -1521095642, -1520794481, -1520112510, -1518760703, -1518183317, -1515133502, -1514998436, -1513018149, -1511820020, -1509879034, -1509496003, -1508818886, -1507933908, -1507774341, -1507368454, -1506722900, -1506695894, -1506447788, -1505484903, -1505322537, -1505008674, -1504340446, -1501271452, -1497868893, -1497721321, -1497247692, -1496054879, -1495689017, -1495337676, -1495069393, -1494588493, -1493473503, -1492475204, -1490735766, -1488933302, -1488546175, -1487779257, -1486596771, -1486335689, -1485761847, -1481631460, -1481403315, -1481370241, -1480030887, -1479773326, -1476916460, -1475287846, -1474607858, -1474202403, -1473907953, -1473748548, -1472851395, -1470937713, -1470558252, -1469830832, -1469741477, -1469590455, -1469145904, -1468624546, -1468624094, -1465263428, -1463376835, -1462881039, -1462530818, -1462166711, -1461321610, -1461066921, -1460873368, -1459683804, -1459531980, -1458906166, -1458775015, -1457320783, -1456488000, -1455889750, -1455832073, -1455780641, -1455757621, -1455742070, -1455456888, -1455299009, -1454901660, -1454670325, -1453912412, -1453893526, -1453522856, -1451758566, -1450551575, -1449816966, -1449549471, -1448319084, -1447799654, -1447795661, -1447607509, -1447505824, -1447459288, -1446689239, -1446171696, -1445286095, -1444286133, -1442041602, -1439560354, -1439173239, -1438613929, -1438601413, -1438443858, -1437474590, -1436463884, -1436213585, -1434739854, -1434693315, -1432978320, -1432436903, -1432054553, -1431875376, -1429550669, -1429443117, -1428492407, -1428091568, -1425448207, -1425378062, -1425260669, -1425121410, -1424862062, -1424791084, -1424666069, -1424375356, -1424149715, -1423547482, -1422896004, -1422802412, -1422782003, -1421499403, -1421298254, -1420450804, -1420280478, -1417218955, -1415710488, -1414723591, -1414402360, -1414170518, -1412445797, -1412059126, -1411750461, -1411492406, -1411222744, -1410453610, -1408691188, -1408280611, -1407821862, -1407320199, -1406832981, -1406440807, -1405120593, -1404947311, -1404635862, -1404003322, -1403878212, -1402339687, -1401320285, -1400895746, -1398267016, -1397701116, -1394722177, -1392725983, -1392253724, -1391029453, -1390809605, -1390309374, -1390063545, -1388452158, -1387621635, -1386971624, -1386926125, -1384369868, -1384344599, -1384253487, -1384200496, -1384115182, -1382304741, -1382222898, -1381031081, -1380226249, -1378329489, -1374966354, -1373428806, -1373377221, -1372446433, -1372026272, -1371858374, -1371602912, -1370013475, -1369737134, -1369310137, -1369190697, -1368763596, -1368456857, -1366280288, -1363757417, -1362326249, -1362031787, -1361148152, -1361052180, -1360954598, -1360536653, -1359049257, -1357276316, -1356690067, -1356490487, -1355565571, -1355283965, -1354888384, -1353597718, -1353547036, -1353289191, -1352925327, -1352610338, -1350203948, -1349646144, -1347598753, -1345974369, -1344912824, -1344038400, -1343333061, -1343301472, -1342607514, -1340851281, -1340696220, -1336931938, -1336906150, -1336860378, -1336804616, -1336679929, -1334551499, -1333746657, -1333619671, -1332438736, -1332423043, -1331992959, -1331262772, -1329796601, -1329250065, -1329003075, -1328655496, -1328471971, -1326739670, -1326498996, -1326376076, -1325943249, -1325815946, -1324271021, -1323895099, -1323792162, -1321183249, -1319928796, -1319509101, -1318955234, -1318571162, -1318513851, -1318209299, -1317494931, -1317051852, -1315440468, -1314670802, -1314279136, -1313105639, -1312910238, -1312132910, -1310412294, -1309356555, -1308105735, -1307354669, -1306536152, -1306536103, -1306420107, -1306135380, -1305538026, -1305510695, -1303683253, -1301469342, -1301302095, -1301158754, -1298778419, -1298526288, -1297735956, -1297084136, -1296952427, -1294836296, -1292329201, -1291317703, -1289739406, -1288458202, -1286597494, -1286080330, -1285183628, -1285100569, -1284483165, -1284188269, -1283112784, -1282934956, -1282895713, -1282732182, -1280358417, -1279902934, -1279574588, -1279347296, -1276995144, -1276959942, -1274184143, -1272752524, -1272265166, -1272087435, -1272076082, -1271709761, -1270114727, -1269437337, -1267800138, -1267432423, -1266961616, -1266106139, -1265169586, -1265030476, -1263635334, -1263441149, -1262126658, -1261247076, -1260043287, -1258283602, -1258142132, -1254859022, -1254474998, -1253920482, -1253896518, -1253663911, -1251734868, -1250411134, -1249472768, -1247911237, -1247494506, -1246123207, -1245896149, -1244972456, -1243094804, -1241623710, -1240559780, -1237564043, -1237140492, -1236933554, -1236542650, -1236096653, -1235543952, -1234490116, -1233478364, -1231692118, -1231610053, -1229783158, -1229365473, -1227239408, -1227141514, -1226925211, -1226353635, -1225977987, -1225544560, -1224326826, -1223733929, -1222746849, -1221269612, -1221169567, -1220848218, -1220107841, -1219859704, -1219043194, -1218634348, -1217883697, -1217686007, -1216679030, -1216395031, -1214633602, -1212785695, -1211718353, -1211433811, -1209911924, -1209712886, -1209162176, -1208059030, -1204957369, -1204690107, -1204504502, -1202591282, -1201813012, -1201571903, -1200072615, -1199286847, -1198636889, -1195495607, -1194637596, -1194186503, -1193078969, -1188896535, -1187693003, -1187083602, -1186334124, -1185366089, -1184734200, -1183200463, -1182928027, -1182434426, -1181439558, -1181019779, -1180008085, -1179217605, -1179077063, -1178748715, -1177629400, -1176755151, -1175955468, -1175754513, -1174796405, -1174080941, -1173542573, -1171399135, -1167716338, -1167496548, -1166934842, -1166177998, -1163846207, -1163350672, -1161004714, -1160298282, -1159926289, -1159663325, -1159076259, -1158949927, -1155520621, -1155044704, -1152803051, -1152397536, -1151290648, -1150864280, -1150578679, -1149505649, -1148617721, -1148129869, -1146683852, -1146625626, -1146163328, -1145737597, -1145705726, -1145636888, -1145113249, -1144872844, -1143239624, -1142251696, -1141646367, -1141396924, -1138879021, -1138515217, -1138041854, -1137952667, -1137085351, -1136783604, -1136344628, -1135739125, -1135713401, -1132053727, -1131826103, -1130969556, -1130668323, -1130447695, -1129088439, -1127622139, -1127207990, -1123655267, -1123283067, -1119912161, -1119540967, -1119381519, -1117066048, -1115459995, -1114413157, -1113764926, -1113291372, -1113231941, -1112133763, -1110280205, -1108825486, -1106922002, -1106794478, -1106231988, -1105473202, -1105080531, -1104322725, -1104209491, -1104162772, -1103464937, -1103380248, -1103340378, -1100399538, -1100376058, -1097208357, -1097191410, -1095727231, -1095615329, -1095507649, -1093868216, -1093810713, -1093741765, -1093478819, -1093376712, -1091715769, -1091065942, -1090763396, -1090020774, -1089340820, -1088466948, -1088355636, -1087936263, -1087888533, -1087362408, -1087064220, -1085366383, -1085269344, -1084743935, -1084698170, -1081925421, -1080429277, -1079865710, -1079071045, -1078617331, -1078060078, -1077061002, -1076582819, -1075248174, -1074332201, -1074278767, -1072749458, -1071907948, -1071530823, -1071431283, -1069890966, -1067931411, -1066830945, -1065658336, -1064739901, -1064396367, -1063758976, -1061948743, -1061252084, -1060980708, -1059243750, -1058874428, -1057635011, -1056900036, -1055354194, -1055279364, -1054591410, -1053251421, -1052869002, -1048721504, -1046688796, -1046176051, -1045312235, -1044585925, -1043724234, -1043139278, -1041356381, -1039657898, -1039284096, -1039128736, -1038692841, -1038007684, -1036528619, -1034497474, -1033838563, -1033682366, -1033557000, -1032810905, -1032415833, -1032022399, -1031855960, -1031572818, -1031366455, -1031145174, -1031026588, -1030952788, -1030914958, -1030367143, -1029903001, -1027404834, -1026876068, -1026666652, -1026058242, -1025882027, -1025759349, -1025400287, -1023908891, -1022294294, -1020736697, -1019289655, -1017922333, -1017861842, -1017760283, -1017564167, -1016698490, -1016222672, -1016029213, -1015887723, -1015872310, -1015553295, -1014511683, -1014459956, -1011001505, -1010146003, -1008799898, -1007423065, -1002838751, -1001773967, -1001655598, -1001349130, -1001036398, -1000832277, -1000537957, -999208601, -998616798, -997071895, -996754758, -996577945, -996389323, -995599115, -993629083, -993483353, -993103479, -992320336, -991488952, -989850183, -989571705, -988790541, -988667000, -987664597, -987643442, -987145339, -986787991, -986626560, -985620368, -984749814, -984058474, -982267282, -981674606, -979850354, -978971585, -977311192, -976383698, -976142384, -975910749, -975302974, -974672646, -974523937, -973124785, -972592645, -972063613, -970902909, -970561118, -970153040, -970043610, -969111696, -968625283, -968550805, -966852783, -966827792, -965395394, -965378184, -963814943, -962929199, -962861478, -962660676, -960989243, -959179134, -958691644, -958554567, -958079986, -957855797, -957534839, -956988547, -955003704, -953492578, -951694475, -950949057, -950035487, -949923774, -949780414, -949550430, -949031881, -948503077, -948005701, -947630287, -946974189, -946872183, -946823908, -946651049, -946183912, -945423088, -944451430, -942020742, -941387187, -940825155, -940586102, -940399696, -940261764, -939767703, -939705784, -937394782, -936797870, -934312940, -934237820, -933332188, -932804649, -932710787, -932244897, -931874221, -931546611, -927758273, -927576097, -925944912, -922701184, -922323384, -921034923, -920362979, -920242185, -920145737, -919553769, -918364793, -917749809, -916761021, -916399948, -914549956, -913210477, -910776670, -910624908, -910364710, -907651764, -906777557, -905254435, -903846952, -903063808, -901571283, -900681898, -899414270, -899277729, -898151896, -897297388, -897139048, -896691130, -896526970, -895928179, -894624191, -894229424, -893910915, -890823361, -890769120, -890759132, -890116001, -889343043, -889074853, -887975343, -886303795, -885971060, -884358456, -884330933, -884163128, -883828042, -882295620, -882100849, -882100082, -880387157, -879190322, -876968791, -875668178, -875526708, -873276402, -873232771, -872058012, -871533071, -871428758, -871342139, -870171534, -868867235, -867110394, -866783917, -863965714, -863862821, -863642680, -862593118, -860652224, -859137754, -859034187, -858076570, -857462621, -857015383, -854655428, -853651450, -853269308, -851549296, -850865617, -850666733, -849482967, -846862786, -845822211, -845807843, -845700891, -845258537, -841934332, -841385654, -840650774, -840510721, -839106176, -838352110, -837592202, -837121194, -835726138, -834685878, -834110039, -833230846, -833059787, -833028144, -831984148, -831972694, -831666419, -831055198, -831042743, -830802239, -830443472, -830432992, -829456365, -828975277, -828897560, -828875742, -828352759, -825633156, -823538786, -823120625, -818877389, -818096783, -817284659, -816446375, -813595354, -813049326, -812392489, -810310121, -809515087, -808239125, -806835934, -805529873, -805478611, -805350087, -805127279, -805002046, -802380238, -802370392, -801765382, -800919449, -800463143, -800146335, -799724978, -797701536, -794810113, -794300561, -794277054, -793963873, -793516919, -792801205, -791066209, -790455996, -790050663, -790009793, -789202526, -788708289, -788434036, -786033731, -785405901, -785262046, -784556640, -784038373, -783735179, -782699103, -782251596, -782182509, -781076628, -780990956, -778625286, -777573451, -777567872, -776670219, -775934488, -775892791, -775030391, -773224406, -772627179, -772224873, -771973875, -771777949, -771572834, -769276326, -766954715, -764658773, -762304676, -762258321, -760283573, -758476232, -757056832, -756722763, -754491719, -754212224, -753466265, -749458480, -749372009, -748379081, -743989833, -742468729, -740669103, -740502546, -738500820, -738355452, -737363992, -736534147, -736340590, -735292539, -734876599, -734269571, -733437195, -730369209, -730156611, -729954121, -729363873, -728776367, -727754706, -726027548, -725708793, -724990031, -724424962, -724331384, -724146828, -724111050, -723578971, -722886120, -722509033, -721571168, -720446900, -716337933, -715307793, -715295087, -715079615, -714738318, -713868252, -713704959, -713418420, -713234460, -712599300, -712454975, -711846569, -710591718, -708381950, -705159707, -704201270, -703694637, -700457889, -699986649, -698891251, -697425878, -697076881, -697032314, -696877035, -696845091, -696335016, -695562414, -694591018, -693991069, -693002230, -692903251, -691271253, -685803140, -685384532, -684393855, -684147119, -684018750, -683198018, -682482761, -682200204, -681929187, -680998431, -680832059, -678571838, -678195163, -676691894, -675190012, -674503476, -674254058, -673963034, -671707241, -670755033, -670554876, -669584807, -665630902, -665335676, -664704667, -663675405, -661203635, -660997710, -660129872, -659934126, -659853739, -658910350, -658820880, -658632202, -658409365, -657113594, -656749682, -656661881, -656083903, -654663453, -652346630, -650133399, -649748999, -649376697, -648647862, -647564849, -645883866, -644607310, -644295652, -644222054, -643168335, -640790485, -639693681, -638883177, -638244310, -636109509, -635871929, -633668940, -631652893, -631552304, -631070123, -630911456, -630665472, -629571740, -628926547, -626077916, -623536765, -621490855, -621468146, -620262303, -617398602, -617160257, -617065815, -616840138, -616828152, -616508826, -616413522, -615281664, -615067293, -613471191, -613234044, -613063217, -609959647, -609624137, -606925383, -604394800, -604147290, -603725913, -603234470, -603157629, -602310295, -602199007, -601796646, -601318581, -599388480, -598482291, -598012631, -595357356, -593338074, -593104321, -593007827, -592933623, -592734450, -592415984, -590972395, -590611711, -590107362, -589477399, -589169534, -588217666, -587515236, -587186283, -586448903, -586361276, -585659967, -585238608, -582434521, -581159357, -580948510, -580648386, -579845223, -578985917, -576802091, -576656834, -576454659, -575157462, -574245863, -573735845, -572677220, -572012498, -571383503, -571086868, -568667909, -566340172, -566194785, -566127172, -565900720, -565816097, -564712722, -564066929, -563771070, -562467080, -562275730, -561202786, -560553466, -558337563, -556676507, -556328217, -554741769, -552744029, -551495608, -551448760, -550592811, -550392139, -549853705, -547001876, -545031309, -541938460, -540250053, -539333666, -539231951, -539170179, -539114960, -536922518, -536750907, -535288136, -534931332, -534829458, -534624722, -532847707, -532481097, -530012043, -529899420, -529755985, -528298919, -527450943, -527109039, -526292739, -523907468, -523714513, -522988833, -522515701, -520876406, -520543986, -519491643, -516960462, -515999059, -515995370, -515921846, -514943193, -514774974, -512459717, -512253584, -512242470, -511568632, -511132570, -510941109, -509642928, -508409103, -507385370, -506828553, -506174503, -505969031, -505941696, -505644875, -503227212, -502923399, -502442837, -499606093, -495882014, -494905395, -493296052, -488719375, -484829581, -482969511, -481423688, -481331020, -481268407, -480803425, -480480199, -480409176, -479287400, -479229035, -479180312, -478665078, -477457196, -476679840, -472692078, -472320839, -471199312, -471096991, -470615649, -469853012, -469567546, -469425201, -465669365, -464672633, -462853086, -460930701, -459800223, -458462049, -458079499, -457602843, -457134858, -454838266, -454604750, -453860593, -453663639, -452874079, -452840857, -451178393, -450992498, -450789688, -450717499, -449843268, -449747028, -449434388, -448506818, -448237624, -448094124, -446728060, -445883288, -445553219, -445000810, -444507285, -444398996, -443641495, -442485123, -441850612, -441771938, -441516216, -441300918, -440903169, -438362953, -438359773, -437844346, -437411305, -437058956, -436894033, -435230031, -434454316, -433807793, -432071902, -431151207, -430881227, -430397601, -430155513, -430103488, -429963029, -429270906, -428467021, -427526365, -427137814, -425240814, -422689518, -422681176, -421539762, -420564753, -418748758, -418365044, -418271196, -418092437, -417889953, -417661553, -417170790, -413119425, -412224377, -411641605, -411629262, -409528637, -409056784, -406624874, -406503818, -405278549, -404926810, -404401745, -403778733, -403367957, -403362712, -402842861, -402727661, -402469344, -401708840, -400467030, -399819722, -398545540, -398268402, -398037545, -397790000, -397647599, -396783775, -394012622, -393412727, -393142837, -391496226, -391297044, -390911521, -390909962, -390698386, -388448552, -387141252, -386513988, -385631327, -383385755, -382575666, -382568743, -380558644, -377975798, -376863547, -376722774, -376357991, -375690340, -375509318, -374844872, -373576054, -373331353, -372173395, -371980637, -371795617, -371637156, -370296403, -369523752, -369306110, -367760323, -367476127, -366431384, -366402201, -366002138, -365909137, -365491627, -364261528, -364027441, -362049431, -361991999, -361448252, -360503242, -358012800, -356854157, -356808788, -356391768, -356048217, -355434486, -355419940, -355416217, -355313026, -355146610, -354565340, -354391782, -354133082, -353916939, -353785895, -353669292, -353226794, -351581473, -351367643, -350204273, -349598523, -349375889, -348651550, -347873867, -346133411, -343510965, -342569165, -342514229, -342504025, -340820242, -338294732, -337975322, -335890731, -335588350, -335582553, -335442498, -335396477, -335277944, -333781563, -326601625, -324684997, -324460417, -322609802, -322551608, -321901852, -321880527, -321234769, -320808524, -319863621, -319083363, -318493360, -313975674, -313571108, -313276429, -311182843, -311046033, -310806957, -310651161, -310007941, -308263620, -307632445, -306073959, -305473798, -300807763, -300584889, -300068990, -298947145, -298874715, -298556557, -298481898, -297979348, -297056010, -296870904, -296155134, -295147962, -294896753, -292958278, -292937365, -292239885, -291456005, -290820178, -287711482, -286591280, -285174171, -283603123, -283118110, -280438838, -280152984, -277357235, -275773931, -275099974, -273606608, -273533725, -270940457, -270763300, -269960300, -269454145, -269176700, -268704109, -268594863, -268234414, -266717038, -265959733, -265440920, -265438978, -265418714, -264377176, -262491939, -262064878, -260177187, -259914251, -254407964, -254312028, -253212450, -253005011, -252294715, -251837098, -250824193, -249892437, -249160516, -249056587, -248346509, -247557416, -246384606, -246369864, -245518527, -245097292, -243768162, -243519681, -242757996, -241125862, -240871203, -239538225, -239176044, -238962785, -238938240, -237068775, -235847794, -235811815, -234569455, -233605547, -232968913, -231025219, -230032934, -228309454, -228135586, -227553309, -225270430, -224326794, -222547501, -221058786, -220305509, -219715552, -219299897, -218993743, -216111852, -215724525, -215624155, -215018399, -214596189, -212594870, -212518289, -211328874, -211167717, -209892895, -208851015, -208266600, -207394460, -206858220, -206744654, -205600653, -204746609, -203279541, -200489666, -198215740, -198053808, -197459457, -196877240, -195965408, -195922788, -195176091, -194977098, -194770927, -194636437, -193672577, -193075973, -190169139, -189827646, -188338362, -188013302, -186740762, -185346564, -185027670, -184462207, -183818398, -180888866, -180633976, -179835955, -179197673, -178509677, -177069758, -176341382, -175948093, -175253062, -174648905, -173862321, -172221125, -169904074, -169416200, -168481195, -167164591, -166839889, -164123663, -163856294, -162206064, -160644987, -159413997, -159229860, -157817091, -157653162, -156888693, -153736122, -153126445, -153037477, -152680167, -152178401, -151325884, -149347444, -147135508, -147115898, -146870239, -145724985, -145420778, -142478512, -142162221, -142041384, -140957738, -140775045, -140319872, -140035093, -138826489, -134211330, -133149494, -132226004, -131489889, -130796638, -130361274, -130074369, -129958547, -129931896, -129647852, -129640437, -129498589, -127809824, -127338498, -123701810, -122672181, -121701758, -121649582, -121105668, -120930202, -117036278, -116691156, -116597561, -116459624, -115199133, -114638206, -112403766, -111987409, -111979322, -111944571, -110849903, -110838517, -110419121, -110089598, -109670226, -107962353, -104714584, -104543900, -103000724, -102552432, -102037697, -101406177, -100533320, -100112639, -100097946, -100009008, -99597681, -98472008, -97289571, -96900548, -96801910, -96525136, -94366695, -93917247, -93233304, -92691035, -92526601, -89803700, -89227374, -88389492, -87769289, -86752453, -86522101, -85926223, -84670572, -84226018, -84174035, -83916663, -82507020, -82422679, -80410275, -79522872, -78132889, -77275829, -76280025, -75247919, -73633627, -72703635, -71237226, -70784000, -70407836, -70332277, -70315680, -70127718, -69788881, -69756573, -69622711, -67852421, -67651313, -65576405, -64902482, -64458516, -63289993, -63062178, -62792725, -59372318, -58518593, -58461578, -57773503, -57646464, -56956060, -53899442, -53656116, -52934370, -52229642, -52209812, -51191305, -50395901, -49800622, -48468978, -48133382, -48000039, -47199126, -46750818, -45873407, -44843051, -44292418, -43690993, -42252642, -41554956, -40930430, -40027489, -38882746, -38541076, -36750956, -35745965, -33502214, -32198082, -31765519, -29374263, -28669421, -27385215, -27043805, -26627627, -26246516, -26108328, -25643424, -25145508, -23524893, -22520226, -19278793, -17279005, -16738129, -16404033, -15668398, -15493093, -15407874, -15307705, -15182344, -13106263, -12201264, -12051893, -9797047, -9552042, -9493143, -8779687, -7079308, -6797972, -5317550, -4678873, -2937404, -1042795, 294086, 528752, 860727, 1539981, 2305154, 2962784, 3427978, 4203947, 4413153, 5759257, 6270287, 7071136, 8012520, 9707582, 10077484, 10417168, 10749507, 12055681, 12404205, 14104496, 14222901, 15232061, 15240487, 17625275, 17638762, 19380260, 22355664, 22888878, 23008365, 23073497, 23884748, 24087867, 24370994, 26869851, 27983802, 28763172, 29041590, 29046798, 30996317, 32491913, 32598030, 32667514, 32950010, 34685710, 34765983, 35296159, 35351947, 35439115, 36094569, 37642405, 38483724, 38505068, 38642784, 39166552, 40117036, 40364112, 40394330, 40474960, 41050657, 42070423, 42882315, 43517249, 44585374, 44971574, 45767421, 46255439, 47482210, 48206381, 48389550, 48443207, 48532388, 48623640, 48820998, 48904298, 49872908, 51533645, 53133113, 54333132, 54442167, 56169643, 56790073, 58256083, 58751656, 59211435, 60738745, 63631122, 63772288, 65866030, 65911516, 66042913, 66132067, 67114281, 67720205, 73660911, 73838942, 74396298, 75111665, 76073176, 78427493, 80354627, 80452163, 81338014, 82177264, 82973601, 85274432, 85966043, 86545278, 86600718, 87564594, 88157552, 90698097, 90980922, 92346016, 94839471, 96392220, 98021803, 98352305, 98425780, 99108660, 99804049, 101108223, 102732257, 103112658, 104143187, 105249960, 105948266, 105965561, 107106187, 107373025, 107881828, 108118189, 108210567, 108607870, 109124047, 109898661, 110583363, 111146973, 111275147, 115060373, 120269787, 120630164, 121611220, 122131635, 123320106, 124007548, 125101308, 125816078, 126642012, 126933453, 127370321, 128719617, 129992844, 130020636, 131157197, 131192709, 132712275, 133041343, 134021171, 134344048, 134758937, 134845378, 135035824, 135716761, 135813687, 137078246, 137592765, 137731422, 137853247, 139464598, 139477841, 140583163, 140876537, 142048354, 146106233, 146444317, 147312612, 147361621, 147484449, 147618764, 148349517, 148667096, 149647415, 150485316, 150891422, 151603402, 153336517, 155201585, 156053419, 156671609, 157162258, 158588390, 158758920, 159510508, 161385811, 161396451, 161438746, 163308806, 164790515, 165158103, 165507726, 165516878, 166847684, 167043958, 168080421, 168358470, 170630984, 170912056, 171381129, 171527028, 171692412, 171796667, 172324127, 173259453, 173398365, 173751419, 173960961, 174021675, 174369441, 174541233, 175176675, 175199436, 178217930, 180129855, 180303851, 180762054, 181024408, 182961384, 184352706, 184608235, 188323346, 188859546, 189856825, 190428361, 192631817, 193256935, 195168699, 195545275, 196173193, 197673515, 197765335, 199051602, 199583811, 200366014, 200515547, 200749081, 200815732, 202103844, 203124507, 203735682, 205177592, 205417517, 206174232, 206797406, 210035555, 211065814, 211085953, 211667109, 212411528, 213255716, 214770163, 215195265, 216188314, 217539780, 217753877, 218617944, 219408407, 219625765, 219645273, 221969357, 222015808, 226761741, 227400917, 227763769, 227860883, 227955537, 228260405, 228308167, 228743590, 228833697, 228963087, 229011400, 230763427, 231032039, 233449532, 233472213, 234106574, 234651847, 235141462, 235169474, 236520355, 237253402, 237664467, 237874289, 238776938, 240448615, 240462022, 241855102, 242684092, 243600124, 244080674, 244980236, 245190255, 245699691, 245962384, 249531989, 249643407, 250617069, 251609608, 252008277, 252262212, 252735367, 253152238, 253802424, 254378824, 257292390, 258049851, 258120020, 258633416, 258885577, 260141840, 260930140, 262400134, 262481936, 265691824, 265709305, 265982703, 266267366, 266414041, 266873718, 267529501, 267667616, 268545280, 268645923, 270444668, 272989377, 273081736, 273275731, 274614791, 274830711, 275000839, 275442493, 276157714, 277558291, 279304856, 279453192, 279709471, 280218068, 280456109, 280986287, 282955520, 284164906, 284315570, 285587165, 286216833, 286228589, 286426358, 286670822, 287070697, 287154745, 289193101, 290298436, 290672041, 290913463, 292222995, 294043985, 295065482, 296433705, 296557249, 297159396, 297460543, 297469714, 298432383, 298971864, 299765938, 299972841, 300022678, 300250763, 301946559, 302522725, 302645942, 303269473, 303826758, 304465635, 304583830, 306727186, 307039790, 307050049, 307334970, 308662755, 310226373, 312263068, 312692019, 312772424, 313009622, 313069203, 315926813, 316360258, 317105372, 317335701, 319373151, 319679611, 320453820, 321767466, 323004478, 323580187, 324389161, 324613267, 324883412, 325168980, 325529089, 327269970, 327665317, 328874235, 329529980, 330154512, 330799382, 331236412, 332492361, 332570566, 333437593, 334081975, 334156530, 339312064, 339422092, 340227285, 340604946, 340679383, 340698442, 340973857, 341061894, 341477814, 341805801, 341936961, 342422503, 342999964, 343010194, 343224963, 343653937, 343845845, 348372520, 348924537, 350396270, 351563709, 351863344, 352009820, 352196516, 353622397, 354639597, 354786080, 355534982, 356300284, 357292337, 357338366, 357340186, 357670942, 357971113, 360604965, 360932434, 363967428, 365375915, 365626700, 365797338, 366743411, 369300339, 369352444, 370286497, 370552098, 370767066, 370966330, 371155366, 372764910, 373377318, 373609917, 373972022, 375200056, 375449843, 378010572, 378905279, 379091944, 379698809, 380375360, 381846289, 381954227, 386830993, 388255258, 388275335, 388464364, 388622499, 388885474, 389450104, 392422707, 393613392, 393682391, 393851194, 394029435, 394366529, 396205521, 396587745, 396831661, 396847414, 396946671, 397501802, 400074333, 400405858, 400828905, 400992480, 401788322, 402302009, 402929140, 403966535, 403998895, 404753956, 405730310, 406747257, 407454370, 409225179, 409975277, 410381984, 411729023, 412170664, 412322518, 413165032, 413484190, 413939545, 415152878, 417077769, 417101984, 419836517, 420529653, 421045696, 421849443, 424318033, 424495315, 424587286, 425242596, 425640282, 425960431, 426982317, 427159687, 427520931, 427875673, 428837570, 429097662, 433080905, 433257235, 436017344, 436184378, 436237771, 437209856, 439016279, 439912281, 440165591, 440643794, 441620021, 441652995, 441967273, 442061475, 443324184, 444669381, 445900871, 446493100, 446709777, 446797121, 447058080, 448390230, 449592291, 450403090, 450839584, 451437872, 455786547, 456471672, 456682316, 457005128, 458436991, 458729146, 459044858, 460000922, 460485995, 462406131, 464084883, 464228694, 465765779, 470064853, 470887049, 471848168, 472763041, 473058355, 473823833, 474942085, 475469411, 475740266, 477126061, 477370256, 478030423, 480428415, 481113014, 483548121, 484197932, 485124286, 486281947, 486848056, 489207794, 491224589, 493269072, 494005803, 495810908, 496217396, 496395267, 496718238, 496867859, 498345916, 499445033, 500989735, 501250862, 501784465, 502044685, 502318837, 502393637, 502958489, 504674523, 505977132, 506567125, 509101432, 509373287, 510050400, 512208109, 512228828, 513028606, 513621134, 513998917, 516513783, 517353664, 518753080, 520043803, 521396687, 525801938, 526051692, 527013817, 528162503, 529824890, 530709381, 530993934, 532249201, 533744323, 536763122, 537026605, 538106791, 538366910, 538531676, 538706851, 539228267, 539536302, 541163703, 542074557, 542516892, 543179352, 543681687, 543912260, 547615346, 547676265, 549105245, 550214364, 553011115, 553317796, 553363936, 553598750, 553672862, 555636202, 555813000, 557140359, 557335265, 560303925, 561815889, 564307179, 564608356, 565994554, 567877916, 567959142, 568347002, 568465418, 568997312, 569805714, 569962982, 570072451, 571494484, 572029430, 573000057, 573043626, 573379228, 573496117, 574378464, 575747583, 577362707, 578135921, 578276381, 578290169, 578349087, 580744144, 581127221, 582231922, 582481129, 582726222, 584979216, 585217019, 585674777, 587479265, 588274279, 589354880, 590008015, 590219193, 590419388, 590697363, 590925394, 591027521, 591723033, 592563546, 594189625, 594201627, 594247034, 594311450, 594567682, 595378878, 597438703, 598553348, 598575762, 602194886, 604226584, 604609613, 605792338, 606951086, 608806698, 609823560, 610332290, 610794490, 612054254, 612930487, 613249424, 613317962, 614544891, 615245601, 615416998, 616765844, 618179586, 618378501, 619154984, 619556739, 620361435, 620676989, 620722978, 620754075, 621252201, 622194116, 624578791, 625540581, 625670595, 626072684, 626544794, 626657728, 627769623, 628380584, 628976003, 629514174, 632197322, 633883378, 634507295, 634619863, 636214910, 637560108, 637965376, 638595941, 640879792, 641892189, 644044791, 644292888, 646783956, 647364061, 647732340, 648122869, 649020890, 649094646, 649308707, 649676771, 649837034, 650144123, 650411444, 651314277, 652808873, 654878409, 655232040, 655638974, 656279928, 659559563, 659808969, 663119717, 664428925, 666236197, 666958868, 667458347, 667598296, 667821853, 668160159, 669209726, 669531202, 669950717, 674008022, 674167108, 678623608, 678745663, 678778838, 679080234, 679453550, 680339970, 680891789, 682205971, 682672135, 684071685, 685727778, 686402542, 686427371, 686641059, 687268951, 687874889, 689320772, 689387187, 690971003, 691181433, 693407035, 693674369, 693914837, 694449644, 694454560, 694605635, 694715745, 695332799, 696607682, 698142595, 698195277, 698870098, 698928349, 699085463, 700087647, 701035502, 701343715, 701890505, 702802932, 707073787, 709079258, 712108663, 712346236, 714565577, 714709544, 714723366, 715427666, 716090361, 716352559, 717169222, 717175547, 717263877, 717671295, 717757218, 718387411, 719199799, 723158990, 723161386, 723299273, 724993745, 726062400, 726338150, 726370939, 726467426, 728408673, 728491351, 729810963, 730394497, 730951977, 731233127, 731872655, 732477848, 732830809, 734364078, 735942509, 736649865, 738883622, 739031638, 739051702, 739883518, 743253242, 744931848, 746472139, 746679796, 746760167, 747458231, 747594006, 748435995, 748437874, 749684130, 750862879, 751026482, 751232649, 753205724, 754714305, 756708262, 756853368, 758969454, 759027823, 759251765, 759575212, 760799347, 761568472, 762355759, 762924817, 763364518, 765538425, 767781913, 768528715, 769143428, 770519542, 771147536, 771988243, 775914398, 776145055, 776478169, 777170588, 778715809, 780071188, 781731148, 781915928, 782849972, 785055897, 785605857, 785712120, 786317656, 788249379, 788461056, 788613197, 790433754, 790507584, 791585232, 792947920, 793366869, 793381841, 793479482, 794812334, 794813087, 795879553, 796040853, 796470760, 797245668, 797526602, 798219128, 799487462, 799712950, 800840094, 800935687, 801400595, 802120236, 803376821, 803670538, 804180493, 804660187, 806034071, 808497807, 810562344, 811012852, 811286093, 811425613, 812902682, 812968031, 813002243, 813600501, 814975668, 817076054, 817648223, 819386637, 821104461, 823016902, 823416944, 823534775, 823629391, 824137546, 824433225, 824753405, 825116534, 825992554, 826392754, 827714988, 833014730, 833031790, 833714682, 834130110, 834144845, 834803486, 834907150, 835337471, 835604200, 836601267, 837708717, 838135981, 839735922, 842213238, 843811779, 844880013, 845094937, 845527467, 845743418, 845868104, 846406419, 847021125, 847555624, 848423850, 848503590, 849221346, 850489052, 851281216, 851670076, 852375901, 852841763, 853438759, 855994954, 856006370, 856207200, 856224524, 856557023, 856589399, 857570464, 858967076, 859342678, 860535694, 860716131, 861035678, 862560605, 862627195, 863411385, 863612516, 863751346, 863871131, 865330392, 865345571, 866022370, 866213173, 869135333, 869302061, 870231973, 870238144, 870298696, 871410071, 871497731, 871871328, 871893908, 872169598, 872238867, 872556910, 873655316, 873694813, 873958053, 874150608, 874328832, 877061108, 878782383, 879120519, 879540460, 879690742, 880640019, 881839209, 883865064, 883908774, 885685893, 885720425, 887630580, 887665934, 888346677, 889005444, 889765615, 890021904, 891832957, 892230178, 892491192, 892772212, 894544675, 895113315, 895272556, 896435847, 896598244, 897730225, 897760266, 898256685, 898300800, 898572662, 899156949, 899463830, 900087417, 900095976, 900936510, 901263709, 901314436, 903409200, 904297075, 905133139, 905181613, 906818275, 907678555, 907911769, 909579741, 913234281, 915181642, 915467593, 916382612, 916811956, 917182347, 917274868, 917723927, 918659005, 919050512, 920929177, 921060917, 921119983, 921406879, 922475689, 925397826, 927383684, 928280835, 928536480, 929769517, 930342102, 930554108, 931022092, 932954629, 933561888, 934302466, 934448987, 935497938, 936751945, 937126717, 937301445, 938543706, 939263933, 940079034, 940952736, 942370015, 943071187, 943792758, 945067322, 945742772, 947849330, 949510730, 950811280, 951133689, 952799090, 953021966, 955512624, 956733901, 958516097, 959309254, 959531930, 961826625, 962864653, 963172882, 964631579, 964697732, 968081804, 968951768, 969176978, 969806542, 971709707, 971998970, 972056239, 972101763, 973413929, 973655831, 973940963, 973944924, 976108069, 976939286, 978048711, 980245442, 980260103, 983496057, 983995500, 984015385, 984050578, 984390794, 985499308, 986693956, 988185892, 988211411, 988635705, 990609205, 991201697, 991712733, 992999765, 993710660, 997216695, 997399130, 998203256, 998327171, 999069311, 1003393958, 1003523624, 1004402630, 1004800362, 1005471891, 1005918041, 1006299978, 1008154621, 1008493231, 1009055910, 1011125533, 1011859229, 1012668792, 1013712843, 1015993266, 1018476089, 1020352432, 1020997519, 1021411178, 1021469295, 1022183265, 1022200000, 1022836434, 1023071326, 1023074450, 1025643814, 1027506937, 1029611645, 1031404463, 1031908730, 1032246845, 1032497618, 1033439139, 1035010885, 1035246486, 1035578780, 1035989972, 1036484279, 1037727254, 1041382062, 1041945708, 1043489631, 1043792985, 1044185747, 1045138998, 1045880793, 1046235040, 1048198465, 1052009384, 1052956904, 1053078294, 1056136305, 1056242120, 1057608502, 1058006315, 1058692472, 1059308746, 1060478381, 1061625665, 1061852186, 1062176481, 1062279009, 1062896654, 1065191971, 1065330800, 1067324122, 1068968703, 1069215132, 1070863623, 1071723976, 1072169079, 1072776216, 1072893919, 1072921498, 1073480453, 1073702754, 1073993855, 1075048105, 1077960228, 1079334996, 1079572163, 1080355433, 1080530759, 1081715641, 1083069492, 1083106514, 1084754873, 1085375486, 1085632582, 1086768143, 1087015909, 1087148144, 1088540209, 1088778340, 1089232903, 1089810757, 1089972550, 1089997057, 1090506289, 1093468219, 1094779283, 1094997649, 1095959299, 1099480055, 1099969787, 1101460457, 1101757217, 1102939288, 1103201649, 1106057559, 1107291612, 1107632795, 1108321831, 1109040510, 1111831765, 1111951010, 1112049794, 1113631283, 1113691215, 1114399633, 1116380920, 1116650785, 1118288195, 1118315443, 1119531905, 1121559836, 1121773967, 1121779138, 1121949019, 1123062524, 1123424479, 1123456691, 1123735623, 1124030505, 1124089552, 1124155631, 1125428811, 1125562427, 1125581841, 1125805793, 1126587106, 1127347049, 1129479702, 1130346719, 1130585495, 1130822838, 1131213975, 1131222094, 1131960805, 1132997904, 1136046753, 1136134571, 1137940890, 1138379079, 1139049203, 1139730771, 1141553727, 1143381053, 1143817567, 1144013572, 1144295661, 1144333244, 1144997666, 1148988771, 1151710452, 1151818224, 1153317824, 1153510602, 1153621188, 1153683286, 1155606279, 1157103346, 1159146229, 1159555604, 1160188910, 1161378490, 1161815310, 1166739671, 1167915757, 1168014124, 1168125206, 1168675030, 1169764903, 1170008546, 1170854955, 1171643771, 1173118795, 1175073199, 1175296998, 1175541961, 1176045646, 1177615127, 1177837457, 1180872957, 1181624532, 1183275351, 1183478625, 1183941121, 1184349353, 1185961306, 1186035312, 1186847671, 1187788920, 1188025046, 1188096355, 1188345858, 1188526566, 1188998588, 1189586212, 1190119442, 1191383916, 1192125301, 1192243925, 1192957923, 1193721535, 1193722154, 1196154294, 1196596534, 1196616256, 1196892958, 1197519935, 1200132503, 1200155865, 1200911599, 1201107058, 1202297911, 1202622448, 1203184631, 1203505446, 1203923400, 1204382541, 1204598400, 1206491407, 1206545725, 1207409170, 1207585310, 1208684633, 1208826761, 1209502475, 1210067362, 1210356118, 1211034563, 1211096265, 1213200651, 1213939621, 1214532186, 1215467346, 1215492843, 1216212075, 1218076153, 1218465419, 1218600383, 1218730591, 1218761373, 1219603475, 1219917229, 1220030804, 1223214695, 1226184469, 1227533953, 1230425209, 1231088966, 1232008130, 1232289675, 1232298818, 1234284973, 1234730998, 1238139842, 1238329307, 1239287450, 1240419778, 1240495764, 1241787270, 1242440006, 1242634917, 1245268791, 1245951835, 1247041650, 1247417863, 1248180949, 1248869653, 1249529099, 1250661026, 1251358427, 1252875504, 1255230633, 1257155146, 1257446075, 1258171636, 1258901611, 1260096024, 1260667532, 1260764435, 1261148867, 1261183369, 1261483834, 1263790536, 1265584162, 1265936073, 1266319167, 1266873904, 1267299679, 1267326939, 1268721911, 1268841096, 1269141880, 1269238158, 1269278928, 1270603297, 1270758180, 1272614754, 1273379453, 1273618775, 1275699578, 1276064477, 1277115550, 1277711721, 1278192427, 1278748431, 1278774756, 1278922581, 1279992076, 1282887343, 1283454122, 1283852936, 1284153751, 1284252815, 1284412455, 1287634012, 1287746377, 1289852361, 1290745719, 1291458264, 1291621691, 1292257703, 1292260213, 1292389556, 1292962340, 1293138713, 1293888805, 1294312520, 1294782682, 1294794316, 1295850895, 1296523906, 1297939105, 1297985339, 1299664507, 1300068839, 1300326683, 1301440015, 1301711924, 1302439214, 1302878514, 1303234236, 1303470358, 1303612123, 1303924394, 1305702820, 1307114600, 1308610705, 1308761268, 1310814082, 1311749594, 1312401806, 1313226927, 1313607212, 1314324493, 1315201260, 1319234082, 1319682706, 1321236886, 1325774688, 1327734565, 1328311171, 1328740657, 1329117893, 1329397811, 1330126522, 1330511174, 1330579450, 1331121561, 1331379162, 1331947453, 1332103653, 1332175044, 1332900881, 1333169414, 1333390193, 1333880386, 1335276494, 1336927890, 1339563446, 1340420648, 1341527108, 1342486910, 1344450511, 1345050421, 1345446739, 1346189467, 1346453843, 1346567742, 1347508747, 1347753450, 1348043893, 1348417813, 1348440973, 1351428929, 1352156812, 1352947368, 1352972024, 1353826451, 1354012540, 1354667522, 1354721760, 1356051694, 1357591674, 1357912543, 1358254787, 1358311021, 1360356397, 1361051065, 1362229177, 1362968207, 1363702675, 1363928738, 1364153620, 1364601416, 1365328278, 1366555820, 1366691418, 1368364213, 1368394682, 1369849073, 1373334014, 1374988702, 1374989439, 1375469480, 1376147029, 1377781532, 1378405454, 1378487783, 1379051182, 1379989398, 1380853748, 1382408079, 1382410238, 1382499532, 1383609002, 1384768769, 1385554167, 1385778488, 1387568618, 1388343567, 1388389768, 1388772833, 1388851519, 1392245136, 1392314130, 1392849185, 1392984279, 1393761857, 1394169888, 1395589819, 1396198798, 1397736089, 1398603450, 1398670109, 1399672952, 1400099543, 1400765245, 1402660895, 1403114999, 1404884473, 1406920387, 1408283394, 1410423070, 1411970645, 1412097041, 1412575250, 1412827667, 1415079138, 1415390482, 1415698654, 1417909517, 1417951338, 1418621111, 1419285072, 1420639235, 1422487788, 1424445338, 1425026958, 1427750681, 1428411117, 1429062233, 1429967588, 1431016667, 1433051727, 1433150446, 1433280373, 1433527917, 1433741927, 1434496093, 1434774604, 1434968755, 1436840192, 1437817573, 1441687600, 1442210326, 1442949303, 1443617037, 1444661083, 1444900796, 1445442383, 1445620156, 1447046240, 1447047073, 1447805435, 1448459555, 1450107757, 1450731495, 1451230795, 1453641604, 1453783907, 1454494553, 1454607993, 1454870649, 1455666943, 1458124591, 1458849240, 1460194953, 1460451491, 1461167939, 1461934683, 1463254835, 1463719173, 1464003424, 1464090776, 1465459097, 1466111751, 1466194725, 1466398266, 1467896246, 1469022532, 1469296530, 1469695233, 1471963416, 1473694958, 1475351009, 1476650092, 1477375528, 1478164330, 1479935836, 1480786207, 1481060733, 1482181387, 1482638835, 1483720005, 1483913191, 1485315097, 1485526614, 1486724314, 1488199745, 1489013889, 1490040317, 1491198688, 1491532473, 1492583658, 1492618215, 1492744277, 1492810781, 1492908874, 1494582361, 1497131813, 1500157501, 1500537220, 1503136637, 1503835328, 1504077009, 1505357810, 1506005378, 1506931017, 1507943171, 1508293776, 1508620191, 1508922615, 1509060384, 1511494112, 1512039020, 1513771976, 1514719755, 1517449020, 1517491290, 1518656050, 1518818650, 1519624291, 1521277049, 1523770681, 1523934139, 1524294922, 1525946626, 1527154555, 1527940879, 1529327990, 1529372397, 1530634521, 1532482288, 1532528633, 1534294722, 1536842179, 1536847175, 1538468354, 1540804490, 1540841088, 1541556662, 1541904447, 1543247400, 1543504710, 1544197796, 1544503578, 1545249144, 1546556796, 1549016465, 1549710112, 1550249237, 1551584975, 1551897611, 1554121138, 1554510493, 1555485842, 1555973494, 1556521524, 1557145095, 1557412017, 1557982853, 1558027103, 1558466375, 1560644199, 1560763375, 1561730424, 1562187896, 1562256733, 1563292397, 1564140014, 1564339465, 1565769774, 1569627997, 1570151441, 1570278555, 1570633659, 1572099989, 1572829396, 1575435048, 1575736792, 1576023333, 1576065852, 1576150665, 1580496755, 1583766517, 1584116048, 1584486094, 1585415107, 1585548135, 1586927715, 1587136182, 1588036116, 1588325528, 1592203176, 1592638435, 1593591063, 1593883256, 1594257958, 1594674511, 1594923770, 1599222242, 1601015761, 1601488018, 1603170277, 1603898338, 1604387005, 1604624331, 1606043663, 1606320390, 1607200379, 1607457727, 1607791690, 1608047111, 1608639766, 1610025680, 1610410744, 1610732064, 1611396423, 1613582476, 1613937712, 1614193182, 1614639789, 1615719919, 1616663336, 1618536714, 1618785895, 1623205233, 1623769403, 1624782246, 1625256278, 1626882035, 1629733372, 1629952224, 1631212105, 1631219583, 1633007089, 1633058581, 1633252615, 1633324716, 1633615125, 1634160083, 1634361498, 1634406070, 1635854849, 1636432414, 1636479691, 1636588523, 1636710471, 1637398934, 1637596194, 1638078650, 1638300651, 1639016045, 1641326504, 1642446963, 1642741632, 1643415027, 1644517644, 1644573213, 1645448012, 1645919932, 1647093287, 1647909886, 1649883661, 1651275603, 1653790543, 1655921662, 1656930685, 1657973219, 1658652107, 1659855263, 1659899623, 1660061949, 1662371923, 1668039235, 1669292375, 1669495547, 1670447513, 1671671267, 1672809983, 1675403429, 1676496457, 1677154029, 1677315349, 1678106782, 1680153419, 1681267217, 1681987457, 1682314643, 1683006757, 1684817031, 1687407124, 1688002527, 1688880509, 1689015096, 1690527395, 1691023637, 1691768473, 1692580019, 1693580048, 1693672505, 1694774222, 1694886587, 1695807473, 1696568601, 1698661192, 1699816008, 1701249594, 1701365858, 1704071977, 1704272497, 1706101681, 1706600279, 1708428129, 1708615607, 1708752097, 1708947797, 1709767509, 1711368126, 1711948352, 1712079970, 1712842394, 1714205754, 1714496856, 1715254188, 1715359779, 1715574252, 1716317446, 1718221719, 1720222595, 1721290066, 1721320425, 1723714573, 1723981664, 1725398852, 1726040353, 1726332523, 1727184836, 1727608712, 1727881314, 1727891511, 1728791313, 1728894028, 1728967846, 1729429937, 1730718187, 1731549438, 1732244470, 1732285966, 1732334949, 1732971308, 1733561298, 1734342140, 1735540518, 1738437208, 1739345660, 1740864968, 1741351523, 1744195514, 1744323293, 1745126965, 1745353967, 1745670266, 1746187438, 1747374143, 1748359535, 1748428728, 1748903116, 1749824503, 1750004551, 1750987256, 1752497557, 1754776702, 1755902277, 1756114221, 1757070006, 1759968649, 1761104347, 1761320803, 1761665810, 1762865258, 1764455689, 1766831908, 1766967432, 1766978148, 1767674137, 1767708037, 1768579936, 1768967145, 1769648522, 1770426662, 1770552360, 1771320695, 1773499488, 1774199070, 1775065580, 1776901171, 1777129472, 1779007179, 1781124647, 1782631117, 1783380605, 1785040615, 1785925426, 1787300731, 1788397099, 1790886508, 1791145776, 1791738560, 1792103293, 1792727282, 1795511481, 1795979386, 1798014444, 1798185587, 1798850142, 1800056698, 1800579223, 1800747911, 1800761400, 1802395867, 1802508587, 1805841337, 1807214805, 1811134129, 1811391732, 1812287745, 1812525413, 1813880307, 1814053789, 1814236601, 1814624646, 1815753215, 1816091476, 1816905728, 1817311592, 1819920852, 1820121903, 1820526130, 1820895611, 1821056784, 1821939885, 1822490297, 1822853895, 1824177658, 1824671922, 1825520491, 1827318184, 1827504529, 1828523742, 1828720373, 1829169526, 1829309863, 1829862862, 1830250056, 1830705715, 1831744870, 1833519905, 1834106108, 1834716960, 1835852264, 1837711775, 1838047370, 1838185037, 1838506704, 1838784323, 1839068847, 1839226319, 1840239506, 1840282385, 1842533319, 1843028302, 1843509108, 1844658446, 1845447125, 1846502665, 1846800750, 1847069982, 1847625909, 1848336217, 1848694184, 1849339521, 1849524860, 1849917251, 1852861873, 1853244894, 1855762935, 1856052914, 1857494126, 1859228205, 1861970752, 1862640313, 1862808159, 1863090956, 1864684202, 1865426271, 1866071002, 1866765286, 1867885308, 1869063725, 1869534286, 1869593284, 1870067688, 1871264224, 1872973363, 1873019651, 1873230744, 1874369054, 1875364253, 1875440198, 1876310568, 1876366992, 1876423795, 1877275805, 1877418989, 1877836102, 1879197185, 1879551656, 1879779720, 1880671776, 1880879359, 1882200534, 1882576958, 1883443575, 1883535408, 1884156523, 1884685705, 1885021275, 1886371702, 1886489656, 1887570510, 1889499171, 1891208596, 1891480038, 1892265601, 1892321984, 1892563034, 1895095183, 1896389295, 1896708298, 1897575790, 1897634318, 1898080535, 1898149876, 1898808020, 1899303555, 1899788348, 1899926168, 1900739644, 1901410703, 1901423320, 1901672807, 1901761230, 1902165792, 1902470552, 1903282316, 1905781903, 1906043893, 1907571752, 1908181800, 1909981662, 1910067757, 1910205491, 1911001975, 1911223285, 1911385280, 1912766815, 1912866419, 1913184478, 1914970287, 1915446061, 1915592762, 1915709511, 1916857214, 1918166403, 1918625656, 1919367719, 1920903240, 1921345245, 1923319828, 1923991167, 1925483068, 1927034716, 1927388550, 1927445295, 1927774644, 1927943667, 1928179688, 1928240505, 1929181002, 1929418578, 1929573562, 1930724344, 1932013426, 1933034555, 1933588793, 1933846693, 1934039621, 1934198375, 1935618020, 1936785286, 1937720534, 1938709601, 1940444911, 1941191853, 1941343678, 1941628921, 1941917591, 1942281254, 1943133330, 1943561920, 1944273838, 1944993135, 1946033449, 1946492106, 1948263820, 1948789806, 1949363819, 1949500775, 1949545329, 1952284163, 1952294641, 1952326086, 1952721759, 1955764184, 1955817940, 1956164019, 1956755259, 1956974702, 1958730797, 1958879299, 1960793589, 1963003556, 1963727401, 1964298789, 1964687035, 1965141086, 1965409706, 1966092971, 1966185647, 1968488952, 1969476624, 1969762540, 1970755163, 1971476905, 1972064482, 1973375983, 1974036712, 1974695693, 1975440764, 1977259401, 1977652628, 1978481851, 1980082605, 1980219974, 1980995411, 1981202732, 1981935223, 1982017091, 1982055299, 1982647893, 1983626048, 1984402703, 1984512349, 1984596341, 1984982928, 1985016491, 1985758382, 1987269436, 1988822949, 1989153572, 1991011111, 1991580564, 1992836570, 1993524877, 1994149989, 1994185491, 1994393866, 1995716271, 1996986433, 1997229924, 1998244617, 1998354018, 1998446753, 1998570141, 1999028158, 1999249564, 2000457464, 2002871556, 2002957939, 2002968575, 2003486539, 2003613834, 2004023857, 2004496824, 2006219538, 2009276101, 2009622849, 2010547881, 2012061374, 2014210366, 2016007464, 2017239802, 2017950864, 2019378544, 2019610631, 2020251976, 2020421002, 2020465060, 2020729618, 2022044991, 2022368145, 2022524506, 2022848830, 2023448529, 2024468041, 2025860459, 2025923557, 2026119644, 2026724442, 2027202650, 2027849483, 2028943614, 2030652099, 2031038069, 2031306738, 2033127564, 2033275629, 2033821874, 2034596699, 2034656539, 2034843685, 2037478899, 2037562545, 2037978575, 2038996348, 2040280364, 2040464605, 2041077302, 2041970151, 2044887858, 2046851063, 2048125030, 2049727504, 2050060862, 2051951957, 2052136968, 2053029646, 2053196953, 2054380019, 2054735646, 2056963390, 2059006823, 2059354334, 2059994715, 2060256379, 2060355134, 2060911110, 2062685871, 2063012325, 2063252522, 2064752007, 2065556289, 2067860365, 2070528356, 2071008830, 2071720620, 2071885283, 2071935528, 2072003197, 2072243444, 2072651949, 2072967483, 2073073296, 2073408983, 2074176469, 2074539650, 2075721392, 2075725554, 2077082811, 2077379228, 2077721537, 2078439415, 2080143366, 2080249660, 2080302307, 2081416535, 2082118794, 2082600345, 2088974490, 2089232180, 2091636964, 2092294603, 2095324424, 2095431960, 2097214415, 2097221623, 2098559711, 2098950795, 2099077768, 2100429638, 2101156556, 2102563865, 2102904663, 2103086753, 2103169544, 2103390133, 2103814861, 2104543712, 2106339348, 2106823102, 2106999638, 2107517781, 2107638412, 2108623293, 2108624268, 2108821669, 2109362865, 2109656705, 2109971485, 2109976053, 2110348681, 2112228552, 2112570309, 2112673821, 2114082869, 2114091150, 2114256464, 2115239436, 2115483729, 2116254259, 2118347054, 2118905054, 2119875234, 2120232825, 2123059266, 2124676231, 2126010027, 2126963398, 2127246751, 2127559457, 2128627936, 2129140600, 2129203506, 2129956321, 2131088083, 2131240214, 2131894103, 2132799180, 2133231369, 2133238570, 2133909213, 2134109525, 2135956972, 2136677429, 2136800674, 2137349500, 2138415249, 2138556529, 2141082189, 2141798636, 2146561680, 2146667419]
Number of swaps: 6227271
Time taken: 138.4124 ms

Binary Search

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Random;

public class HashMapComparison {
    public static void main(String[] args) {
        // Create HashMap and populate with 5000 records
        HashMap<Integer, String> hashMap = new HashMap<>();
        for (int i = 0; i < 5000; i++) {
            hashMap.put(i, "Value " + i);
        }

        // Generate 100 random keys for lookup
        ArrayList<Integer> randomKeys = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < 100; i++) {
            randomKeys.add(random.nextInt(5000));
        }

        // Perform Binary Search and HashMap lookup 12 times
        long binarySearchTotalTime = 0;
        long hashMapLookupTotalTime = 0;
        for (int i = 0; i < 12; i++) {
            // Shuffle the keys for each iteration to get a random order
            Collections.shuffle(randomKeys);

            // Binary Search
            long binarySearchStartTime = System.nanoTime();
            for (Integer key : randomKeys) {
                binarySearch(hashMap, key);
            }
            long binarySearchEndTime = System.nanoTime();
            long binarySearchTime = binarySearchEndTime - binarySearchStartTime;
            binarySearchTotalTime += binarySearchTime;

            // HashMap lookup
            long hashMapLookupStartTime = System.nanoTime();
            for (Integer key : randomKeys) {
                hashMap.get(key);
            }
            long hashMapLookupEndTime = System.nanoTime();
            long hashMapLookupTime = hashMapLookupEndTime - hashMapLookupStartTime;
            hashMapLookupTotalTime += hashMapLookupTime;
        }

        // Calculate average time for Binary Search and HashMap lookup
        long binarySearchAverageTime = binarySearchTotalTime / 12;
        long hashMapLookupAverageTime = hashMapLookupTotalTime / 12;

        System.out.println("Binary Search Average Time: " + binarySearchAverageTime + " nanoseconds");
        System.out.println("HashMap Lookup Average Time: " + hashMapLookupAverageTime + " nanoseconds");
    }

    // Binary Search implementation
    public static int binarySearch(HashMap<Integer, String> hashMap, int key) {
        int low = 0;
        int high = hashMap.size() - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            int midKey = new ArrayList<>(hashMap.keySet()).get(mid);

            if (midKey == key) {
                return midKey;
            } else if (midKey < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return -1;
    }
}

HashMapComparison.main(null);

Binary Search Average Time: 213447141 nanoseconds
HashMap Lookup Average Time: 33958 nanoseconds