C2W3_12HEAPS_13BALANCED_BINARY_SEARCH_TREES.ipynb

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