week2_notes.ipynb

{
 "metadata": {
  "name": "week2_notes.ipynb"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Week 2 - Data Structures"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Alright, today we're going to be talking about data structures, what they are, why they're important for programming competitions, and how to use them effectively.  I'll be covering mostly data structures that are useful for a wide range of problems; for those that are only useful for a particular subclass of problems, I'll get to them later when I talk about that subject.\n",
      "\n",
      "A data structure is largely defined by two things: its interface and its implementation.  The interface to a data structure tells you what kinds of things you can do with it - add or remove elements, choose a particular kind of element, etc. - while the implementation contains the details of how those methods and functions are actually performed.\n",
      "\n",
      "For programming competitions, usually the interface is going to be what's most important to you.  That's because often the implementation is tricky, both in terms of handling edge cases and in choosing the most efficient way to implement the interface.  So generally, I strongly advise using a library for most common data structures rather than trying to implement one during the contest.  You can either use pre-existing libraries like the `C++ STL` or preprepare a library of structures you think will be useful before the contest when you can debug them without time pressure.  So for the purposes of this class, what I'll focus on is what the data structure supports and when you should use this structure rather than an alternative.\n",
      "\n",
      "The only real exceptions to this advice are first, when you don't a good library for a particular structure you want to use and second, when you need to augment a data structure to use in your algorithm.  The first can be rectified again, by preparing your own library outside of the competition, and we'll talk about the second, augmented data structures, later.\n",
      "\n",
      "So, why should you care about data structures at all?  Why can't we just store all the data we need in a fixed array or something like that and then write the algorithm using that?  Well, usually you can, but choosing the right way to structure your data can often give you access to an interface with efficient methods that make the actual algorithm design completely trivial.\n",
      "\n",
      "Here's a good example.  Sorting is the canonical algorithm problem, and if you've taken an algorithms class you've probably learned a number of different ways to sort an array of $n$ integers.  Quicksort is the standard, and it works on a fixed array.  But it is not at all trivial to implement correctly under a time constraint; the algorithm itself is complex with some important edge conditions.  Suppose instead we had a data structure that gave us an efficient method called `find_min` that identified the minimum value in the data structure along with efficient `insert` and `remove` methods.  Then here's an obvious way to write a sort algorithm: add all the numbers in our array to the data structure, then repeatedly find the minimum, put it in the next position in the sorted array, and delete it from our structure until we've gone through all $n$ integers.  This takes $n$ calls to each of `find_min`, `insert`, and `remove`.  If those are all $log(n)$ operations, our sort is done in $O(n log n)$ time, just as fast asymptotically as quicksort, but with a much easier implementation."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Sample (unimplemented!) data structure sort\n",
      "class DataStructure(object):\n",
      "    def __init__():\n",
      "        pass\n",
      "    def find_min():\n",
      "        pass\n",
      "    def insert(num):\n",
      "        pass\n",
      "    def remove(num):\n",
      "        pass\n",
      "    \n",
      "def structure_sort(array):\n",
      "    S = DataStructure()\n",
      "    \n",
      "    for item in array:\n",
      "        S.insert(item)\n",
      "        \n",
      "    for i in range(len(array)):\n",
      "        array[i] = S.find_min()\n",
      "        S.remove(array[i])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 11
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Does anyone recognize this sort?  In fact this data structure is called a heap or a priority queue and this sort is a well-known sort called a heapsort.  The important thing to note here is that in the quicksort all the complex code is in the algorithm itself.  But in the heapsort, all of the complicated stuff is in the data structure, which we won't have to deal with during the contest.  We just use a heap.  The sort itself is very simple - only 6 lines of code - and thus much less likely to have errors or bugs.  So the way to use data structures is to look at your problem, see if you can identify methods that would make algorithm implementation simple, and then find a data structure that makes those methods simple.\n",
      "\n",
      "Alright, let's get started on specifics."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Loading in some visualization libraries for later use\n",
      "import networkx as nx\n",
      "import matplotlib.pyplot as plt"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 12
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "####Stacks and Queues"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Stacks and queues are one of the more basic data structures you'll use.  The only thing that would be simpler would be an indexed static array.  Just as an aside, one thing you'll discuss a lot in algorithms classes because they're useful for analysis are linked lists, arrays connected by pointers between elements.  You should basically never use a linked list in a programming competition unless they are specifically required.  You can get almost all of the benefit from a linked list with an indexed array and stored indices of the head and tail and linked lists are notoriously difficult to implement correctly.  OK, aside finished.\n",
      "\n",
      "Stacks and queues are very similar - they have only two methods, one which inserts elements and another which removes them, both of which are implemented so that they run in constant time, independent of the size of the structure.  For historical reasons, these methods are called `push` and `pop` for stacks and `queue` and `dequeue` for queues.  The only difference between them is in which element gets removed when you pop off of a stack or dequeue from a queue.  In a stack, the last element to be pushed onto the stack is the first element to be popped off, just as if you had a stack of elements that you piled new ones onto and removed off the top.  This is also known as Last In First Out (LIFO) order.  In a queue, the first element to be queued is also the first element to be dequeued, just like a queue of people waiting in line - if you arrive in line first, you will be dequeued before anyone who arrives after you, also known as First In First Out (FIFO) order.\n",
      "\n",
      "Stacks are often seen in recursive algorithms, even if only implicitly.  If each task to be performed requires subtasks to be finished, we can push new tasks onto a common stack as they get generated and then pop each task off to be evaluated.  Imagine, say, a program to evaluate the Fibonacci numbers, where $F_0 = 0, F_1 = 1$, and $F_n = F_{n-2} + F_{n-1}$.  We could calculate this with explicit recursive calls, or we could do so with a stack of Fibonacci evaluations where we repeatedly remove tasks and replace them with their recursive sums if needed or the base values if they're small enough.  In fact the explicitly recursive call contains a stack under the hood - the program holds a stack of function calls to be evaluated that will expand and collapse in exactly the same way."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def fib_recursive(n):\n",
      "    if n > 1:\n",
      "        return fib_recursive(n - 1) + fib_recursive(n - 2)\n",
      "    else:\n",
      "        return n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 13
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def fib_stack(n):\n",
      "    stack = []\n",
      "    stack.append(n) #append == push\n",
      "    running_sum = 0\n",
      "    while stack:\n",
      "        num = stack.pop()\n",
      "        if num > 1:\n",
      "            stack.append(num - 1)\n",
      "            stack.append(num - 2)\n",
      "        else:\n",
      "            running_sum += num\n",
      "    return running_sum"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print [fib_recursive(i) for i in range(10)]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]\n"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print [fib_stack(i) for i in range(10)]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]\n"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Queues, on the other hand, are often used where the processing order is important - these steps have to be performed in a particular order the same as we put them in.  For competitions, look to see whether the order is important to see whether to use a queue or not.  We'll also see these later when we do graph theory as a way to structure breadth-first searches.\n",
      "\n",
      "If you need access to *both* the oldest and newest element, there's another structure called a double-ended queue, or dequeue."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "##### Takeaway:\n",
      "* Both insert and remove operations should be constant time ($O(1)$) for both queues and stacks.\n",
      "* Use when you want to process elements in order of newest (stacks) or oldest (queues)\n",
      "* Use a stack to explicitly represent a recursive algorithm\n",
      "\n",
      "Data structure implementations for stacks, queues, and dequeues:\n",
      "\n",
      "* C++ STL libraries:\n",
      "    * `stack`\n",
      "    * `queue`\n",
      "    * `deque`\n",
      "* Java libraries:\n",
      "    * `Stack`\n",
      "    * `Queue`\n",
      "    * `Deque`\n",
      "* Python libraries:\n",
      "    * `[]` (native lists)\n",
      "    * `collections.deque`\n",
      "    * `collections.deque`"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "####Dictionaries, Hash Tables, and Binary Search Trees"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Unlike a fixed array, where elements are accessed by index, or a stack or a queue, where elements are accessed in some particular order, dictionary structures allow access of elements by content, usually with a key $k$.\n",
      "\n",
      "A dictionary interface will implement fast ($O(1)$ or $O(log n)$) methods for:\n",
      "\n",
      "* `search`, which, given a search key $k$, returns the element in the dictionary whose key value is $k$, if it exists\n",
      "* `insert`, which, given a key $k$ and item $x$, adds it to the dictionary so that `search(k) = x`\n",
      "* `delete`, which, given a key $k$, removes the element associated with that key from the dictionary\n",
      "\n",
      "The classic use case of a dictionary data structure is as an actual dictionary - that is, valid words for some purpose, where the words are keys and the elements associated with them are trivial - say 1.  This is better than say, simply a separated list of strings, because searching for a particular key is much faster using a dictionary structure.\n",
      "\n",
      "Here's an example:  suppose we have a string \"peanutbutter\" that we want to split into two words, where each word must be one of those in a long text file provided as `dictionary.txt`:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`pea`\n",
      "\n",
      "`nut`\n",
      "\n",
      "`falafel`\n",
      "\n",
      "`peanut`\n",
      "\n",
      "`butt`\n",
      "\n",
      "`butter`"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "For a short input string, we might simply iterate through each way of splitting the string: first \"p\" and \"eanutbutter\", then \"pe\" and \"anutbutter\", then \"pea\" and \"nutbutter\", and so on.  We'll then take each of these string pairs and look for them in the text file, by going through each line of the file and seeing if they're present.  This works and you'll get the right answer.  Unfortunately, this will take longer the more words are in the input file.  If the string isn't a valid word, we'll have to iterate through the whole input file to test that.  If we've got 10 million possible words, this quickly gets infeasible.  So instead, we'll preprocess the text file - loop through each line and insert it into a dictionary structure, where the key is the word and the element is 1, say.  Then we can use dictionary operations to quickly test whether or not a particular word is there.  Here's an implementation in Python:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "wordlist = ['pea', 'nut', 'falafel', 'peanut', 'butt', 'butter']\n",
      "#build a dictionary\n",
      "D = {}\n",
      "for word in wordlist:\n",
      "    D[word] = 1\n",
      "\n",
      "def splitwords(S, D):\n",
      "    for i in range(1, len(S) - 1):\n",
      "        a, b = S[:i], S[i:]\n",
      "        if a in D and b in D:\n",
      "            return a, b\n",
      "    return False"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 17
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print splitwords(\"peanutbutter\", D)\n",
      "print splitwords(\"peanutsbutter\", D)\n",
      "print splitwords(\"peanut\", D)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "('peanut', 'butter')\n",
        "False\n",
        "('pea', 'nut')\n"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Other possibilities for dictionaries are counts associated with particular characters or words or any other kind of key - any situation where you would want to keep track of values or numbers associated with keys that aren't simply indexes."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "As usual, I'm not going to go into great detail on implementation because there are libraries with good implementations of dictionaries available.  Usually, a dictionary is going to be implemented with either a hash table or a balanced binary search tree.\n",
      "\n",
      "Briefly, hash tables allocate a static array of size $m$, where $m >> n$, the expected number of elements in the dictionary.  It then uses a mapping function to map key $k$ to an integer $i$ and then a hash function to map $i$ to an index $j$, where $j \\in [0, m)$.  That is, it assigns each key to a particular slot in the static array.  If the array size is large enough, collisions where two keys map to the same slot should be fairly rare, and access to a particular key is constant time depending only on the speed of the mapping and hash functions.  Be wary - hash functions are easy to get wrong so that the mapping isn't uniform, with lots of keys mapping to the same slots, so performance can degrade.\n",
      "\n",
      "*Balanced* binary search trees will work well for keys that are easily comparible to each other, like strings or integers.  Each node in the tree has a key associated with it, and the left child of a node always has a key less than the parent, while the right child always has a key greater than the parent.  That means you can find a particular key by looking at the root, seeing if the key you're searching for is greater than or less than the key of the root, and then recursing on the left or right subtree.  This takes time dependent on the depth of the tree, which if the tree is balanced, should be $O(log n)$.  Be careful because *balanced* search trees are hard to guarantee.  You'll almost always want to use an existing implementation like a red-black tree or an AVL tree. "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "##### Takeaway\n",
      "\n",
      "* Dictionaries should give $O(1)$ (hash-tables) or $O(log n)$ (BSTs) access to insert, remove, and location methods\n",
      "* Use where keys of your elements aren't just indices from 0 to $n$ (where an array would work fine)\n",
      "* Allows very fast testing of element presence scaling well with size of the dictionary\n",
      "* Think very very hard before deciding to implement your own dictionary during a contest.  Both hash tables and balanced binary search trees are very easy to get wrong.\n",
      "\n",
      "Data structure implementations for dictionaries:\n",
      "\n",
      "* C++ STL libraries:\n",
      "    * `map` (binary search tree)\n",
      "    * `unordered_map` (hash table, may not always be supported)\n",
      "* Java libraries:\n",
      "    * `TreeMap` (binary search tree\n",
      "    * `HashMap` (hash table)\n",
      "* Python libraries:\n",
      "    * `{}` (native dictionary type)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "#### Heaps and Priority Queues"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Alright, on to the next structure - priority queues and heaps.  Here priority queue describes the *interface* and heap describes the *implementation*.  Just as I described it earlier, priority queues support a method that can extract either the minimum or the maximum value contained in the structure, depending on implementation.  The implementation is usually done as a *complete binary tree* with the particular property that each node is always greater than (for a max-heap) or less than (for a min-heap) both of its children.  This means that the root of the tree is always the largest (or smallest) value in the heap."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def draw_heap(heap, outfile=None):\n",
      "    \"\"\"Draw the heap using matplotlib and networkx\"\"\"\n",
      "    G = nx.DiGraph()\n",
      "    G.add_node(0)\n",
      "    for i in xrange(1, len(heap)):\n",
      "        G.add_node(heap[i])\n",
      "        G.add_edge(heap[(i - 1) / 2], heap[i])\n",
      "\n",
      "    labels = dict((u, \"%d\" % (u)) for u in G.nodes())\n",
      "\n",
      "    nx.draw_graphviz(G, prog='dot', labels=labels, node_size=700, node_color='white')\n",
      "    return G"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 37
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import heapq\n",
      "heap = (np.arange(13) * 3).tolist()\n",
      "heapq.heapify(heap)\n",
      "draw_heap(heap)\n",
      "print heap"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36]\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAd4AAAFBCAYAAADZrs5VAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzs3XdYFGf3N/DvoiJFEWmCglQRUbAsKEYNSqKCGo0xsReC\nFWvyGMsTTdSUJzHGxIpYYouKir3HaDSCFbChKCJIsSFFpS6wu+f9I6/8NFIWmNld4HyuyytX2Jkz\n5152OXvPzj1HQkQExhhjjKmFjqYTYIwxxmoTLryMMcaYGnHhZYwxxtSICy9jjDGmRlx4GWOMMTXi\nwssYY4ypERdexhhjTI248DLGGGNqxIWXMcYYUyMuvIwxxpgaceFljDHG1IgLL2OMMaZGXHgZY4wx\nNeLCyxhjjKkRF17GGGNMjbjwMsYYY2rEhZcxxhhTIy68jDHGmBpx4WWMMcbUiAsvY4wxpkZceBlj\njDE14sLLGGOMqREXXsYYY0yNuPAyxhhjasSFlzHGGFMjLryMMcaYGnHhZYwxxtSICy9jjDGmRlx4\nGWOMMTXiwssYY4ypERdexhhjTI248DLGGGNqxIWXMcYYUyMuvIwxxpgaceFljDHG1IgLL2OMMaZG\nXHgZY4wxNeLCyxhjjKkRF17GGGNMjbjwMsYYY2rEhZcxxhhTIy68jDHGmBpx4WWMMcbUiAsvY4wx\npkZceBljjDE14sLLGGOMqREXXsYYY0yNuPAyxhhjasSFlzHGGFMjLryMMcaYGnHhZYwxxtSorqYT\nYIwxVaSnpyMyMhKRkZFISUlBUVERDAwM4OLiAqlUinbt2kFfX1/TaTJWLgkRkaaTYIyxkiiVSpw4\ncQJBQUEIDw9Hhw4d4OHhAXt7e9SrVw+5ubm4ffs2oqKi8ODBA4wYMQKBgYFwdXXVdOqMlYpnvIwx\nrRQbG4uAgADk5eVh2rRp2L17NwwMDErdPiUlBevWrUOPHj0wePBg/PjjjzA0NFRjxoyphr/jZYxp\nnfXr16NLly4YOnQooqKiEBAQUGbRBQAbGxt8++23uHPnDl6+fAl3d3fcuHFDTRkzpjo+1cwY0ypL\nly5FUFAQTpw4gRYtWlQ6zs6dOzFjxgwcPXoUHh4eAmbIWNXwqWbGmNYICQnBqlWrEBYWBmtr6yrF\nGjp0KAwMDNCvXz9ERETAxsZGoCwZqxqe8TLGtMLjx4/Rrl07/PHHH2jfvr1gcb/77juEh4fj+PHj\nkEgkgsVlrLL4O17GmFaYOnUqAgMDBS26ADBnzhykpaVh69atgsZlrLJ4xssY07i7d+/C29sbycnJ\nqF+/vuDxz549i8mTJ+P27ds862UaxzNexpjGBQcHY9y4cSoV3dzcXIwcORLm5uZwc3PDkSNHyt3H\n29sbEokEf//9txDpMlYlXHgZYxq3Z88ejBkzRqVtp0+fjuTkZJw/fx4TJkzA8OHD8eDBgzL3kUgk\n8Pf3R2hoqBDpMlYlXHgZYxr19OlT5Ofnq7R0KD8/Hzt37sQPP/wAZ2dnTJs2DZ07d8bmzZvL3bdT\np06IiooSIGPGqoYLL2NMo65du4b27dur9N1rcnIy8vPz4ebmVvwzNzc33L17t9x927dvj+joaCgU\niirly1hVceFljGlUWloarKysVNo2IyMDxsbGMDIyKv6Zvb09MjIyyt23YcOG0NHRQW5ubqVzZUwI\nXHgZYxpFRCpfaWxqaooXL14gKyur+GcJCQkwMzNTaX8dHR0olcpK5cmYULjwMsY0ysjICM+fP1dp\n2+bNm0NfXx83b94s/ll0dDRcXFzK3begoAAymYwbJzCN48LLGNMod3d3XL9+XaVt9fX1MWzYMMyf\nPx9xcXFYuXIlLl26BH9//3L3vXXrFpydnVGvXr0qZsxY1XDhZYxplIODA3JycpCamqrS9itWrIC1\ntTU6d+6MdevWISQkBHZ2duXuFxkZCalUWsVsGas6vnMVY0zjhg0bhs6dO2P69OmiHcPHxwcTJ07E\nkCFDRDsGY6rgwssY07iwsDCMHz8ed+7cEeWWjjExMXjvvfeQlJQEXV1dweMzVhF8qpkxpnFdu3aF\noaEhtm3bJnhsIsJXX32FwMBALrpMK/CMlzGmFa5evQpfX1/cuHFD5XW9qti1axcWLVqEq1evQk9P\nT7C4jFUWz3gZY1qhQ4cOmDRpEoYNGwaZTCZIzJiYGEyfPh2bNm3iosu0BhdexpjWWLBgAaysrODn\n51flO0xFR0ejZ8+eWLp0KTp16iRQhoxVHRdexpjWqFOnDjp37oyYmBh06NABFy9erHAMpVKJ1atX\no0ePHli6dClGjhwpQqaMVV5dTSfAGGOvHDp0CD/++CMuXryIq1evYuDAgRgwYACmTZuGNm3alLmv\nQqHA8ePH8dNPP6GoqAjh4eEq3dGKMXXji6sYY1ohIiICffr0wdGjR9GxY0cA/zRQWL16NdatWwd7\ne3u8++678PDwgL29PerVq4fc3Fzcvn0bUVFROHbsGPLz8zFkyBD8+uuvqFOnjoZHxFjJuPAyxjQu\nISEBXbt2RXBwMPr37//W40VFRTh16hSuXLmCyMhIPHz4EEVFRdDX14eLiwukUim8vb0RGxuL4OBg\nnD17Vv2DYExFXHgZYxqVkZGBLl26YNq0aZgyZUqVYhUVFcHe3h6HDx9G+/btBcqQMWHxxVWMMY2R\nyWT48MMP8cEHH1S56AJAvXr1MHXqVCxfvlyA7BgTB894GWMaoVQqMWzYMBARdu7cCR0dYeYBGRkZ\ncHJywp07d2BpaSlITMaExDNexphGzJ07F48ePcLWrVsFK7oAYGpqiiFDhiA4OFiwmIwJiWe8jDG1\nW716NVasWIELFy7A1NRU8PgxMTHw8fFBYmIi37GKaR2e8TLG1OrQoUP4/vvvcfz4cVGKLgC4urqi\nXbt22LlzpyjxGasKLryMMbWJiIjA2LFjceDAATg4OIh6rM8++wzLli0Dn9Rj2oYLL2NMLRISEjBg\nwAD89ttvxTfIEFOvXr1QUFCAv//+W/RjMVYRXHgZY6LLyMhAnz59MG/evBJvkCEGHR0dzJgxA8uW\nLVPL8RhTFV9cxRgTlUwmQ8+ePeHl5YUlS5ao9di5ubmwtbXF5cuX4ejoqNZjM1YaLryMMdGItVa3\nIubOnQuZTMYzX6Y1uPAyxkQze/ZsXLhwAadOndLYsp6UlBS0bdsWiYmJMDIy0kgOjL2Ov+NljIli\n9erVOHjwIA4ePKjRtbQ2Njbo1asXNm7cqLEcGHsdz3gZY4I7dOgQJk2ahPDwcNGXDani0qVLGD58\nOOLi4rhdINM4nvEyxgSlzrW6qvLy8oKFhQUOHz6s6VQY48LLGBOOutfqVsSrG2owpml8qpkxJggh\n++qKgXv1Mm3BM17GWJUJ3VdXDNyrl2kLnvEyxqpEG9bqqop79TJtoL3vEMZYtSBWX10xcK9epg14\nxssYqzSx++qKgXv1Mk3T7o+njDGtpY6+umLgXr1M07jwMsYqTBvX6lYE9+plmsSFlzFWIdq8VldV\n3KuXaRIXXsaYyjTRV1cM3KuXaRJfXMUYU4km++qKgXv1Mk3hwssYK1d1WqtbEdyrl2kCF17GWLm0\noa+uGLhXL9OEmvGxlTEmGm3pqysG7tXLNIFnvIyxtxw9ehSFhYWoU6eOVvXVFcPrvXrT0tL4VpJM\ndFx4GWNviIyMhLe3N/Lz82FgYIC//vqr2i4bUoVcLkerVq1Qp04dZGRkICUlpcbN7Jl2qavpBBhj\n4ikoKEB0dDTu37+PwsJC6OrqwtHREe7u7qhfv/5b2z948AB9+/ZFXl4egH+u/A0NDa2xhZeIIJVK\ncf/+/eKf7dixA4MGDcK1a9fw+PFjyOVyGBoawtXVFc7OzqhTp44GM2Y1ARdexmqY3NxchISE4Lff\nfsONGzfQokULtGzZEnp6epDJZIiNjUVcXBzc3d0xduxYDB8+HIaGhsjMzESfPn3w7NmzN+LZ29tr\naCTik0gk6NWrF27evAkAqFOnDr744gtMnz4dbdu2RfPmzVG3bl1kZ2cjOjoaz549g7e3NwIDA+Hr\n68tFmFUOMcZqBIVCQStWrCATExP64IMP6NixY5SXl1fitnl5eXT8+HHq378/mZiY0M8//0zdunUj\nAG/8mz17tppHoX63b98mPT090tPTo9GjR1NERATJ5fISt83MzKRNmzaRp6cnOTg40IkTJ9ScLasJ\n+DtexmqA5ORkjBo1CnK5HL/99htcXFxU3jc2NhYjR45ETExM8SlmABgyZAh27NhRY9bsluTcuXMY\nM2YMunbtihUrVqBx48Yq73vy5ElMmDABPXv2xPLly2FgYCBipqwmqbnvKMZqidjYWHTt2hV+fn44\nd+5chYouALRs2RKXLl3CvHnzoK+vDwDo1q0bNm/eXKOL7sGDB/Hxxx9j9erV+P333ytUdAEUn6LO\nzc1F7969kZ2dLVKmrKbhGS9j1djjx4/h5eWFhQsXIiAgoMrxNm7ciBkzZuDChQtwc3MTIEPtdObM\nGQwZMgTHjx+HVCqtUiylUomJEyciPj4ef/zxB+rVqydQlqym4sLLWDVFROjXrx88PDywaNEiweIu\nXLgQly9fxrFjxyCRSASLqy1evHgBNzc3/Pbbb+jVq5cgMRUKBXx9fdGjRw98+eWXgsRkNRcXXsaq\nqS1btmDZsmW4cuWKoLOsoqIieHl5YcqUKYLMorXN2LFjoaurizVr1ggaNzk5GVKpFGfOnEGbNm0E\njc1qFi68jFVDCoUCjo6O2LVrFzp16iR4/IiICAwaNAgJCQmoW7fmrDqMj4+Hl5cXEhIS0LBhQ8Hj\n//LLL7hy5Qp27twpeGxWc9TcKycYq8GOHTsGS0tLlYvuyJEjYWVlhcaNG6NHjx5Yu3Ztmdt7enrC\n2toaR48eFSJdrREcHAx/f3+Vi+6xY8fQsWNHNGrUCE5OTggPDy9z+4CAAPzxxx94+vSpEOmyGopn\nvIxVQ5988gn8/PxUPhV8+/ZtODo6on79+rhy5Qp69+6N8+fPo3Xr1qXus3nzZhw6dAj79u0TKm2N\nIiJYWloiPDwcLVq0KHf7yMhIfPjhh/j6668xevRoPH/+HESEpk2blrlfQEAA3Nzc8PnnnwuVOqth\neMbLWDV0+fJleHt7q7x969atoaenB6VSCYlEgrp165Z7P2Jvb29cuXKlqqlqjaSkJNSpU0elogsA\n+/btw+jRozFhwgTo6enBysqq3KIL1LznjQmPCy9j1UxaWhqysrIq3C1o8uTJaNCgAbp27YqQkBA4\nOjqWub2dnR3y8vJqzGnTqKioCi0dOnz4MAoKCtCuXTt4eHhg7dq1KCwsLHc/qVSKqKioqqTKajgu\nvIxVM8nJybC3t6/wUp+goCBkZmZiy5YtGDx4MGJiYsrcXiKRwN7eHikpKVVJV2ukpKSo/GElIyMD\nt2/fxsmTJ7Fp0yZs3rwZa9euxe7du8vd18HBocY8Z0wcXHgZq2aKiooqvXxIX18fw4YNQ48ePbB3\n795yt9fV1UVRUVGljqVtKvK8vbr4yt/fH+3bt0ebNm0wceJEhISElLtvvXr1VJoZs9qLCy9j1YyB\ngcEb91SujNzcXFhZWam03avbSFZ3+vr6yM3NVWlbXV1d2Nvbv3HLTCJS6SxDXl4e37eZlYkLL2PV\njJOTEx48eKDyrCotLQ07d+5ETk4Onj9/ji1btuDy5csYNmxYmfsVFRUhPj4ezs7OQqStcS4uLrh9\n+7bK20+cOBEbN27EzZs3cefOHWzYsAGjR48ud79bt25V+H7ZrHapOSvjGaslDAwM4ODggFu3bqFD\nhw7lbi+RSBAcHIzAwEA0bNgQ/fr1w5EjR2BoaFjmfrdv34adnV2521UXHTp0wPXr16FUKlVq/jBr\n1qziHsVWVlYYO3YsBg4cWO5+Fb2Ii9U+vI6XsWpo6tSpsLCwwNdffy3aMb7//ns8fPhQ8FsrapK7\nuzuWL1+OHj16iHaM3r17Y8yYMRg+fLhox2DVGxdexqqhGzduoG/fvkhMTBTllo5yuRz29vY4fPgw\n2rVrJ3h8TVm1ahXOnTun0tXJlREXF4cuXbogOTm53HXSrPbi73gZq4batm0Le3t7bN++XZT4ISEh\nsLGxqVFFFwBGjRqFU6dOITY2VpT4P/30Ez799FMuuqxMPONlrJqKiopCnz59cP36dZWuUFbV06dP\n0bZtWxw5cgSenp6CxdUWq1atwo4dOxAWFoY6deoIFvf06dPw9/dHdHQ0jI2NBYvLah6e8TJWTdWv\nXx8SiQQjRowQbK2tXC5HQEAAxo4dWyOLLvDPHbx0dXXx3XffCRYzNTUVY8eOxbp167josnJx4WWs\nGtqyZQt69OiB77//Hnp6ehg9enSVi29RURHGjBkDIsLChQuFSVQL6ejoYPv27diyZQuWL19e5XjP\nnj1Dz549MWbMGPj5+QmQIavp+FQzY9VIfn4+pk2bhvDwcISGhsLNzQ35+fkYPHgwcnJysGnTJtjZ\n2VU4blJSEgICAlC/fn3s2bOnVtwAIikpCT179kTPnj2xePFiNGjQoMIxwsPDMXz4cOjo6CAmJqZW\nPG+s6njGy1g1ERcXh86dOyMnJwcRERFwc3MD8M8dmfbv3w9fX194enpi+fLlyMnJUSlmTk4OVqxY\nAQ8PD7z//vs4dOhQrSketra2uHz5MnJzc9G2bVscOHAACoVCpX0fP36MGTNmYPDgwVi2bBm6dOmC\nUaNGqbw/q+WIMab19uzZQ+bm5rR69WpSKpWlbnfr1i0aOHAgNW7cmKZMmUL79++n5OTk4n2USiWl\npKTQgQMHaOrUqWRiYkIDBgyg6OhodQ1FKx09epS8vLyoefPmtHDhQjp16hRlZmYWP65QKOjOnTv0\n+++/08cff1z8/KanpxMRkUwmI29vb/r88881NQRWjfCpZsa0WGFhIebMmYMDBw4gNDQUHh4eKu2X\nkpKCLVu24OLFi4iMjEROTg7q16+PnJwcGBsbw8PDA507d4a/vz9sbGxEHkX1cfXqVWzfvh0RERG4\ndu0aJBIJFAoFFAoFmjVrBqlUCh8fH4wYMaK4kcIrz58/R5cuXTBx4kTMmDFDQyNg1QEXXsa0VEpK\nCgYPHgxzc3Ns2bIFjRs3rlQcIkJubi4KCgpgZmYGpVJZ4ZaCtZFSqUROTg4aNWqEvLw8lZpFJCUl\n4Z133sGqVatUur0kq534O17GtNCJEyfg6emJgQMH4sCBA5UuusA/92pu0KABTE1Ni/+flU9HRwdG\nRkYAoHKHJltbWxw6dAgTJkzApUuXxEyPVWM842VMiygUCixcuBCbNm3Cjh078O677woaXyKRgN/y\nFVOZ5+zYsWMYO3YswsLC4OTkJFJmrLriwsuYlkhNTS2+sf6OHTvQpEkTwY/BhbfiKvucrVu3DkuW\nLMHFixdhZmYmQmasuuJTzYxpgXPnzkEqlaJLly44efKkKEWXqdeECRPwySefoH///sjPz9d0OkyL\n8IyXMQ1SKpVYsmQJfv31V2zevBm+vr6iHo9nvBVXledMqVRi1KhRkMlk2L17t6D3hmbVFxdexjQk\nMzMTY8aMQUZGBnbt2qWWZT1ceCuuqs9ZQUEBevfujQ4dOuCXX34RMDNWXfGpZsY0ICIiAlKpFC1a\ntMDZs2d5LW0NVr9+fezfvx8nTpwQ5N7QrPoTvoM2Y6xURISgoCAsWrQIa9aswaBBgzSdElODxo0b\n4/jx43jnnXfQvHlzXuNby3HhZUxNsrOzMWHCBNy5cwcXLlzgZSa1zKs1vr6+vrCysoKXl5emU2Ia\nwqeaGVODW7duwdPTEw0aNMDFixe56NZSUqkUW7ZswcCBA3H//n1Np8M0hAsvYyJ71Tv3yy+/xPr1\n61W+CxKrmfr06YNFixbBz88P6enpmk6HaQBf1cyYSF7vnbtnzx60adNG0ynxVc2VINZz9uWXX+Ls\n2bM4ffo0fxirZXjGy5gIXvXOzc3NRUREhFYUXaZdvvvuO9jb22PkyJHcx7eW4cLLmMD27t2LLl26\nYMKECdixY8db7eMYA/5pwrBx40ZkZGRg1qxZmk6HqRFf1cyYQF7vnXvs2DGVe+ey2uvVGt8uXbrA\n1taW+/jWElx4GRPA671zr169WqU2fqx24TW+tQ+famasioTsnctqJ+7jW7vwVc2MVZLYvXPFwFc1\nV5w6nzPu41s7cOFlrBLU0TtXDFx4K07dzxn38a35+FQzYxXEvXOZmLiPb83HM17GVKTu3rli4Blv\nxWniOeM+vjUbF17GVKCJ3rli4MJbcZp6zriPb83Fp5oZKwf3zmWawH18ay5ex8tYKbh3LtM0XuNb\nM3HhZawE3DuXaQvu41vz8Klmxv6Fe+cybcN9fGsWLryMvYZ75zJtxX18aw6+qpkxaGfvXDHwVc0V\np23PGffxrf54xstqJSLCr7/+igsXLnDvXFat/LuP7x9//AGlUqnptFgF8IyX1TovXrxAQEAA9u/f\nD1NTUwDAN998g8DAQEgkEg1nJy5tm71VB9r4nBUUFKBXr17Iz89HREQE/vOf/2Dp0qWaToupiAsv\nqzaICBkZGcjNzUXdunVhZmaG+vXrVyjGtWvX8PHHHyMhIaH4Z15eXjh//jx0dGrmCSCFQoG6dd9c\nwMBv+/L9+0OYUqnUmg9mBQUFGDFiBPbu3Vv8s+XLl2P69Oml7pObm4vMzEwQEYyMjGBsbKyOVFkJ\nuPAyrZaeno7Nmzfjr7/+QlRUFAoLC9GwYUPI5XK8ePECLVu2hKenJ0aMGIF333231D+MRIT169dj\n+vTpKCgoeOMxY2NjXLx4ES4uLuoYklrcu3cPGzduxIULF3D9+nUAgK6uLgoLCyGTydCpUye88847\nCAgIQMuWLTWcrXYgIoSFhWH79u24cuUKbt26BUNDQ9SpUwf5+flo0KABpFIpfHx88Omnn2q0gcGj\nR4/g6emJJ0+eFP9MIpFg3759+PDDDwEAcrkcR48exZ49exAZGYmkpCSYmJhAIpHgxYsXaNy4MTw8\nPODn54fhw4fD0NBQU8OpfYgxLfTkyRPy9/cnY2NjGjNmDO3fv59SUlJIqVQWb5OXl0eXL1+mpUuX\nUqtWrcjV1ZV27tz5xjZERDk5OTRy5EgC8NY/qVRKCQkJ6h6eaCIjI+n9998nCwsLmjNnDp06dYoy\nMzPf2CYzM5NOnTpFc+fOJQsLC3rvvfcoIiJCQxlrnlKppF27dlHr1q3JxcWFfv75Z7p06RLl5eW9\nsU1KSgodOHDgjdfl48ePNZb31atXydDQ8I3Xs56eHoWHh9Py5cvJxsaGOnfuTMHBwXT9+nUqLCws\n3lehUFBcXByFhITQgAEDyMTEhGbOnElZWVkaG09twoWXaRWlUknbtm0jCwsLmjt3LqWnp6u836lT\np8jV1ZUGDhxIT58+JSKimJgYcnV1LbHoBgYGUn5+vpjDUZuCggKaN28eWVhY0Pr160kmk6m0n0wm\no99++40sLCzov//9r8r71RSpqan00UcfUatWrejPP/9860NbadLT0+nLL78kCwsL+v3331XeT2jH\njh2jOnXqvPG6btSoEXXr1o2ioqJUjpOUlET+/v5kZ2dHp0+fFjFjRsSFl2kRpVJJX3zxBbm4uFR6\nBiaTyWju3LnUvHlzWrJkyVszAgBkaGhI27dvFzh7zcnKyiIfHx/q06dPpWdgT548oX79+lH37t3p\n5cuXAmeonWJjY6l58+Y0e/bsSn8Ai4qKolatWtHnn3+useK7bt264te2vr4+LVu2jBQKRaViHTt2\njJo2bUpr1qwROEv2Oi68TGvMmTOHPDw8KCMjo8qxNmzYQPr6+m8VXVdXV4qJiREgW+2Qn59P3bt3\np4CAAJLL5VWKJZfLafz48fTuu+++cZq1Jnrw4AFZW1vThg0bqhwrMzOTPD096YsvvhAgs8rx9/cn\nAwMDOnXqVJVjxcfHk62trSDPDSsZF16mFQ4cOECOjo4qn1pWxY8//vjGjHfUqFGUk5MjWHxtMHPm\nTBowYECVi+4rCoWCBg4cSJ9//rkg8bSRXC4nLy8v+umnnwSLmZGRQY6OjrRv3z7BYqrq+fPnZG1t\nTYcOHRIs5r1798jMzIxu3LghWEz2f7jwMo3LyMggKysrOnfunKBxFQoFdezYkXR1dWndunUaOxUo\nlvPnz5OlpSU9e/ZM0LhpaWlkZWVFYWFhgsbVFkuWLKHu3btX+nRsacLCwsjS0pLS0tIEjVuegIAA\nmjhxouBxf/vtN2rfvv0bF2UxYfByIqZxs2bNQm5uLoKCggSPnZiYiHbt2iEhIQEmJiaCx9ckLy8v\nfPbZZxg6dKjgsXft2oWff/4ZERERgsfWpOfPn8PBwQFRUVFwcHAQPP7UqVOhq6urtsb1169fR9++\nfXH37l00bNhQ0NhEhJ49e2LIkCEYP368oLFru5p5xwBWbeTn52PTpk2YOXOmStsnJibiiy++gLW1\nNdq3b4/Tp0+Xub2dnR0++OADbN68WYBstUdkZCSePn2KTz755K3HVq1aBQ8PD+jp6eHTTz8t/vml\nS5fQs2dPmJqawtXVFfPnz0dGRkaJ8T/++GOkp6fXuMK7efNm9OnTp8SiW9rzlpiYCB0dHTRs2LD4\n3/fff19i/JkzZ2Lr1q3Iy8sTbQyvCwoKQmBgYIlFt7TxAMDp06fx0UcfwdLSEoMGDcKZM2fe2l8i\nkWDWrFkICgriG64IjAsv06h9+/bB09MTjo6OKm0/efJk1K1bF7du3cIXX3yBvn374tGjR2XuExgY\niHXr1gmRrtbYsGEDJk6ciDp16rz1WLNmzfDVV18hICDgjZ+/ePECkyZNQlJSEv7880/cvn0bS5Ys\nKTF+nTp1MGnSpBr3vK1fvx6BgYElPlba8/ZKVlYWsrOzkZ2djXnz5pW4jb29PTp16oQ9e/YIlnNp\ncnNzsXv3bowbN67Ex0sbj0KhQEBAAPr164cHDx7A19cXAQEBJd7vuWfPnsjOzkZkZKQoY6ituPAy\njQoLC4Ofn59K2z579gx///035s2bB2NjY4wYMQKurq7YtGlTmft17twZT58+xbNnz4RIWSuU9bwN\nHDgQAwaFYnLfAAAgAElEQVQMKL4P9Su+vr4YNGgQGjRogGbNmuGLL74o80yAn58fwsPDhUxbo9LT\n0/Ho0SO88847JT5e2vP2iqqNCNT1vF27dg3Ozs6wtLQs8fHSxhMTE4OMjAwEBARAX18fAQEBSEtL\nw927d9+KoaOjg969e9eo14E24MLLNCoyMhIeHh4qbUv/XAz4xh9AuVyO2NjYMveTSCSQSqWIioqq\nUq7aIicnB4mJiWjdunWZ25V3evDixYto0aJFqY+7uroiOTkZ2dnZlcpT20RFRaFDhw7l3pO7tOfN\n1tYWnp6eWLZsGV68eFHq/h4eHmqZIar63vn3eNq0aQMLCwusW7cOWVlZWLduHaysrODq6lri/uoa\nT23ChZdp1L1790p9w/9bkyZN0KVLF3z77bdIS0vD5s2bcfv2bZUKg6urK+7du1fVdLVCfHw8HBwc\nUK9evTK3K+uG/jdu3MB3331XZkebunXrwsnJCXFxcZXOVZuo+lr79/Nmbm6OyMhIJCcnY82aNTh+\n/Hip3/EC6nutVXY8EokEhw4dwuzZs9G4cWPMmzcPhw4dKnX/mvTe0RZceJlGyWSyCjXzDg4Ohlwu\nh4eHB/bv3w8fHx9079693P309fWRn59fhUy1R35+vkrPWWkzt7i4OPTp0wdBQUHo2LFjmTEMDAwg\nk8kqlae2UfW19u/nzdDQsHim7OHhgR9++AFbt26FQqEocX91vdYqO56EhAR069YNoaGhyM7Oxo4d\nO/DOO+8gOTm5xP0NDAxqzHtHW3DhZRpVr149FBYWqry9o6Mjli1bhqSkJBw4cAA3b95Ev379yt2v\nsLAQurq6VUlVa7zqMlSekma8SUlJ6NWrF77++msMHz683BiFhYXlzqyrC1Vfa+W1/nv1lUdpH2zU\n9Vqr7Hj+/PNPtG/fHj179oSBgQF8fX3Rrl07nDx5ssT9a9J7R1tw4WUaZWtri/j4eJW3j46Ohkwm\nQ3x8PKZMmQJLS0s4OTmVu198fDxsbW2rkqrWsLW1xYMHD0q92EehUEAmk0Eul0OhUKCgoAAKhQKP\nHj2Cj48PpkyZgokTJ5Z7HCJCfHw87OzsBB6BZpT3WivpeZPL5bhy5QpiY2OhVCpx/fp1zJs3D/7+\n/m/1OH5FXa+1yoxHoVCgb9++uHLlCv766y/IZDL8+eefiIiIQN++fUuMc//+/Rrz3tEa6r9nB2P/\nZ+TIkRW6J+ysWbOocePGZGFhQYMGDSruQlQeKysrevDgQSWz1D62trYUGxtb4mMLFiwgiUTyxr+F\nCxfSokWLSCKRUIMGDYr/NWzYsNRjxMXFkY2NjVhDULukpCRq0qRJqXcwK+l5W7RoEYWEhJC9vT0Z\nGhpS586dacmSJWXeT3zjxo00fPhwsYZR7MSJE9S9e/dSHy9tPEREmzZtot69e5OZmRn5+fnR1q1b\nS40za9Ys+vbbbwXPvzbjO1cxjVq9ejUuXryIbdu2iXaM2NhYeHt748mTJ+WeRqwuhg4dCh8fH0yY\nMEG0Y2zYsAF//PEHQkNDRTuGOhERmjVrhtOnT6NVq1aiHWf06NHw8PDA9OnTRTsGAGRkZMDBwQGP\nHj1CgwYNRDuOp6cn/ve//6Fnz56iHaO24VPNTKOGDBmCI0eOID09XbRjrF27Fp9++mmNKboA4O/v\nj+DgYFHvKPTqeaspJBIJ/P39sXbtWtGOkZGRgUOHDmHYsGGiHeMVU1NT+Pj4YPv27aIdIyoqCs+e\nPYOPj49ox6iNuPAyjTIzM8OAAQNE+2P48uVLbN26VaXvNKuTXr164eXLl6Ld2OD8+fPIyMhA7969\nRYmvKRMnTsTvv/9e5jrcqli/fj0++OADmJubixL/3yZPnoyVK1eWeoV1Va1YsaLUO6SxKtDsmW7G\n/mlBZmpqSnFxcYLHFqtzizYICQkhV1fXSjdxL41MJqPWrVvTtm3bBI2rLQIDA8nf31/wuPfv3ydT\nU1O6e/eu4LFLo1QqqUePHrR48WLBY58+fZqsra3p+fPngseu7bjwMq3wyy+/UNeuXQVtQXbkyBGy\ntbWlrKwswWJqE6VSSQMHDqRZs2YJGnfOnDk0YMCAGtdG8ZWsrCyys7OjgwcPChazsLCQunXrRj//\n/LNgMVWVkJBApqamdPPmTcFiPn/+nOzt7eno0aOCxWT/hwsv0wpyuZz69etHw4YNo6KioirHu3Dh\nApmbm1N4eLgA2Wmv1NRUcnR0pJUrVwoSb/Xq1WRvb6/y1eLV1fnz58nMzEyQ10dRURGNGDGC+vTp\nQ3K5XIDsKm7btm1kY2ND8fHxVY6VlZVFXbp0oc8++0yAzFhJuPAyrZGbm0uOjo7Uq1evKjUTDw0N\nJXNzczp+/LiA2WmvhIQEcnBwoHnz5lX6jEFhYSF99dVXZGdnJ8gf7+rgjz/+IHNzc9q1a1elY6Sn\np1Pv3r3JwcGBcnJyBMyu4oKDg6lZs2YUFhZW6Rjx8fHk6elJEyZMIIVCIWB27HV8cRXTGqtXr4a+\nvj6cnZ3h7u6OvXv3Vuiq3dTUVAwZMgTz58/HkSNH4OvrK2K22sPe3h7h4eG4evUqOnbsiGvXrlVo\n/+vXr8PLywtXrlzB+fPnRWkQr4169eqFo0ePYsGCBRg8eDCePn2q8r5EhH379sHNzQ2Ojo4wNDTE\nqlWrRMy2fBMnTsSaNWswePBgfP755xVqbiGXy7F69Wp06tQJQ4cORXBwcLnNJFgVaLryM0ZEtHPn\nTrKxsaGUlBQi+udUoLu7O7m4uNDy5cspOTm5xO8c8/Ly6OzZszRixAgyNjamWbNmUV5enrrT1wpK\npZI2btxIZmZm1LFjR9q9e3epN3rIzMyk0NBQ6tSpE5mamtKGDRtq7He65cnPz6c5c+aQsbExDR8+\nnM6cOVPia0ipVFJycjKtXLmSWrVqRW5ubsWzy4cPH1Lz5s1px44d6k7/Lenp6TR69GgyMTGhKVOm\nUERERIlnQhQKBcXGxtI333xD1tbW1KNHD7VeGFab8Q00mMaFhYVh0KBBOHXqFNzd3Yt/TkQIDw/H\nmjVrcPr0aRAR3NzcYGRkhIyMDLx8+RJxcXFo1aoVRo4ciTFjxsDExESDI9EO/fv3h4WFBZKSknD5\n8mWYmZmhZcuW0NPTg0wmQ2xsLNLT09GxY0fY29vjyZMnOHLkiKbT1rjnz59jy5Yt2LZtG2JiYuDk\n5ITmzZsjLy8POjo6uHnzJiQSCXx8fBAYGIhu3bq9sTY8Ojoa7733HkJDQ+Ht7a3Bkfzj4cOHWL9+\nPUJDQ5GUlITWrVvD0tISOjo6yMzMxM2bN9GoUSP4+flh8uTJb7z3mLi48DKNunv3Lry9vbFt27Yy\n74xDRHj06BFu376N3NxcDBo0CFeuXIGbmxv09PTUmLF2i4+PR6dOnZCUlARDQ0MolUrcu3cP8fHx\nKCgogK6uLpycnNCiRQvUqVMHeXl5sLW1xYULF8rszVvbFBQUIDo6Gk+ePEH//v1x4sQJtG7dGs2a\nNSvzRiynT5/G8OHDcfbsWVHvjlVROTk5uH79OjIyMqBUKmFkZAR3d3e1rTdmb+LCyzQmNTUVnTt3\nxtdffw1/f/8K7SuRSES9a1N19dlnn0FPTw8//vijyvt8+eWXyMnJwYoVK0TMrPqq6Gtt69atWLBg\nAS5evAhLS0sRM2PVFRdephG5ubno3r07+vXrhwULFlR4fy68b8vKyoKdnR1u3LgBGxsblfd7+PAh\n3N3dkZCQAGNjYxEzrJ4q81r79ttvceDAAfz999+i3keZVU982RpTO7lcjqFDh6JNmzb4+uuvNZ1O\njbFx40b06tWrQkUXAKytreHr64uNGzeKlFntM3/+fLRr1w5Dhw6FXC7XdDpMy/CMl6kVEWHKlCm4\nf/8+jh49Wukm6zzjfZNCoUCLFi2wY8cOeHl5VXj/K1euYPDgwbh//36pfWZrq8q+1oqKitCvXz84\nODggKCioRjXpYFXDM16mVj///DPOnz+PPXv2VLrosrcdPnwYFhYWlSq6ANCxY0c0bdoUhw4dEjiz\n2qtevXoIDQ3FxYsX8dNPP2k6HaZFuPAytdm1axdWrlyJo0ePwsjISNPp1CjLli3DZ599VqUYn332\nGZYtWyZQRgwAjIyMcPToUQQFBSEkJETT6TAtwaeamVqUtla3svhU8/+5du0aPvjgAzx48KBKZxHk\ncjkcHBywf/9+SKVSATOs3oR4rWnbGl+mWTzjZaK7e/cuPv74Y2zfvp0X6Ytg+fLlmDp1apVP3det\nWxdTp07F8uXLBcqMveLm5oaQkBAMHjwYd+7c0XQ6TMN4xstEVZW1umXhGe8/nj59ilatWuH+/fsw\nNTWtcrzMzEw4OjoiJiYGVlZWAmRY/Qn5WuM1vgzgGS8TUW5uLvr164cxY8YIWnTZ/wkODsaQIUME\nKboAYGJigmHDhmHNmjWCxGNvGj16NAICAtC3b1/k5ORoOh2mITzjZaKQy+UYOHAgzMzMsHHjRsGX\nUvCMF5DJZLCzs8Nff/0FV1dXweK+uo1nUlIS344Twr/WiAjjxo1DamoqDhw4wMu3aiGe8TLBERGm\nT5+OgoICrFu3jtcvimTnzp1o166doEUXAFxcXCCVSrFjxw5B47J/SCQSBAcHo6ioCNOmTav1HyBr\nIy68THC8Vld8RCTIEqLSvFpaxEVBHLzGt3bjwssExWt11ePvv/9GQUEBevXqJUr8nj17Qi6X48yZ\nM6LEZ7zGtzbjwssEExYWhmnTpuHIkSOwtrbWdDo12rJlyzBjxgzo6IjzFpZIJHxDDTVo1qwZjhw5\nghkzZuDvv//WdDpMTfjiKiYIVfvqCqU2X1z17567YuFevf9Qx2tNW/v4MnHwjJdVWWpqKvr06YPF\nixerpejWditXrsS4ceNELboAYGBggPHjx2PlypWiHocB7733HpYsWYI+ffrg6dOnmk6HiYxnvKxK\nqtpXt7Jq64y3sj13K4t79ar3tcZ9fGsHnvGySuO+uupX2Z67lcW9etWL+/jWDjzjZZUiVF/dyqqN\nM96q9tytrNreq1fdrzXu41vz8YyXVQqv1VW/qvbcrSzu1atevMa35uPCyyqM1+pqhpg3zCgPLy1S\nL17jW7PxqWZWIUL31a2s2naqWaieu5VVm3v1avK1xn18ayae8TKVcV9dzRGq525lca9ezeA+vjUT\nz3iZSsTqq1tZtWnGm5qaChcXF8F67lZWbe3Vqw2vNe7jW7PwjJeVi/vqapbQPXcr61Wv3uDgYI3m\nURtxH9+ahWe8rExi99WtLG2YhahDQUEBbG1tBe+5W1m1sVevtrzWuI9vzcEzXlYq7qureWL13K2s\nV716+Upb9eM+vjUHF172lrS0NAC8VlfTxO65W1ncq1dzSlrj++r9yqoPLrzsDaGhoXBwcMDs2bN5\nra6GyOVyTJ06FcHBwZDJZKL13K2snj17oqioCGvWrMHUqVP51oZq9voa39mzZ8PBwQG7du3SdFqs\nIoix/y8sLIzq169PAAgAffnll5pO6S2vcnv1rybau3dv8fjs7e1p7969mk7pDfv27SMHB4fiHEND\nQzWdkii0/bU2f/784tx0dXXp3Llzmk6JqYgvrqqB7t27h+PHjyMqKgo3btxAVlYWJBIJzMzM0KFD\nB0ilUvTv3x9NmjQp3ic2NhbvvPMOMjMzi39Wt25d3LlzB05OTpoYBoB/TrdGRkbir7/+QlRUFE6c\nOAGlUgmJRAIdHR18+umn8PT0xAcffFAtZuZKpRJnzpxBeHg4oqKiEBsbC5lMBl1dXdjZ2UEqleLQ\noUNvrNkcN24c1q9fr8Gs3zRx4kSsW7eu+P9dXFzw4YcfIjIyEomJiSgsLISenh6cnZ0hlUrRtWtX\n+Pj4QEdH+0+wZWdn4/Dhw7hy5Qo2b94MhUIBIoKOjg569+4NqVQKHx8feHp6avSah4SEBLi4uKCo\nqKj4Z40bN8aFCxfg4uJS/LPU1FQcPnwYkZGRuHbtGtLS0kBEMDIygru7Ozw8PODr64uWLVtqYhi1\nFhfeGuTo0aNYtmwZbt68iYEDB8LDwwPt2rWDiYkJiAhPnz7F1atXcenSJRw7dgy+vr6YOXMmbGxs\n0LlzZzx48OCNeFu2bMHo0aM1MhaFQoHff/8dq1atQmZmJgYMGACpVAp3d3c0bNgQcrkcKSkpiIqK\nQnh4OMLCwjB06FDMnDkTjo6OGsm5LPn5+QgKCsKaNWvQsGFD+Pn5QSqVolWrVtDX10dhYSHu37+P\nyMjI4sJbVFQEuVyO6OhotGnTRtNDKBYTE4PWrVujbt26qFevHlxcXDBgwAB4eHjAyckJurq6yM/P\nx507d4o/LL18+RKBgYGYPHkyDAwMND2EtyQkJGDp0qUICQlB165d0bVrV0ilUjRv3hx169ZFdnY2\noqOjERUVhYMHD8LY2BhTp07F6NGjUadOHY3kvG3bNowaNeqNn9nZ2eHSpUt49OgRfv75Zxw/fhx+\nfn7w8vJChw4dYGVlBYlEgufPn+P69euIjIzE/v370aZNG8yYMQP9+vXjiyjVQXOTbSaU1NRU+vjj\nj8nFxYW2b99OMpms3H2eP39Oy5YtoyZNmpCNjc1bp9W++eYbNWRestjYWOrSpQt16dKFjh07RgqF\notx9Hj58SF999RWZmprSsmXLVNpHXc6fP0/Ozs40cOBAunjxIimVynL3uXPnDvn7+1PDhg217lTu\n3r17ycjIiPz9/SkmJqbc7ZVKJV26dIkGDRpELVq0oPDwcDVkqRqFQkErVqwgMzMzmj9/Pj18+FCl\nfY4fP05du3ald955h+7evauGTEv23XffvfXetba2piZNmtCvv/5Kz58/LzeGTCajHTt2UKtWreij\njz6ip0+fqiHz2o0LbzUXERFBVlZWNHv2bMrPz6/w/s+ePaO+ffuSgYFB8Rs3ICBApeIghn379pGZ\nmRmtWLGiUsXz3r171LVrV+rVqxdlZ2eLkGHFLF26lCwtLSv9Pe2FCxeoZcuWNHHiRJLL5QJnVzFy\nuZwCAwPJ2dmZzp8/X6kY+/btIysrK1qyZInA2VVcTk4O+fn5UZcuXejevXsV3l+hUNDKlSvJzMxM\nY9/DK5VKGjduXPF718DAgPr06UOpqakVjpWfn09z584lS0tLunz5sgjZsle48FZjkZGRZG5uTgcP\nHqxyrG+//ZYMDAzI29ubCgsLBciu4vbu3UuWlpYUFRVVpThyuZwCAgKoW7dulJubK1B2Fbd48WJq\n2bIlJScnVylOdnY2+fj40OjRozU2k1coFPTpp59S9+7dKSsrq0qxUlJSyMXFhf73v/8JlF3F5eXl\nkbe3N/n7+1NRUVGVYl29epUsLS01dmaisLCQevToQQYGBrRo0aIqxzt8+DCZm5vTlStXBMiOlYQL\nbzWVlpZGTZs2pQMHDggWc/78+eTp6amRmVV0dDSZmZnR1atXBYmnUCho+PDhNHr0aEHiVdTBgwfJ\n1tZWpVOXqsjNzaXOnTtrrFgtXryYvLy8KCcnR5B4jx49Ijs7O9q/f78g8SrK39+fhgwZItgHmWvX\nrpGZmRnduHFDkHgVIZfLycvLi/773/8KFvPQoUNkZWVFz549Eywm+z9ceKupYcOG0eeffy5oTIVC\nQd27d6effvpJ0LjlKSoqIqlUSuvWrRM0bnZ2Njk4ONChQ4cEjVuejIwMatq0Kf3999+Cxk1MTCRT\nU1OKjo4WNG55bt++TWZmZvTgwQNB4547d46srKwoPT1d0LjlOXLkCNnZ2Qn+VcT69eupffv2aj9j\n9PPPP5O3t7fgZ0NmzpxJgwcPFjQm+wcX3mrozz//JCcnJ1FOoyYkJJCpqSmlpKQIHrs0K1asoPff\nf1+U75XPnj1LzZo1o4KCAsFjlyYwMJCmTZsmSuzg4GDq1q2bKLFL0717dwoKChIl9owZM2jChAmi\nxC5JQUEB2djY0OnTpwWPrVQqqVevXvTrr78KHrs0Dx8+JBMTE7p//77gsfPy8sjZ2ZlOnDgheOza\njgtvNdSvXz/asGGDaPGnTJlCX3/9tWjxX6dQKMjJyanSF+uowsfHh0JCQkSL/7rnz59To0aN6MmT\nJ6LELyoqImtra7p27Zoo8f/t+vXr1KxZsyp/D1qa1NRUatSoEWVmZooS/9927txJ3bt3Fy3+xYsX\nycHBQW3fxS9YsIACAwNFi79x40bq06ePaPFrKy681UxiYiKZmJiUONstKCiggIAAsrW1JTMzMxo5\ncmTx0o3CwkIaNGgQ2dnZkUQiobNnz5Z6jFu3bpGVlZVaTpmdPHmS2rZtW+Jst6zxvG7RokUkkUhK\nncXs2bNHbbPE5cuX09ChQ0t8rKzxbNu2jRo0aFD8z8DAgCQSSYnfeX/77bdqmyVOmjSpzAt2RowY\nQZaWlmRsbEzdu3en4ODg4scuXbpEUqmUGjduTH379i31+8Lhw4fTL7/8InjuJfH29qbdu3eX+nhp\n47l9+3bxWJo1a0ZDhgwp8ftcpVJJ7du3p+PHj4s2hleKioqoadOmdPPmzRIfL+t3U1hYSLNmzSIH\nBwcyMjKid999t8QYubm5ZGpqSgkJCaKMobbiwlvNbNiwgUaMGFHiY7m5ubRw4UJKSkqigoIC2rBh\nA1lbW1NRUREVFhbS8uXLKTw8nKysrMr9/tHV1bXKVxerYubMmfTdd9+V+FhZ43nl/v375ObmRs2a\nNSu18BYUFJCBgYFalhf16dOn1KUlqoznlc2bN5OTk1OJce7evUu2trZCpl0qe3v7Mtfq3rp1i/Lz\n84vX6jZq1Ihu3bpF2dnZZGxsTF999RUlJSXRRx99RD4+PiXG2L9/P/n6+oo1hGI5OTmkr69f5jr3\n0sbz4sULSkhIIKVSSdnZ2bRgwQLq2LFjiTH+97//CX79RUmuXbtGLi4upT5e2liIiKZNm0a9evWi\nsLAwUiqVZV7UOGrUKMGvv6jtuPBWM4GBgRX6DsnJyemt72isra3LLbyjR49Wy5ute/fuFfoO6d/j\n8fX1pWPHjpGdnV2Z39t5enpSWFhYlXItj1KppCZNmlBSUpLK+5T0+yH653kp7SYmCoWCjIyMRL8o\nKSMjgxo2bKjSaVO5XE6XL18mU1NTun//Pm3atOmNDw6PHz8miURS4swpJSWFzM3NRV87fv78eZJK\npSpt++/xvO7ly5f0zTfflHrK+uTJk6XOIIW0YcMGGjlyZLnb/XssSqWSmjVrRrGxsSodZ/ny5TRx\n4sSqpsteo/03T2VviI6ORtu2bVXa9tGjR3j06BEcHBwqfJx27dohOjq6wvtVVFXGExoaCj09Pfj5\n+ZW7rzrGk56ejsLCQtjY2Ki0fWm/n6SkJISFhZV6u04dHR24u7uLPp5bt26hTZs25d5jefLkyWjQ\noAG6du2KkJAQODo6IjY2Fm5ubsXbWFlZwcTEBLGxsW/t36xZMyiVSjx79kzwMbxO1ddaSeN5xdjY\nGI0bN0ZoaCgOHjxY4v7a9N4paSxXr16FQqHA+vXrYWtri2HDhiE8PLzUGOoaT23Chbeayc7OhrGx\ncbnbFRYWYsSIERg/fjxatGhR4eM0atQI2dnZlUmxQio7nuzsbMybNw/Lly9X6TiNGjVCVlZWVdMt\nU3Z2Nho1aqTSvW7L+v1s3boV7777LmxtbUvdX13jUeV3ExQUhMzMTGzZsgWDBw9GTEwMMjMzYWdn\n98Z2Dg4OyMjIeGt/iUSi9eN55cWLF7h//z48PT0xYMCAEvdXx1gA1cZT0ljOnj2L1NRU5OfnIzIy\nEgMGDEDfvn0hk8lKjGFsbKyW8dQmXHirGR0dHSiVyjK3USqVGDlyJBo2bIhffvmlUsdRKpVqufl7\nZcezcOFCjBo1Cs2bNy/ejsro96GO8agylle5lPX72bp1K8aMGVNuDG0ZDwDo6+tj2LBh6NGjB/bu\n3QtTU9O3mm4kJCTA1NS0xP21fTyvs7e3x+LFi3HhwgU8fPjwrX216b0DvD0WIyMj6OjoYMGCBTA3\nN8fQoUPh6uqKw4cPl7i/QqHQWCOImooLbzVjYWGBx48fl/o4EWHs2LFIT0/Hnj17Kv2Gefz4MczN\nzSubpsoqO56//voLK1asgJWVFaysrJCSkoLBgwdjyZIlJcZ5/PgxLCwsRBnDK2ZmZkhPTy+zMXx5\nv5/z58/jyZMn+Pjjj8s8ljrGU97vpiS5ubmwsrJCy5Yt3zg9+fjxY2RmZpbYfk4ulyMtLQ1mZmZV\nzrksVRnPv8lkMtSvXx+NGjV66zF1/G6Aio/n1VhetQ3895mZ0s7UqGs8tYpmv2JmFfXf//6XFixY\nUOrjkyZNKvXWfjKZjPLz88na2ppOnjxZZlOF/v37l7nsQigffvgh7dy5s9THSxtPRkYGpaamUmpq\nKj19+pRsbGxoz549pd7SsEWLFmq541PLli3LvG1gWb8fIqLx48fTmDFjyjxGfn4+6evrV6opRkXI\nZDLS19envLy8Eh9/9uwZhYSEUHZ2NmVmZtLmzZupUaNGlJOTQ1lZWdS4cWNauHAhJSYm0sCBA+m9\n994rMU50dDS1aNFCzKEQ0T9LghwdHUt9vKzx/Pnnn3Tt2jWSy+V0+/ZtGjFiRKm/p927d1P//v1F\nGsX/2bNnD/Xr16/Ex8oai1KpJFdXV5o2bRqlp6fT7t27ydTUtNSbzCxatIjmzJkj5lBqHS681cze\nvXupV69eJT6WmJhIEomE9PX131gTumPHDiIisrW1JYlEQjo6OsX/LekKXLlcTpaWlhQfHy/qWIj+\naWs2Y8aMEh8rbzyvK+uq5rS0NDI0NBTtJhCvGzFixBvrJV9X3njy8/PJ2NiY/vrrrzKPER4eTm3b\nthU895J06NCh1Cvg09LSyNvbm4yNjcnGxoYCAwPfuHL81TpeY2Nj6tu3L6WlpZUYZ/369aWufRaS\nXC6nhg0bltq5p6zxhIaGkouLCzVo0IA6duxIP/74Y6nt8/7zn/8I0qygPImJiWRhYVHivdXL+90k\nJd8qCw4AAAhhSURBVCXR+++/T6ampjRs2LAyWzX6+fmp5UN4bcKFt5rJzs6mxo0bV2jJSkUdOXKE\nPD09RYv/urt375KFhYVKPYQra8mSJWprlnDw4EHq1KmTqMcICAigH374QdRjvPLjjz+Sv7+/qMfo\n3Lmz2poljBkzhhYvXixafJlMRk2aNKE7d+6IdozXdezYUdR7kaekpFDjxo2r3JGKvYkLbzU0bdo0\n+vLLL0WL7+fnR5s2bRIt/r+9//779Pvvv4sSWy6Xk6OjI128eFGU+CUdr3nz5hQZGSlK/IyMDGrU\nqFGl+q1WxrNnz6hRo0airRm+evVqqTcREcPly5fJzs5OtA5c27dvL/VGIWLYvHkz9e7dW7T48+fP\npylTpogWv7biwlsN3b9/v8SF/UJ41bmltO/1xHDq1Clq3rw5vXz5UvDYrzq3iH1zhtetWrWKunTp\nIsof97Fjx9KkSZMEj1uWKVOmUEBAgOBxFQoFde3alZYvXy547NIolUry8fERpQPXy5cvydbWlk6e\nPCl47NLk5eWRvb29KLPe+Ph4MjU1pbi4OMFj13ZceKuppUuX0rvvvivozdifP39O1tbWonRuKc+4\nceNo/Pjxgsa8e/euaB9QyqJQKKhbt26C33/4xIkTon1AKUtWVhbZ2trSsWPHBI3766+/ivYBpSyv\nCkpZt8KsjAkTJojyAaU8Z86coaZNm1JGRoZgMV+1CF2yZIlgMdn/4cJbTcnlcvLx8aHJkycLMpvL\ny8ujHj160GeffSZAdhX38uVLcnJyohUrVggSLzU1lZydnWnt2rWCxKuouLg4srCwEKxY3bp1i5o0\naaKRD0VE//xxb9KkSak35K+oEydOkIWFBd27d0+QeBW1fv16atGihWBdpFatWkWOjo704sULQeJV\n1H/+8x/y9vYW5EyVUqmkadOmkbe3t9o/FNUWXHirsZcvX1LHjh1p/PjxVbo4KSMjg3r06EHDhw/X\n6BvtwYMHZGtrSz/++GOVPkzEx8dTy5Yt1XJlaVkuXrxI5ubmVb4i9NKlS2RpaVni1dzqtHPnTmrS\npAlduHChSnH27NlD5ubmoraCVMV3331Hzs7OVTojolQq6aeffqLmzZtrtIOPQqGgUaNGkbe3d5W+\njy8oKKBJkyaRh4eHxj5E1AZceKu5rKwsGjBgALVp06ZSF/QcOHCAmjZtSl988YVWfLpNTk4mT09P\n8vHxoQcPHlRoX4VCQatXryZTU1NatWqVOAlWUFRUFDk4ONCoUaMq3HNWJpPRf//7X7KwsBD1ytWK\nOHLkCFlYWNDcuXMr/GEvMzOTRo8eTQ4ODqJdfFZRQUFBZGZmRqtWrarw1zaJiYn0/vvvk6enp6ir\nDFSlUCho9uzZZGVlVamrxKOiosjNzY369++v9q8zahsuvDWAUqmkbdu2kYWFBX3yySd05syZMmeM\nhYWFFBoaSt27dydHR0c6d+6cGrMtX1FRES1evJhMTExowoQJdP369TK3z8nJoXXr1lHbtm3Jy8tL\nbUs5VJWTk0PTpk0jc3NzmjNnTrkzo7S0NFq8eDHZ2dnRhx9+KNjpUKE8ffqUPvroo+KzE6X12X3l\nwYMHNHfuXDI3N6epU6eqpT1jRdy9e5c6d+5M7u7utHbt2nLzu3HjBk2cOJFMTEzohx9+UNsV2aoK\nCwujFi1aFPceLquvtlKppLNnz9LgwYPJ3Nyctm7dqtYLEWsrCVEZN7hl1UpWVhZ+//334hujS6VS\ntG/fHiYmJlAqlUhNTUVUVBSuXr0Kd3d3TJ48GQMHDoSurq6mUy/R06dPsWHDBqxduxZ169aFVCqF\nu7s7jIyMIJfLkZycjKioKERHR8PHxweTJ0/G+++/X243HU2Ji4tDcHAwtmzZAgsLC0ilUrRq1QoG\nBgYoLCxEXFwcoqKicP/+fQwaNAiTJ0+Gp6enptMuVUREBNasWYO9e/fC0dERUqkULVq0gK6uLvLy\n8nDnzh1ERUUhNTUVY8aMwaRJk+Ds7KzptEukVCpx+vRpBAUF4dSpU3Bzc4NUKkXz5s1Rr149ZGdn\n4+bNm4iKikJhYSEmTpyIcePGlXg7SW1QWFiIAwcOICgoCNevX0eHDh0glUphaWkJHR0dZGZm4vr1\n64iKioKxsTEmT56MUaNGlXgLTCY8Lrw1EBEVF6UbN27g5cuX0NHRgZmZGTp06IAOHTpUq3uvKpXK\n4qJ069Yt5Obmol69erCysir+cFGd/mAUFRUhJiYGUVFRiI2NhUwmQ7169WBvbw+pVIq2bdtCX19f\n02mqLD8/Hzdv3kRkZCQSExNRWFgIPT09ODs7QyqVonXr1qhXr56m01TZy5cvce3aNURFReHJkyco\nKiqCoaEhWrduDalUCmdnZ639cFeStLS04g/c6enpUCqVMDIyQtu2beHh4YHmzZur1FGLCYcLL2OM\nMaZG1edjG2OMMVYDcOFljDHG1IgLL2OMMaZGXHgZY4wxNeLCyxhjjKkRF17GGGNMjbjwMsYYY2rE\nhZcxxhhTIy68jDHGmBpx4WWMMcbUiAsvY4wxpkZceBljjDE14sLLGGOMqREXXsYYY0yNuPAyxhhj\nasSFlzHGGFMjLryMMcaYGnHhZYwxxtSICy9jjDGmRlx4GWOMMTXiwssYY+z/tVfHAgAAAACD/K1n\nsaskYiReABiJFwBG4gWAkXgBYCReABiJFwBG4gWAkXgBYCReABiJFwBG4gWAkXgBYCReABiJFwBG\n4gWAkXgBYCReABiJFwBG4gWAkXgBYCReABiJFwBG4gWAkXgBYCReABiJFwBG4gWAkXgBYCReABiJ\nFwBG4gWAkXgBYCReABiJFwBG4gWAkXgBYCReABiJFwBG4gWAkXgBYCReABgF7cLpRU6tAjkAAAAA\nSUVORK5CYII=\n",
       "text": [
        "<matplotlib.figure.Figure at 0x10dbb4090>"
       ]
      }
     ],
     "prompt_number": 38
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "When you remove the minimum, you simply remove the root, promote its smallest descendant, and continue on down the line, while maintaining the tree's completeness by a series of tree rotations.  Similarly, to add a new element insert it as a leaf at the next position, then promoting it and rotating until the heap property is conserved.  I'm being deliberately vague here because I don't want to focus on the details - as I said at the beginning, you shouldn't be focused on the implementation details during the contest.  Instead what I want to focus on is when you would want to use a priority queue.  I mentioned earlier that heaps are quite useful for sorting static data - I have an array of $n$ elements, and a heap lets me sort those in $O(n log n)$ time just by trivial use of the interface.  \n",
      "\n",
      "But suppose that you instead have a dynamic list of elements, say tasks to be performed, where new tasks can be added during execution (say by recursive calls).  Different data structures allow fast identification of the next task to be done in different ways:\n",
      "\n",
      "* Stacks let you quickly find the *newest* task\n",
      "* Queues let you quickly find the *oldest* task\n",
      "* Priority queues let you choose the *best* task based on a numerical priority you assign\n",
      "\n",
      "As such, priority queues are ideal for any algorithm that requires you to process items in a particular order that's not the same as the order we insert them into the queue.  We'll just attach a priority to the item that describes how we want to process it and then remove items from the queue based on its priority.  Priorities won't be seen often in isolation, but they're key components to lots of more complex algorithms, in particular graph theory problems where you need to repeatedly find, say, the shortest edge in a graph."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "##### Takeaway\n",
      "* Priority queues give $O(log n)$ access to insert and remove-max/remove-min methods\n",
      "* Use when you want to process items based on some numerical priority (path length, task cost, etc.)\n",
      "\n",
      "Data structure implementations for priority queues:\n",
      "\n",
      "* C++ STL libraries:\n",
      "    * `priority_queue`\n",
      "* Java libraries:\n",
      "    * `PriorityQueue`\n",
      "* Python libraries:\n",
      "    * `heapq` (package, use methods on lists to maintain heap properties)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "#### Union-Find"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Union-find structures are used when you want to keep track of a number of disjoint sets on a common group of elements.  Say these elements are all in group 1, while these elements are all in group 2 and I need to be able to quickly tell what set a particular element is in.  It's called a union-find because those are the two interface methods it supports:\n",
      "\n",
      "* `union`, which given two elements, merges the sets containing them\n",
      "* `find`, which given an element, returns the set to which that element belongs\n",
      "\n",
      "Let's take an example array\n",
      "\n",
      "    A = [1, 2, 3, 4, 5, 6, 7]\n",
      "where the disjoint sets are (1, 4, 5), (2, 6), (3), and (7).  One way you could implement this interface would be to number the sets and create a supplementary array marking which group each element belongs to:\n",
      "\n",
      "    S = [1, 2, 3, 1, 1, 2, 4]\n",
      "Then `find` would clearly run in constant time - all we have to do is look it up in $S$ - but how long would a `union` operation take.  Suppose, for example, we want to merge groups 3 and 4.  We can do that by going through each element of $S$, find elements belonging to group 4, and changing them to group 3 instead, which will take linear time.  Unfortunately, this isn't good enough.  A common use case for this kind of structure is starting with each element in its own disjoint set and serially merging sets until they're all in the same set.  In the worst case, this can take as many as $n$ `union` operations, leaving us with an $O(n^2)$ algorithm.\n",
      "\n",
      "To resolve this, instead of marking groups arbitrarily, let's think of another way to mark groups.  We'll pick an arbitrary member of each group to be its representative. Then instead of using our supplementary array to mark group numbers, we'll use it to indicate the representative of the group that element is associated with.  So if we pick the representatives 4, 6, 3, and 7, we'd have an array like:\n",
      "\n",
      "    S = [4, 6, 3, 4, 4, 6, 7]\n",
      "    \n",
      "We can think of this as a forest of trees, with each tree representing a set and root of each tree being that set's representative:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "G = nx.DiGraph()\n",
      "A = [1, 2, 3, 4, 5, 6, 7]\n",
      "S = [4, 6, 3, 4, 4, 6, 7]\n",
      "for element in A:\n",
      "    G.add_node(element)\n",
      "for i, root in enumerate(S):\n",
      "    G.add_edge(i+1, root)\n",
      "labels = dict((u, \"%d\" % (u)) for u in G.nodes())\n",
      "    \n",
      "nx.draw_graphviz(G, prog='dot', node_color='white', node_size=700, arrows=False)\n",
      "print S"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[4, 6, 3, 4, 4, 6, 7]\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAdwAAAFBCAYAAADdWx5oAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Wt8VOWdwPH/5J6QNBvInQl3EcGEyAS8oqjYVbRyU7aI\n0ApoIO6Cu+t62ZaVooJote5+EEyxKHiJtHjbotRFhALicpmSCxeD4RaSAAuJBBKSTDLz7AsLXbeS\nzCTnnJlzzu/70s555umQ5JfznJPzOJRSSgAAgK7Cgj0BAADsgOACAGAAggsAgAEILgAABiC4AAAY\ngOACAGAAggsAgAEILgAABiC4AAAYgOACAGAAggsAgAEILgAABiC4AAAYgOACAGAAggsAgAEILgAA\nBiC4AAAYgOACAGAAggsAgAEILgAABiC4AAAYgOACAGAAggsAgAEILgAABiC4AAAYgOACAGAAggsA\ngAEILgAABiC4AAAYICLYE4DI2bNn5YMPPpDt27eL2+2WyspKaW1tlZiYGBk0aJC4XC658cYb5fbb\nb5fw8PBgT9cQzc3N8p//+Z+ybds2cbvdcvDgQfF4PBIVFSUDBgwQl8sl1113ndx9990SHR0d7Oka\noq2tTdatWydbtmwRt9st5eXl0tzcLJGRkdK7d29xuVxy9dVXy/jx4yUhISHY0zWEz+eTTZs2yeef\nfy5ut1v27dsnjY2NEhERIZmZmeJyuWT48OEyceJE6dGjR7CnayrHjh2TDz74QHbt2iV/+tOf5NSp\nU+Lz+SQhIUFycnLE5XLJHXfcIXl5ecGeqmk4lFIq2JOwq6NHj8rixYulqKhIbrrpJhk1apS4XC7p\n37+/REZGyvnz52Xv3r3idrvl448/luPHj0t+fr7MnTtXunXrFuzp6+LUqVPywgsvyOuvvy5XXXWV\njB49Wlwul1x++eUSExMjTU1NUl5eLm63W9avXy9lZWUyffp0efTRRy37A7WhoUFefvllKSwslKys\nLBkzZoy4XC4ZPHiwxMXFicfjkYMHD4rb7ZZNmzbJli1b5L777pPHH39csrKygj19XXg8Hnn11Vfl\nlVdekejoaBk7dqzk5eVJdna2JCQkSFtbm1RWVsquXbtk69atsm7dOhk3bpw8/vjjcsUVVwR7+iHt\nyy+/lMWLF8vmzZtlwoQJcu2118qwYcMkMzNTHA6HnDlzRoqLi2Xnzp2yZs0aSU5Olrlz58qUKVPE\n4XAEe/qhTcFwPp9PLVu2TCUnJ6uf/exnqqqqyq/j3G63mjRpkurfv7/avHmzzrM03po1a1R6erp6\n+OGH1YEDB/w6pry8XM2aNUtlZGSoDz74QOcZGm/jxo2qb9++avLkyWr37t1+HVNZWameeOIJlZyc\nrJYvX658Pp/OszTW7t271dChQ9Xtt9+utmzZ4tf/v1OnTqlFixapHj16qIULF6rW1lYDZmouDQ0N\nas6cOSozM1O9+uqr6ty5cx0e09bWptauXauGDx+ubr31VnXkyBEDZmpeBNdgTU1NasKECWrEiBFq\n7969nRrjww8/VBkZGeqXv/ylxrMLDq/Xq/7+7/9eDRw4UG3btq1TY2zevFkNGDBAPfLII8rr9Wo8\nw+BYtGiR6tmzp1q7dm2nji8rK1Mul0tNmjRJtbS0aDy74Fi1apVKSUlRb7zxRqd+kThy5IgaPXq0\nGjVqlKqvr9dhhuZ07NgxdcUVV6gpU6ao2tragI9vbW1Vzz33nEpOTlYbNmzQYYbWQHAN1NLSou68\n8041ceLELv8ArKysVJdffrlavHixRrMLDp/Ppx588EE1cuTILv8A/Oabb9S1116rHn74YdOf1T3z\nzDNq8ODBqrq6ukvjNDU1qbFjx6px48aZ/qxu5cqVyul0qn379nVpHK/Xq2bPnq2uueYav87irK66\nulr169dPvfDCC10ea+PGjSo5OVl9/vnnGszMegiugf75n/9ZjRkzRnk8Hk3Gq6qqUr169VIff/yx\nJuMFw3/8x38ol8ulzp49q8l4Z86cUUOHDlXLli3TZLxg+PDDD1WfPn1UTU2NJuO1tLSo2267TT3x\nxBOajBcMO3bsUKmpqWr//v2ajOfz+dRPfvITdd9992kynlm1tbWpa665Ri1YsECzMT///HOVkpKi\njh07ptmYVkFwDfLFF1+o9PR0derUKU3H3bBhg3I6neqbb77RdFwjfP3116pHjx6qvLxc03H37t2r\nkpOT1eHDhzUd1winT59WGRkZml+jP3HihEpLS1M7duzQdFwjNDc3q8GDB6t33nlH03EbGxvVgAED\nLHnt31/PP/+8GjVqlOaXYX7xi1+oO+64w/QrTVojuAbw+XwqOztb/e53v9Nl/FmzZqm5c+fqMrae\n7rzzTvXiiy/qMvbChQvV+PHjdRlbTwUFBWrOnDm6jP3222+rYcOGme6H4HPPPafGjh2ry7y3bNmi\nMjMzVXNzs+Zjh7qamhrVvXt3dejQIc3H9ng8aujQoeq9997TfGwzI7gG2Lhxoxo8eLBuP+iOHTum\nunfvbqrrURUVFSolJUU1NTXpMn5DQ4Pq3r27qe6aPHPmjEpKSlLHjx/XZXyv16suu+wy9cUXX+gy\nvh7a2tpUVlaWcrvdur3HrbfeqvnZsxksWLBAzZo1S7fxV69erUaNGqXb+GbEk6YMsGzZMikoKPDr\nb9SWLFkieXl5EhMTIw888IBf4zudTrnpppvknXfe6epUDVNYWCgPPPCAxMTE+PX6UaNGSWxsrCQk\nJEhCQkKHf0vZrVs3mTp1qvz617/WYrqGePPNN+WHP/yhpKend/haj8cjM2bMkD59+khKSopMnTpV\nvvjii3aPCQsLk9mzZ8vSpUu1mrLuPvnkE+nZs6cMGzbMr9fff//9kpGRIUlJSXLzzTdLYWFhh8cU\nFBTIsmXLujpVU/F6vVJYWCizZ8/u8LXx8fEXv+8SEhIkIiJC5syZ0+Fx48aNk/Lyctm3b58WU7YE\ngqszpZSsX79eJk6c6Nfre/bsKfPmzZPp06cH9D4TJ06U9evXd2aKQbF+/XqZMGGC3693OBzyyiuv\nyLlz5+TcuXOyf//+Do+555575LPPPuvKNA0VyGfS1tYmvXr1ks2bN0t1dbWMGjVKfvzjH0tbW1u7\nx02cOFE+++wzUSZ53k2gXydPPvmkHD58WOrq6uS5556Txx9/XPbu3dvuMXfddZfs2rVLGhsbuzpd\n09i/f7/ExsZKTk5Oh69taGi4+H134sQJiY2NlUmTJnV4XFRUlNx9992yYcMGLaZsCQRXZ0eOHJG4\nuDi/zlpERMaPHy9jx44N+KlJLpdL3G53Z6ZouObmZikvL5ehQ4cGdFygkcjNzZU9e/ZIa2trQMcF\ni9vt9vsxeXFxcfLUU09Jr169JCoqSmbMmCExMTEd/nDLysoSr9crNTU1WkxZd4F8JiIiQ4YMkZiY\nGPH5fOJwOCQiIqLDVZSoqCgZPHiwlJSUdHW6phHo53rBmjVrJC0tTW644Qa/Xm+mn0tGILg6Kysr\n8+u3yP8v0LgMHDhQTpw4YYrf0svLy6Vv375+Lydf8OSTT0pWVpbMmTPHrx+O8fHx0rNnT6moqOjs\nVA1z5swZqa+vl759+3bq+OrqaqmurpZ+/fq1+zqHwyFDhw6VsrKyTr2P0fbs2RPwL2YFBQUSHx8v\nN9xwgxQVFUn//v07PMZMn4kWOvO5ioisXLlSpk2b5vfr7fa5doTg6qyhoUESExMDPi7QZ5KGhYVJ\nt27dTBHcznwmixcvlsOHD4vb7ZbMzEy54447xOv1dnjcD37wA2loaOjsVA3T0NAgP/jBDzr1LFqP\nxyNTpkyRBx98UC677LIOX5+YmGiKz0RE5Ny5cwF/rSxdulTq6upk5cqVMmnSJL+uIZrl60QrF77e\nAnH06FHZvHmz/OQnP/H7GLt9rh0huDoLDw/3Kwz/X2eusfl8PlPsJtSZz2TEiBHSrVs3SU1NlSee\neEKSk5Nl7dq1HR7n9XpN85n4fL6Aj/P5fHL//fdLQkKCvPTSS34dY5bPRKTz3z+xsbEyefJkufnm\nm+W9997r8PVm+d7RSme+3t58800ZOXKk9O7d2+9jzPS1ZgSCq7P09HSpqqoK+LhAz3QaGhqkubk5\n4N9ag6Gzn8n/5XA4OvylRCklVVVVkpaW1qX3MkL37t2lvr5empub/T5GKSUzZsyQ06dPy5o1a/z+\nwWaWz0Sk618rjY2NkpGR0eHrzPSZaCEtLS3gz3XVqlUBnd2K2O9z7QjB1Vlubq6UlpZ2ePfoBV6v\nV5qbm6WtrU28Xq+0tLT49Rt+cXGxDBkyRCIjI7s6Zd317t1bmpub5cSJE369vr6+Xj799FNpbm6W\n06dPyy9/+Us5ffq03H333e0ed+zYMQkPD5fMzEwtpq2r6OhoGThwoJSWlvp9TEFBgXz11Vfy+9//\n3u89gT0ej+zbt09yc3M7O1VDDRs2zO+bbk6dOiXvvvuuNDQ0yDfffCMrV66U7du3y+TJkzs81u12\ni8vl6up0TSOQz1VEZNu2bVJTUyP33ntvQO9jt8+1IwRXZ4mJieJ0Ov2+A/Lpp5+WuLg4Wbx4sbz1\n1lsSGxsrzz77bIfHbdu2zTQbQTscDsnLy5Nt27b59frW1laZN2+epKamSl5enlRWVspHH30kYWHt\nf/l++eWXkpeXZ5o9OocPH+73Z3L06FEpLCyUkpISSU9Pv/g3kkVFRe0e53a7pX///hIXF6fFlHUX\nyGficDjk1VdflaysLBk6dKhs375d1q5d2+He0TU1NXLmzBkZMGCAFlM2hby8PNm1a5d4PB6/Xr9q\n1SqZOHFiwPtwX/gexJ8F75kb9vHUU0+pgoIC3cb3+Xxq4MCBasuWLbq9h9ZWrFih7rzzTl3f47bb\nblNvvfWWru+hpQ0bNqgrr7xS10cvzpgxQz377LO6ja+18vJyXZ9IptS3T1zKz8/XbfxQdcstt6ii\noiLdxq+qqlJJSUmabUxiBQTXABe+8M6cOaPL+OvXr1fZ2dmmekZuY2Oj6tGjhzp48KAu43/11Vcq\nNTXVVM/I9fl86vLLL1ebNm3SZfza2lqVmJioTpw4ocv4erntttvUypUrdRnb4/Eop9OpiouLdRk/\nlK1Zs0Zdf/31uv3cmDdvnq4nGmZEcA0yc+ZMXZ5b2tzcrIYMGaLrb6p6efrpp3XZUcTn86nRo0er\n5557TtNxjbBy5Uo1dOhQXTaMnz59upo9e7bm4+pt48aNuu2INX/+fDVmzBjNxzUDj8ejBg8erN5+\n+23Nx66oqFA9evRQX3/9teZjmxnBNcg333yjnE6nWr9+vabjPvnkk2rcuHGmOru9wOPxqNzcXLVi\nxQpNx3311VfV8OHDTbnhus/nU2PGjFFPPfWUpuN+8sknqnfv3qZd3ps1a5Z64IEHNB1z9+7dtt+3\n9cI+w1rtvazUtxtO3HjjjbrtBGZmBNdA69evV2lpaaqsrEyT8d58803ldDp1213GCCUlJSolJUWz\nZdTPPvtMpaSkqL1792oyXjBUVVWpzMxMzVYtiouLVWpqqtq4caMm4wXD2bNn1aBBg9QLL7ygyXhH\njx5VvXv3tuUuQf/fggULlMvl0uSSl8/nU/n5+eqWW25RbW1tGszOWgiuwd555x2VlpbWpS3SfD6f\nWrJkicrMzDR1WC7YsGGDSklJUR999FGXxnnvvfdUSkqK+uMf/6jRzIKntLRUpaenq8LCwi6tXmze\nvFmlpqbqthezkSorK1X//v3V/Pnzu/TDfM+ePap3797q5Zdf1nB25uXz+dQ//MM/qGHDhqmqqqpO\nj9PU1KQeeOABdc0116j6+noNZ2gdBDcI1q5dq9LS0tRjjz0W8N2XVVVVasyYMSo3N1cdOHBApxka\n78svv1R9+vRR06dPD/haXV1dnZo2bZrq27ev2rFjh04zNN5XX32lsrOz1Y9+9KOAl/zOnz+v/umf\n/kmlp6erdevW6TRD49XU1KiRI0eq66+/PuCv/9bWVrVo0SKVnJysVq1apdMMzcnn86mFCxeqlJQU\n9frrrwf8S95///d/q0GDBql7773XVPtyG43gBsnJkyfVPffco5xOp1qwYEGHP1CLi4tVfn6+SkpK\nUvPnz1cej8egmRrn7NmzKj8/X6WkpKjHHnuswzuYKyoq1KOPPqqSk5PVww8/bMlv9JaWFvXzn/9c\nJSUlqdmzZ6vS0tJ2X19dXa3mz5+vMjMz1d/93d+pU6dOGTRT43i9XvXv//7vqnv37ur+++9X27Zt\nazcQtbW16sUXX1QDBgxQo0ePVkeOHDFwtuaye/dulZubq6666ir12muvqcbGxku+1uv1qnXr1qkf\n/ehHKi0tTa1evdrAmZqTQymTbIxpUSUlJbJs2TIpKiqSzMxMcblc0r9/f4mMjJSGhgYpLS2V0tJS\ncTgckp+fLzNnzvR7qz+zqqiokMLCQnn99dclLi5OcnNzZejQoRIdHS0tLS3y1VdfidvtlnPnzsn0\n6dMlPz+/w11yzK6mpkaWL18uv/71ryUsLExcLpcMGTJEYmNjxePxyMGDB8Xtdsvx48dlypQpMnv2\nbMnOzg72tHVVV1cnb7zxhixbtkzOnj0rLpdLcnJyJD4+Xtra2qSyslJ27dolhw4dkgkTJkhBQYFc\nffXVpnkQSrD4fD75r//6L1m2bJl89tlnMmTIEHG5XJKeni5hYWFy5swZKS4uvvgQlYKCApk8ebJp\nHqYSTAQ3RLS2tsq+ffvE7XZLZWWltLa2yvr16yUnJ0f+9V//Vfr27Wu7HxRer1emTJkiUVFR0r9/\nf/F4PBIdHS39+/cXl8slAwcO7PBpU1ajlJJDhw6J2+2W8vJyaW5uloULF8qKFSvE5XLJFVdcYYrH\ne2pJ/fmZ2W63W/bt2yeNjY0SGRkp6enpkpeXJ9nZ2X4/+hLf1djYeDGutbW14vV6JSEhQXJycsTl\ncklqamqwp2gqBDeEPfvss9LQ0CCLFi0K9lSC5tprr5Xnn39eRo4cGeyphCx/NnIAEHz2Oj0wmays\nLDl27FiwpxE0Xq9XysrKJCcnJ9hTAYAuI7ghzOl0dnkbOzOrqKiQtLS0gDcgB4BQRHBDmN3PcIuL\ni02zjRwAdITghjCn0ynV1dXi8/mCPZWgILgArITghrDY2FhJSEiQU6dOBXsqQUFwAVgJwQ1xdl5W\nJrgArITghji73jh14sQJ8Xg84nQ6gz0VANAEwQ1xdj3DLSkpkdzcXNs97AOAdRHcEGfX4LKcDMBq\nCG6II7gAYA0EN8QRXACwBoIb4ux401RjY6McPXpUBg0aFOypAIBmCG6I69mzpxw/fly8Xm+wp2KY\nPXv22HLXGwDWRnBDXHR0tCQlJcnJkyeDPRXDsJwMwIoIrgnY7TouwQVgRQTXBAguAJgfwTUBO904\nxR64AKyK4JqAnc5w2QMXgFURXBOwU3BZTgZgVQTXBAguAJgfwTUBggsA5udQSqlgTwLta21tlW7d\nusn58+clIiIi2NPRVUZGhuzYsUOysrKCPRXTcDgcwrcxEPo4wzWByMhISUlJkePHjwd7KrpiD1wA\nVkZwTcIOy8rsgQvAygiuSdghuFy/BWBlBNckCC4AmBvBNQk7PG2K4AKwMoJrElY/w2UPXABWR3BN\nwurBZQ9cAFZHcE3C6sFlORmA1RFck0hPT5fa2lrxeDzBnoouCC4AqyO4JhEeHi7p6elSU1MT7Kno\nguACsDqCayJWXVZmD1wAdkBwTcSqwWUPXAB2QHBNxKrBZTkZgB0QXBMhuABgXgTXRKz6tCmCC8AO\nCK6JcIYLAOZFcE3EisFlD1wAdkFwTSQ1NVXOnj0rzc3NwZ6KZtgDF4BdEFwTCQsLk8zMTEtdx2U5\nGYBdEFyTsdqNUwQXgF0QXJOx2nVcggvALgiuyVgpuOyBC8BOCK7JWCm47IELwE4IrslYKbgsJwOw\nE4JrMla6aYrgArATgmsynOECgDk5lFIq2JOA/5RSEhcXJ7W1tRIXFxfs6XSa1+uVxMREqa6uZlu+\nLnI4HMK3MRD6OMM1GYfDIU6n0/RnueyBC8BuCK4JWSG4LCcDsBuCa0JZWVmmv3GK4AKwG4JrQla4\ncYrgArAbgmtCBBcAzIfgmpDZg8seuADsiOCakNlvmmIPXAB2RHBNyOw3TbGcDMCOCK4JJSUlSWtr\nq5w7dy7YU+kUggvAjgiuCTkcDlNfxyW4AOyI4JqUWYPLHrgA7IrgmpRZb5xiD1wAdkVwTcqsN06x\nnAzArgiuSZl1SZngArArgmtSBBcAzIXgmpQZg+v1eqWsrExycnKCPRUAMBzBNakLN02ZaeNx9sAF\nYGcE16QSExMlLCxM6uvrgz0Vv7GcDMDOCK6JmW1ZmeACsDOCa2IEFwDMg+CaGMEFAPMguCZmpqdN\nsQcuALsjuCZmpqdNsQcuALsjuCZmpiVllpMB2B3BNTGCCwDmQXBNzOl0SlVVlSkefkFwAdgdwTWx\n+Ph4iY6Olrq6umBPpV3sgQsABNf0zLCszB64AEBwTc8MwWU5GQAIrukRXAAwB4JrcgQXAMyB4Jrc\nhTuVQxV74ALAtwiuyYX6GS574ALAtwiuyYV6cFlOBoBvEVyTczqdUl1dLT6fL9hT+V4EFwC+RXBN\nLjY2VhISEuTUqVPBnsr3IrgA8C2CawGhfOMUwQWAbxFcCwjV67jsgQsAf0FwLSBUg8seuADwFwTX\nAkI1uCwnA8BfEFwLILgAEPoIrgWE6k1TBBcA/oLgWkAonuGyBy4AfBfBtYCePXvK8ePHxev1Bnsq\nF7EHLgB8F8G1gOjoaElKSpKTJ08GeyoXsZwMAN9FcC0i1JaVCS4AfBfBtYhQu3GK4ALAdxFciwil\nM1z2wAWAv0ZwLSKUgsseuADw1wiuRYRScFlOBoC/RnAtguACQGgjuBYRSjdNEVwA+GsOpZQK9iTQ\nda2trdKtWzc5f/68REREBHUuGRkZsmPHDsnKygrqPOzC4XAI38ZA6OMM1yIiIyMlJSVFjh8/HtR5\nsAcuAHw/gmshoXAdlz1wAeD7EVwLCYXgcv0WAL4fwbWQULhxiuACwPcjuBbCGS4AhC6CayHBDi57\n4ALApRFcCwl2cNkDFwAujeBaSLCDy3IyAFwawbWQ9PR0qa2tFY/HE5T3J7gAcGkE10LCw8MlPT1d\nampqgvL+BBcALo3gWkywlpXZAxcA2kdwLSZYwWUPXABoH8G1mGAFl+VkAGgfwbWYYD1tiuACQPsI\nrsVwhgsAoYngWgzBBYDQRHAtJhjBZQ9cAOgYwbWY1NRUqa+vl+bmZsPekz1wAaBjBNdiwsLCJDMz\nU6qrqw17T5aTAaBjBNeCjF5WJrgA0DGCa0EEFwBCD8G1ICODyx64AOAfgmtBRgaXPXABwD8E14KM\nfNoUy8kA4B+Ca0FGnuESXADwD8G1IIILAKHHoZRSwZ4EtKWUkri4OKmtrZW4uDjd3sfr9UpiYqJU\nV1ezLV8QORwO4dsYCH2c4VqQw+GQnj176n6Wyx64AOA/gmtRWVlZut84xXIyAPiP4FqUEddxCS4A\n+I/gWhTBBYDQQnAtiuACQGghuBbldDp1DS574AJAYAiuRel90xR74AJAYAiuRem9pMxyMgAEhuBa\nVFJSkrS2tsq5c+d0GZ/gAkBgCK5FORwOXc9yCS4ABIbgWpheN06xBy4ABI7gWpheN06xBy4ABI7g\nWpheS8osJwNA4AiuhRFcAAgdBNfCCC4AhA6Ca2F63DTl9XqlrKxMcnJyNB0XAKyO4FrYhTNcLTcn\nZw9cAOgcgmthiYmJEhYWJvX19ZqNyXIyAHQOwbU4ra/jElwA6ByCa3EEFwBCA8G1OK1vnCK4ANA5\nBNfitHzaFHvgAkDnEVyL03JJmT1wAaDzCK7FaRlclpMBoPMIrsURXAAIDQTX4pxOp1RVVWny8AuC\nCwCdR3AtLj4+XqKjo6Wurq5L47AHLgB0DcG1AS2WldkDFwC6huDagBbBZTkZALqG4NoAwQWA4CO4\nNnDhxqmuILgA0DUE1wa6eobLHrgA0HUE1wa6Glz2wAWAriO4NtDV4LKcDABdR3BtwOl0SnV1tfh8\nvk4dT3ABoOsIrg3ExsZKfHy8nD59ulPHE1wA6DqCaxNdWVYmuADQdQTXJjobXPbABQBtEFyb6Gxw\n2QMXALRBcG2is8FlORkAtEFwbaKzT5sqLi6WoUOH6jAjALAXgmsTnOECQHARXJvoTHDZAxcAtENw\nbaJnz55y/Phx8Xq9fh+zZ88eGTRokERFRek4MwCwB4JrE9HR0ZKUlCQnT570+xiWkwFAOwTXRgK9\ncYrgAoB2CK6NBHodl+ACgHYIro0EEtwLe+DyJ0EAoA2CayOBBLeiokJSU1PZAxcANEJwbSSQ4LKc\nDADaIrg2EshNUwQXALRFcG2EM1wACB6HUkoFexIwRmtrq3Tr1k3Onz8vERER7b42IyNDtm/fLr16\n9TJodugsh8MhfBsDoY8zXBuJjIyUlJQUOX78eLuvO3HihLS0tEhWVpZBMwMA6yO4NuPPsjJ74AKA\n9giuzfhz4xTXbwFAewTXZvw5wyW4AKA9gmszBBcAgoPg2kxHwWUPXADQB8G1mY6Cyx64AKAPgmsz\nHd00xXIyAOiD4NpMRkaGnD59Wjwez/f+7wQXAPRBcG0mPDxc0tPTpaam5nv/d4ILAPoguDZ0qeu4\n7IELAPohuDZ0qeCyBy4A6Ifg2tClbpxiORkA9ENwbehSZ7gEFwD0Q3BtiOACgPEIrg0RXAAwHsG1\noe8LLnvgAoC+CK4NpaamSn19vTQ3N1/8b+yBCwD6Irg2FBYWJpmZmVJdXX3xv7GcDAD6igj2BGCs\nlpYWKSsrk4iICFmwYIE4nU6Ji4uTdevWyYQJE0QpxVluCFNKycGDB8XtdsuBAwcurlKsWLFCXC6X\nDB48WCIjI4M8SwDfx6GUUsGeBPSllJLt27fLsmXL5P3335e+fftKdna2XHbZZRIRESGNjY3y5Zdf\nyv79+yU+Pl5mzZol06dPlx49egR76viz6upqWb58uSxfvlzCw8MvxjUuLk5aWlrk0KFD4na7paam\nRu677z7Nk1l2AAAJKUlEQVQpKCiQ7OzsYE8bwP/BGa7FVVZWyoMPPigVFRVSUFAgL7300iVDqpSS\nnTt3ytKlS+Wyyy6Tn//85zJ37lwJDw83eNa4oKWlRZ555hl55ZVXZPLkyfLpp5/KlVdeecnX19TU\nyGuvvSZ33HGH3HDDDbJkyRJJTk42cMYALoUzXAt75513ZO7cufLII4/IY489FtBS48GDB2X69Oni\n9Xpl9erV0rNnTx1niu9TXl4u9957r/Tp00cKCwslIyPD72Obmppk3rx58vbbb8vrr78ut99+u44z\nBeAXBUtasmSJ6tWrlyopKen0GF6vVz3zzDOqb9++6siRIxrODh0pLS1V6enpqrCwUPl8vk6Ps3nz\nZpWWlqZ++9vfajg7AJ3BGa4F/fa3v5VHH31UNm/eLH369OnyeC+//LIsXbpUdu7cycYGBqiurpYR\nI0bIiy++KD/+8Y+7PF5JSYn88Ic/lNWrV8uoUaO6PkEAnUJwLaampkZyc3Nl3bp14nK5NBv3oYce\nEqWULF++XLMx8deUUnLXXXfJ8OHDZf78+ZqN+4c//EFmzZolZWVlkpCQoNm4APxHcC1m3Lhxkp2d\nLU8//bSm4549e1ays7PlN7/5jYwePVrTsfEXq1atkpdeekl27NghUVFRmo49Y8YMiY6OlqVLl2o6\nLgD/EFwL2bt3r9x2221y+PBhiY6O1nz8oqIiWb58uXz++eeaj41vz26vuOIKKSwslJtuuknz8evq\n6qRfv35SXl4uaWlpmo8PoH08acpCli1bJg8++GBAsf36668lJiZGpk6d2uFrJ06cKPv27ZP9+/d3\nZZq4hI0bN0pkZKTceOONfh/zySefyIgRIyQxMVEGDBggW7duveRru3fvLvfcc4/85je/0WK6AAJE\ncC1CKSVFRUUyY8aMgI57+OGHZcSIEX49XSoqKkqmTp0q7777bmeniXZc+Pfz90lfu3btkoceekhm\nzpwpJ0+elC1btki/fv3aPWbGjBlSVFSkxXQBBIjgWsThw4clNjZWevXq5fcx7777riQlJcmtt94q\n/l5ZuO6662TXrl2dnSbasXPnTrnuuuv8fv37778v06ZNk4ceekhiYmIkIyNDMjMz2z3G5XLJwYMH\npbGxsavTBRAggmsRf/rTnwK6K/ns2bPy1FNPya9+9Su/Yyvy7Q9st9vdmSmiHS0tLXLgwAHJycnx\n+5jf//730tLSIrm5uZKXlyeFhYXi8XjaPSYqKkoGDx4sJSUlXZ0ygADxaEeLOHnypDidTr9fP2/e\nPJk5c6ZkZmYGtFmB0+mU//mf/2GTA43V1dVJYmKixMTE+PX62tpa2bt3r4h8e2dzZGSkTJs2Tbp1\n6yb3339/u8c6nU45efJkl+cMIDAE1yK8Xq+Ehfm3YFFcXCwbNmyQ3bt3i4gEdIZ7IbI+n49nLGso\nkH8/Ebn4t7Q//elP5aqrrhIRkfz8fCkqKuowuOHh4eL1ejs/WQCdQnAtIj4+Xs6ePevXa//4xz/K\nkSNHLl7vbWhoEK/XK/v37+/w+uy5c+ckJiaG2Grswr+fvysHUVFR0rdv3+9E2t9j6+vrJT4+vkvz\nBRA4ruFaxJVXXun3dbmHHnpIDh06JCUlJVJcXCyzZs2SO++8Uz799NMOjy0pKWHbNx38zd/8jSQm\nJsrhw4f9PiY/P19WrFghpaWlsn//fnnttddk2rRp7R6jlOLfEAgSznAtIicnRw4cOCBNTU0SGxvb\n7mtjY2O/85r4+HiJjY31a/9bt9ut6SMj8Rcul0t27drV4Z/2XPAv//IvUldXJ2PGjJGMjAyZMWOG\njB8/vt1jjh07JuHh4R3ezQxAezxpykJuueUWmTVrlkyaNEm39xg5cqT84z/+o0yYMEG397CrJUuW\nyNatW3X9O+df/epX4na75a233tLtPQB8P4JrIWvWrJElS5bIpk2bdBm/tLRUxowZI0eOHJGICBZH\ntFZfXy99+/aVffv2SXp6uubj+3w+GTRokLzxxhsB/b0vAG1wDddCxo4dK4cOHdItuAsWLJDZs2cT\nW50kJibK5MmTZdGiRbqM/+6770pCQoJce+21uowPoH2c4VrM2rVrZc6cOVJaWqrpnai/+93v5N/+\n7d9k9+7dfv+tKAJXW1sr2dnZsnr1ahk5cqRm4548eVJycnJk7dq1Mnz4cM3GBeA/gmtBP/3pT6Wt\nrU1WrVoV0N92XsqBAwfkxhtvlA8//FCuueYaDWaI9nz00UfyyCOPyLZt2yQjI6PL43k8HrnrrrvE\n5XLpdvYMoGMsKVvQ0qVL5ejRo5Kfn9/lBxyUl5fL6NGjZeHChcTWIGPHjpWZM2fK6NGjpaampktj\nNTc3y6RJk6Rbt26a75EMIDAE14Li4uLkk08+kcOHD8vo0aMD+tvOC5RS8uabb8rIkSPlF7/4hUyf\nPl2HmeJSfvazn8nUqVNlxIgR8vHHH3dqjLKyMrn++uslJiZGVq9ezbV3INgULKutrU09//zzqkeP\nHuqZZ55RJ0+e7PAYn8+ntm7dqsaMGaOys7OV2+02YKa4lI0bN6p+/fqpyZMnq927d/t1TGVlpXr8\n8cdVcnKyeu2115TP59N5lgD8wTVcGygvL5fFixfL+++/L3/7t38rN9xwg+Tl5Unv3r0lMjJSzp07\nJ2VlZeJ2u+Wjjz6SpqYmKSgokIKCAomKigr29G2voaFBXn75ZSksLBSn0yljxowRl8slQ4YMkbi4\nOPF4PFJRUSFut1s2bdokW7dulSlTpshjjz0mWVlZwZ4+gD8juDZSV1cn77//vuzcuVN27dolNTU1\n0traKnFxcTJkyBBxuVxy8803y80336zJzVbQVltbm/zhD3+QLVu2iNvtlvLycmlqapLIyEjp06eP\nuFwuufrqq2X8+PE8KxkIQQQXAAADcBoDAIABCC4AAAYguAAAGIDgAgBgAIILAIABCC4AAAYguAAA\nGIDgAgBgAIILAIABCC4AAAYguAAAGIDgAgBgAIILAIABCC4AAAYguAAAGIDgAgBgAIILAIABCC4A\nAAYguAAAGIDgAgBgAIILAIABCC4AAAYguAAAGIDgAgBgAIILAIABCC4AAAYguAAAGIDgAgBgAIIL\nAIABCC4AAAYguAAAGIDgAgBggP8FUTP6R8cDFQMAAAAASUVORK5CYII=\n",
       "text": [
        "<matplotlib.figure.Figure at 0x10dbcce50>"
       ]
      }
     ],
     "prompt_number": 46
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "So for a `find` operation, we start at our element of interest.  If it points to itself, then we return it.  Otherwise, we call `find` on the element it points to.  This will give us the representative of the set for every element in the set, and will run in time proportional to the depth of the trees.  `union` operations can be done by first finding the representatives of the two elements to be merged, and then changing the representative of one to point to the other.  For example, if we called `union(1, 2)`, the representatives of those sets are 4 and 6 respectively.  We would then change 4 to point not to itself but instead to 6, or vice versa: "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "G = nx.DiGraph()\n",
      "A = [1, 2, 3, 4, 5, 6, 7]\n",
      "S = [4, 6, 3, 6, 4, 6, 7]\n",
      "for element in A:\n",
      "    G.add_node(element)\n",
      "for i, root in enumerate(S):\n",
      "    G.add_edge(i+1, root)\n",
      "labels = dict((u, \"%d\" % (u)) for u in G.nodes())\n",
      "    \n",
      "nx.draw_graphviz(G, prog='dot', node_color='white', node_size=700, arrows=False)\n",
      "print S"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[4, 6, 3, 6, 4, 6, 7]\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAdwAAAFBCAYAAADdWx5oAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XtYVPW+BvAXBxFBUxIQJREQhIMXQEBKUCFMQ5RwbzW8\n4E5RMY6XBLqcMrWT+7g7W+bgQQWfjERNfZ4009QOFbuyUHGLomhqpIMgZoHihTvM/M4fHdx7n10y\nA2vWmmHez99r/dbbMzkv35k1v2UlhBAgIiIio+qmdAAiIiJLwMIlIiKSAQuXiIhIBixcIiIiGbBw\niYiIZMDCJSIikgELl4iISAYsXCIiIhmwcImIiGTAwiUiIpIBC5eIiEgGLFwiIiIZsHCJiIhkwMIl\nIiKSAQuXiIhIBixcIiIiGbBwiYiIZMDCJSIikgELl4iISAYsXCIiIhmwcImIiGTAwiUiIpIBC5eI\niEgGLFwiIiIZsHCJiIhkYK10AFPQ3NyMqqoqtLa2omfPnnBycoKVlZXSsej/PHjwAHfv3oUQAn37\n9sVjjz2mdCT6P0IIVFdXo76+HtbW1nBycoKNjY3SsUhmTU1NqK6uRmtrK+zs7ODo6Mj30F9hkYUr\nhEBhYSF27tyJU6dO4bvvvkOfPn1gbW2Nuro6WFlZYdSoUYiIiMD8+fMxYMAApSNblKamJnz00Uc4\nePAgTp8+jR9//BGPP/44AODOnTtwcXFBcHAwYmNjMX36dPTo0UPhxJblp59+Qk5ODr766isUFRVB\np9OhV69eaG1txd27d+Hn54fRo0cjISEBTz75JN94uyAhBAoKCvDBBx/g1KlTuHTpEvr27Qtra2vU\n1tZCpVIhKCgIkZGRmD9/PpydnZWObBIs7iPlw4cPIygoCHPnzsWgQYOwceNG/Pzzz7h58ybKy8tx\n+/ZtlJSUYPny5SgvL4efnx/i4+Nx/fp1paN3eU1NTVi3bh0GDx6M9957D88++ywOHTqE+/fvo6Ki\nAhUVFbh//z4OHz6MmJgY5Obmws3NDW+99RaampqUjt/llZeXY86cOfD19YVGo8HSpUtx/vx53Llz\nB+Xl5bh58yaqq6uRmZmJwYMHY968eRg1ahQOHjyodHSS0EcffYSAgAAkJibC09MTmzdvRnV19T+8\nhxYXFyM5ORmlpaXw8fFBQkICKisrlY6uPGEh7ty5IxISEoSnp6f45JNPhFar1eu8u3fvirffflv0\n69dPZGVlCZ1OZ+SklqmoqEgMHz5cTJ06VVy6dEnv865cuSLi4uKEn5+fOHXqlBETWi6dTifeffdd\n4ejoKN566y1RU1Oj13larVYcOXJEeHl5idmzZ4vq6mojJyVjqqqqEjNnzhRDhw4Vn376qd7voXfu\n3BGrV68WTk5O4v3337fo91CLKNzr16+LoUOHiuTkZFFbW9uhNS5evChGjRolEhMTRWtrq8QJLduB\nAweEk5OT2LlzZ4f+Mep0OrF7927h5OQkPvzwQyMktFytra0iKSlJ+Pv7i5KSkg6tUVdXJ5YtWyaG\nDBkiNBqNtAFJFj/88IPw8PAQK1euFPX19R1ao7i4WAwfPlwsXbpU77Luarp84f74449iyJAhIj09\nvdNrPXjwQERGRoqFCxda9F9pUjpy5IhwdnYWp0+f7vRaZ8+eFf379xcHDx6UIBnpdDqxZMkSMXbs\nWHH//v1Or7dx40bh4eEhKisrJUhHcqmoqBCDBw8WW7Zs6fRad+/eFWPGjBHLly+3yPfQLl24Op1O\nTJo0Sbz++uuSrfngwQMxcuRIkZOTI9malurGjRvCyclJHD9+XLI1T506JRwdHcX169clW9NS7dix\nQwwbNkzcu3dPsjVXr14toqKiLPLN1hxptVoxbtw4sW7dOsnWrKmpEb6+vmLv3r2SrWkuunThbtu2\nTYwaNUo0NzdLum5xcbFwdHQUFRUVkq5rSXQ6nZg8ebJYu3at5GuvW7dOPPPMM3xT74SbN28KJycn\nUVRUJOm6LS0tYvTo0SIrK0vSdck4Nm7cKMLCwiT/Gq2wsFD0799f3Lp1S9J1TZ2VEEIofeOWMTQ0\nNMDNzQ35+fkYOXKk5OuvWrUKN2/eRE5OjuRrW4K8vDykpKSguLgY3bt3l3Tt1tZWBAUF4Y9//COm\nTJki6dqWIikpCQ4ODvjTn/4k+drfffcdxo0bh+vXr8Pe3l7y9Uka9+/fh7u7O06ePImhQ4dKvn5K\nSgqam5uxadMmydc2WUo3vrG8//77Ijo6Wq9jMzMzRVBQkOjRo4d44YUX9Drn559/Fn369BG3b9/u\nTEyLNXXqVPHuu+/qdez48eOFra2t6NWrl+jVq5fw9fVt95zt27fr/frTP6qpqRF9+/YVP/74o17H\nz5kzR7i4uIi+ffuKiIgIkZ2d3e45sbGxer/+pIzNmzeL6dOnt3ucvb39w3+bvXr1EiqVSixbtqzd\n8yoqKoSDg4Mk9weYiy5buGPGjBGffPKJXsd+9NFH4uOPPxYvvvii3oUrxC9vNBs3buxoRItVWVkp\nHn/8cVFXV6fX8REREeK9994z6Br19fX8LreDtmzZIp5//nm9j79w4YJoaGgQOp1OnDx5UvTp00dc\nuHDhked8+umnIiQkpLNRyYj8/f1Ffn6+QefU1taKXr16iW+++Uav4+Pi4izqD68uufFFY2Mjzp49\niwkTJuh1/LRp0/Dcc8+hX79+Bl0nOjoa3377bUciWrTjx48jPDwcdnZ2ep8jDPzmo2fPnhg3bhyO\nHz9uaDyL98033yA6Olrv44cNGwZbW1vodDpYWVnB2toatra2jzzn6aefxoULF1BXV9fZuGQE9+7d\nww8//IBx48YZdN6+ffvQv39/hIeH63W8pb2HdsnCPX/+PIYOHdruP/r/z9A39aCgIJw+fdqgcwg4\nffo0goKCDDrn3/7t3zBo0CAsX74c586d0+scvj4d05HXJzk5Gb169UJ4eDj27NmDIUOGPPJ4Gxsb\n+Pn56f1akrzOnDkDf39/WFsbtvtvbm4u5s2bp/fxwcHBFvVvtEsW7vfffw8/Pz+DzzN0z9ehQ4ei\noqICzc3NBl/Lkhn6+rzzzjvQaDQoKirCwIEDER0dDa1W2+55fn5+uHLlSmeiWhydToerV6/C19fX\noPO2bNmCO3fuIDc3FzNnzsR3333X7jl8fUxXR95Dr1+/jmPHjuEPf/iD3udY2v8DXbJwGxoa0LNn\nT4PPM3TC7datG3r06MF9fA1k6OszevRo2Nvbw9nZGa+99hocHR1x+PDhds+zs7NDY2NjZ6JanKam\nJlhbWxs82QC/fIw/a9YsREZGYv/+/e0ez9fHdDU2Nhr8Hrpz506MHTsWgwcP1vucHj16QKvV6vUH\ndFfQJQvXxsamQ1OnoROuEALNzc2S/6ylq+vo69PGyspKrz+O+NoYzsbGBi0tLQb/8fn36urq9HrC\nFl8f09WRf6M7duwwaLoF8LBou3XrklX0T7rkf+XgwYNx9epVvY/XarVobGxEa2srtFotmpqa9PqL\nq6KiAo8//jgfD2cgQ16fe/fuIS8vD42NjaiursaGDRtQXV2N2NjYds/94Ycf4O7u3sm0lkWlUmHg\nwIHQaDR6HV9VVYW9e/eitrYWNTU1yM3NRWFhIWbNmtXuuT/88INB0xDJx83NzaD30OPHj+PmzZuY\nMWOGQddp+zdqKY9w7JKFGxgYiPPnz6O1tVWv499++23Y2dnhnXfewa5du9CzZ0/88Y9/bPe8oqIi\nBAUFWcz/LFIJCgpCUVGRXse2tLTgzTffhLOzM4KDg1FeXo6DBw/q9Rdx2+tDhjHk9bGyskJ2djYG\nDRoEf39/FBYW4vDhw+1uaKHT6VBcXMzXx0S1/T+g7ycdO3bswO9//3uDNzKxtH+jXXanqWHDhmHb\ntm146qmnjHaNFStWoF+/fli9erXRrtEVXblyBVFRUbh+/TpUKpVRrqHVauHp6YkjR45g+PDhRrlG\nV7V+/XrcuHEDmzdvNto1/vrXv2LOnDn4/vvvjXYN6hx3d3ccPHgQ/v7+RrvGwoUL4evri7S0NKNd\nw5R0yQkXAF544QVs3brVaOvX19fjgw8+MOgWePqFj48PBg0ahCNHjhjtGnl5eXB2dmbZdsDcuXOx\nZ88e1NbWGu0aW7duxfz58422PnXe/Pnzjfoeeu/ePezfvx9z5swx2jVMTZct3Pnz5+Pjjz/Gjz/+\naJT1d+zYgaeeeorfEXZQcnIyMjIyOnVzzm8RQmDjxo1ITk6WfG1LMGjQIIwfPx7bt283yvo///wz\n9u/fj8TERKOsT9JYtGgR9u7di9u3bxtl/ffeew8TJ07U6wa7LkOhHa5k8frrr4u4uDjJnxpjrCep\nWJKmpiYxYsQIsWPHDsnX3r17t/Dz8xONjY2Sr20piouLhZOTk7hx44bka0+fPl28/PLLkq9L0lux\nYoWYPXu25OuWlZUJR0fHdrcA7Wq6dOE2NjaKYcOGSfqmrtVqxZQpU8SqVaskW9NSFRUVCScnJ1Fe\nXi7Zmjdu3BDOzs7i1KlTkq1pqdauXSueffZZSR/Ntnv3buHr6ysaGhokW5OMp66uTnh5eYkPP/xQ\nsjVbWlpEVFSU+I//+A/J1jQXXbpwhfjbX+p5eXmdXkur1Yrk5GQxduxY0dTUJEE6UqvVwtfXV5Ln\nYv78889i2LBh4p133pEgGTU3N4uIiAixaNEiodVqO73eF198wU+GzNCpU6eEo6Oj+Oqrrzq9Vmtr\nq3jhhRfEM888I1paWiRIZ166fOEKIcS3334rnJycxLZt2zr88fK9e/fE7NmzxZgxY8Tdu3clTmjZ\n3nrrLeHt7S2Ki4s7vMb58+eFj4+PePPNN/ngeQndv39fjB07Vjz//POipqamQ2vodDqxfft24eTk\nJL7++muJE5Ic8vPzhaOjo9i1a1eH/33duXNH/P73vxeRkZGitrZW4oTmwSIKVwghSkpKREBAgJg8\nebJBj2zT6XTi008/FW5ubmLRokUW+z+Kse3YsUM4OTmJtWvXGvRxY2Njo1i3bp1wdHQUOTk5Rkxo\nuerq6sSSJUvEE088IQ4fPmzQG25FRYWYOnWqGDFiRKf+oCLlnTlzRgwbNkzExcWJyspKvc/T6XTi\n4MGDwtXVVSxdutSiv06wmMIV4pePyN566y3h4OAgpk+fLj777LPfLNDKykqxdetW4e3tLQYPHizJ\nR9L0aDdu3BCxsbGid+/eIi0tTZw/f/5Xvz9sbW0VJSUl4rXXXhPOzs4iNjZW0u+B6dd98cUXwtfX\nV4wcOVJkZ2f/5ptuXV2d+Pzzz8XMmTOFg4ODWL16Nb+C6SIaGxvF66+/Lvr27Svi4+NFfn7+rz7X\nWqfTiYqKCrF582YxbNgw4efnJ8lH0uauy2588SgPHjzArl27kJubi/Pnz8PDwwMeHh7o3r07amtr\nceHCBbS0tGD8+PEYOHAgKioq8PHHHysd2yLs2bMHGRkZGDt2LA4ePIgff/wRI0eOhJOTEwCguroa\n58+fR//+/REbG4sXX3wR3t7eCqe2HEII/OUvf0F2dja++uorWFtbY/jw4ejVqxdaWlpQVlaGa9eu\nYcSIEZg3bx4SEhLw2GOPKR2bJHb37l3s2LEDu3btwoULFzBkyBAMHjwY3bt3x4MHD1BSUgIhBCIj\nI7FkyRJERERwRz504Z2m9NXc3IyLFy/ixo0baGlpQc+ePeHn5wc3NzdYWVmhvr4e7u7uKCgo4Bu7\nkQkhEBISgjVr1mDq1KkAfvmHfe7cOdy9exdCCPTt2xcBAQHo27evwmlJCIHy8nJcunQJ9fX16N69\nO1xdXTF8+HDY2NgoHY9k0tTUhAsXLuDmzZtoaWmBnZ0dhg0bhieeeIIl+/9YfOHqY9WqVaipqTHq\nVncEfP3110hKSsJ3331nMU8PISLLwcLVw61bt+Dn54fS0lL069dP6ThdVmxsLGJiYpCUlKR0FCIi\nyXGM0IOLiwvi4uKQnZ2tdJQu68qVKygsLOTe1ETUZXHC1dPFixcxYcIEaDQa2NraKh2ny0lKSsKA\nAQOwdu1apaMQERkFC9cA0dHRmDFjBhYsWKB0lC6lqqoKPj4+uHz5MpydnZWOQ0RkFPxI2QCpqalQ\nq9VGecKNJduyZQumT5/OsiWiLo2Fa4CoqCioVCrk5eUpHaXLaGhoQFZWFlJSUpSOQkRkVCxcA1hZ\nWSE1NRXp6elKR+kydu3aheDgYPj6+iodhYjIqPgdroGam5vh6emJw4cPIyAgQOk4Zk2n08HPzw/Z\n2dmIiIhQOg4RkVFxwjWQjY0Nli1bBrVarXQUs3f06FHY29tj/PjxSkchIjI6TrgdUFNTgyFDhqCk\npASurq5KxzFbkZGRWLRoEWbPnq10FCIio+OE2wEODg5ISEhAZmam0lHM1pkzZ3D16lXMmDFD6ShE\nRLLghNtBGo0GISEh0Gg06N27t9JxzM6cOXMQGBiItLQ0paMQEcmChdsJM2fORFhYGFasWKF0FLNS\nXl6OwMBAXLt2DX369FE6DhGRLFi4nVBYWIj4+HiUlpbC2tpa6ThmIy0tDUII/ryKiCwKC7eTwsPD\nsWLFCn4Xqaf79+/Dw8MDZ8+ehZubm9JxiIhkw5umOqltIwz+3aKfbdu2YeLEiSxbIrI4nHA7SavV\nwsfHB7m5uQgLC1M6jklraWmBl5cX9u/fj+DgYKXjEBHJihNuJ6lUKqSkpGDDhg1KRzF5+/btg4eH\nB8uWiCwSJ1wJ1NfXw93dHQUFBfD29lY6jkkSQiAkJARr1qzB1KlTlY5DRCQ7TrgSsLOzw+LFi5GR\nkaF0FJN17Ngx1NbWIiYmRukoRESK4IQrkVu3bsHPzw+lpaXo16+f0nFMTmxsLGJiYpCUlKR0FCIi\nRXDClYiLiwvi4uKQnZ2tdBSTc+XKFRQWFmLevHlKRyEiUgwnXAldvHgREyZMgEajga2trdJxTEZS\nUhIGDBiAtWvXKh2FiEgxLFyJRUdHY8aMGViwYIHSUUxCVVUVfHx8cPnyZTg7Oysdh4hIMfxIWWKp\nqalQq9XcCOP/bNmyBdOnT2fZEpHFY+FKLCoqCiqVCnl5eUpHUVxDQwOysrKQkpKidBQiIsWxcCVm\nZWX1cLtHS7dr1y4EBwfD19dX6ShERIrjd7hG0NzcDE9PTxw+fBgBAQFKx1GETqeDn58fsrOzERER\noXQcIiLFccI1AhsbGyxbtgxqtVrpKIo5evQo7O3tMX78eKWjEBGZBE64RlJTU4MhQ4agpKQErq6u\nSseRXWRkJBYtWoTZs2crHYWIyCRwwjUSBwcHJCQkIDMzU+kosjtz5gyuXr3KZwQTEf0dTrhGpNFo\nEBISAo1Gg969eysdRzZz5sxBYGAg0tLSlI5CRGQyWLhGNnPmTISFhWHFihVKR5FFeXk5AgMDce3a\nNfTp00fpOEREJoOFa2SFhYWIj49HaWkprK2tlY5jdGlpaRBC8GdRRET/DwtXBuHh4VixYkWX/07z\n/v378PDwwNmzZ+Hm5qZ0HCIik8KbpmTQthFGV//bZtu2bZg4cSLLlojoV3DClYFWq4WPjw9yc3MR\nFhamdByjaGlpgZeXF/bv34/g4GCl4xARmRxOuDJQqVRISUnBhg0blI5iNPv27YOHhwfLlojoN3DC\nlUl9fT3c3d1RUFAAb29vpeNISgiBkJAQrFmzBlOnTlU6DhGRSeKEKxM7OzssXrwYGRkZSkeR3LFj\nx1BbW4uYmBiloxARmSxOuDK6desW/Pz8UFpain79+ikdRzKxsbGIiYlBUlKS0lGIiEwWJ1wZubi4\nIC4uDtnZ2UpHkcyVK1dQWFiIefPmKR2FiMikccKV2cWLFzFhwgRoNBrY2toqHafTkpKSMGDAAKxd\nu1bpKEREJo2Fq4Do6GjMmDEDCxYsUDpKp1RVVcHHxweXL1+Gs7Oz0nGIiEwaP1JWQGpqKtRqtdlv\nhLFlyxZMnz6dZUtEpAcWrgKioqKgUqmQl5endJQOa2hoQFZWFlJSUpSOQkRkFli4CrCysnq43aO5\n2rVrF4KDg+Hr66t0FCIis8DvcBXS3NwMT09PHD58GAEBAUrHMYhOp4Ofnx+ys7MRERGhdBwiIrPA\nCVchNjY2WLZsGdRqtdJRDHb06FHY29tj/PjxSkchIjIbnHAVVFNTgyFDhqCkpASurq5Kx9FbZGQk\nFi1ahNmzZysdhYjIbHDCVZCDgwMSEhKQmZmpdBS9nTlzBlevXu3yz/YlIpIaJ1yFaTQahISEQKPR\noHfv3krHadecOXMQGBiItLQ0paMQEZkVFq4JmDlzJsLCwrBixQqlozxSeXk5AgMDce3aNfTp00fp\nOEREZoWFawIKCwsRHx+P0tJSWFtbKx3nN6WlpUEIYdY/ZyIiUgoL10SEh4djxYoVJvvd6P379+Hh\n4YGzZ8/Czc1N6ThERGaHN02ZiLaNMEz1759t27Zh4sSJLFsiog7ihGsitFotfHx8kJubi7CwMKXj\n/IOWlhZ4eXlh//79CA4OVjoOEZFZ4oRrIlQqFVJSUrBhwwalo/yTffv2wcPDg2VLRNQJnHBNSH19\nPdzd3VFQUABvb2+l4wAAhBAICQnBmjVrMHXqVKXjEBGZLU64JsTOzg6LFy9GRkaG0lEeOnbsGGpr\naxETE6N0FCIis8YJ18TcunULfn5+KC0tRb9+/ZSOg9jYWMTExCApKUnpKEREZo0TrolxcXFBXFwc\nsrOzlY6CK1euoLCwEPPmzVM6ChGR2eOEa4IuXryICRMmQKPRwNbWVrEcSUlJGDBgANauXatYBiKi\nroKFa6Kio6MxY8YMLFiwQJHrV1VVwcfHB5cvX4azs7MiGYiIuhJ+pGyiUlNToVarFdsIY8uWLZg+\nfTrLlohIIixcExUVFQWVSoW8vDzZr93Q0ICsrCykpKTIfm0ioq6KhWuirKysHm73KLddu3YhODgY\nvr6+sl+biKir4ne4Jqy5uRmenp44fPgwAgICZLmmTqeDn58fsrOzERERIcs1iYgsASdcE2ZjY4Nl\ny5ZBrVbLds2jR4/C3t4e48ePl+2aRESWgBOuiaupqcGQIUNQUlICV1dXo18vMjISixYtwuzZs41+\nLSIiS8IJ18Q5ODggISEBmZmZRr/WmTNncPXqVZN9Ji8RkTnjhGsGNBoNQkJCoNFo0Lt3b6NdZ86c\nOQgMDERaWprRrkFEZKlYuGZi5syZCAsLw4oVK4yyfnl5OQIDA3Ht2jX06dPHKNcgIrJkLFwzUVhY\niPj4eJSWlsLa2lry9dPS0iCEUORnSEREloCFa0bCw8OxYsUKyb9jvX//Pjw8PHD27Fm4ublJujYR\nEf2CN02ZkbaNMKT+G2nbtm2YOHEiy5aIyIg44ZoRrVYLHx8f5ObmIiwsTJI1W1pa4OXlhf379yM4\nOFiSNYmI6J9xwjUjKpUKKSkp2LBhg2Rr7tu3Dx4eHixbIiIj44RrZurr6+Hu7o6CggJ4e3t3ai0h\nBEJCQrBmzRpMnTpVooRERPRrOOGaGTs7OyxevBgZGRmdXuvYsWOora1FTEyMBMmIiOhROOGaoVu3\nbsHPzw+lpaXo169fh9eJjY1FTEwMkpKSJExHRES/hhOuGXJxcUFcXByys7M7vMaVK1dQWFiIefPm\nSZiMiIh+CydcM3Xx4kVMmDABGo0Gtra2Bp+flJSEAQMGYO3atdKHIyKif8LCNWPR0dGYMWMGFixY\nYNB5VVVV8PHxweXLl+Hs7GykdERE9Pf4kbIZS01NhVqtNngjjC1btmD69OksWyIiGbFwzVhUVBRU\nKhXy8vL0PqehoQFZWVlISUkxYjIiIvr/pN8Fn2RjZWX1cLvHkSNH4qOPPsLp06dRVFSEn3/+GVqt\nFr1798aIESMQFBSEiRMnoqSkBMHBwfD19VU6vsUQQuDUqVPIy8tDUVERSkpK8ODBA3Tr1g1OTk4I\nCgpCcHAwpk2bhieeeELpuERkJPwO18wdP34cU6dOhVarxbRp0/DUU08hKCgIrq6uUKlUuHv3Ls6d\nO4fTp09j3759qKmpwcKFC7F+/Xp068YPOIxJp9Nh586d2LhxI+7du4fp06cjODgY/v7+6Nu3L3Q6\nHW7evImioiKcOHECH3/8MSIjI/HKK68gNDRU6fhEJDEWrplqbGzE6tWrsWPHDrzxxhv4wx/+gMce\ne+yR5+h0Onz++ef493//d6hUKuTk5MDLy0umxJbl2rVrSExMRENDA9auXYuJEye2+wfOgwcPsHPn\nTrz99tuYPXs23n77bdjZ2cmUmIiMjSOOGbp16xaefPJJaDQalJSUYNmyZe2WLQB069YNkyZNwrFj\nx/C73/0OTz31FD799FMZEluWzz77DKGhoZgyZQoKCgrw7LPP6vVpQu/evZGcnIySkhLcvHkToaGh\nuHnzpgyJiUgOnHDNTFVVFcaNG4dZs2bhzTffhJWVVYfXOnnyJJ577jls374d0dHREqa0XJ9//jnm\nzJmDAwcOdPqJTuvXr8f777+Pb775Bv3795coIREphYVrRnQ6HSZMmIDQ0FCsX79ekjVPnDiB2NhY\nFBYWwtPTU5I1LdX169cRHByMAwcOIDw8XJI1V69eja+++gpfffUVv3MnMnP8F2xGsrOz0dDQgHXr\n1km25lNPPYVXX30ViYmJ0Ol0kq1raYQQSExMRGpqqmRlCwBr1qyBTqfDpk2bJFuTiJTBCddM3L59\nG0OHDkVBQYHkP+nRarUICwvD0qVLMXfuXEnXthR79+7Fhg0bcPLkSVhbS/tru9LSUjz55JO4fPky\nnJycJF2biOTDCddMbN++HTExMUb5/axKpcKqVauQmZkp+dqWIjMzE6tWrZK8bAHA29sbcXFxyMnJ\nkXxtIpIPC9cMCCGQlZWF5ORkg84rLS2Fra0tEhIS2j02OjoaP/30E4qKijoa02KdO3cOFRUVmDJl\nSrvHNjc3IzExEe7u7nByckJCQgIKCgraPS85ORlZWVn82J/IjLFwzUBZWRkaGhoM3gzhX//1XzF6\n9Gi97mRWqVT43e9+hy+++KKjMS3WF198geeee06v6ba1tRVubm44duwYKisrERERgfj4eLS2tj7y\nvKCgIAAWjLZpAAAUpklEQVTA1atXJclMRPJj4ZqBoqIiBAcHG/QToL1798LBwQFRUVF6P9wgKCiI\nE24HtL0++rCzs8OaNWvg5uYGGxsbJCYmwtbWFvn5+e2eGxQUhNOnT3c2LhEphIVrBkpKSjBy5Ei9\nj79//z7WrFmD//qv/zLoSUL+/v4oKSnpSESLZujr8/cqKytRWVmp10+y+PoQmTcWrhmora1Fnz59\n9D7+zTffxMKFCzFw4ECDpuLHHnsMtbW1HYlo0Qx9fdo0Nzdjzpw5WLRoEby9vds9/rHHHkNdXV1H\nIhKRCeDTgsyASqWCVqvV69ji4mLk5+fj7NmzAGDQhKvVaqFSqTqU0ZIZ8vq00el0mDt3Lnr37g21\nWq3XOXx9iMwbC9cMuLi4QKPR6HXs119/jbKyMri5uQH4ZfrSarW4dOlSu9//3bhxg1sIdoCLiwtu\n3Lih15QK/G2TjOrqanz66ad6lyhfHyLzxo+UzcCoUaP0vplp8eLFuHbtGs6dO4fi4mIsWbIEMTEx\nej2kvqio6OHdsKQ/Q14f4Jef+Fy+fBmffPIJevToofd5htycRUSmh4VrBkaNGoWSkhLU19e3e2zP\nnj3h7OwMZ2dn9O/fH7169ULPnj3Rr1+/ds89ceIE39A7ICQkBMePH9fr2OvXr2Pr1q04d+4cXFxc\n0Lt3b/Tu3Rt79ux55HmNjY0oLi7GqFGjpIhMRArg1o5mYurUqZg2bRoWLFhglPWrq6vh7e2NH374\nQa9ypr+5e/cuPDw8cPnyZaN95Ltjxw7s2bOHj1MkMmOccM1EcnIyNm3aZNBNUIbYtm0b4uLiWLYd\n0LdvX0yfPh3vvvuuUdYXQmDz5s0G7zRGRKaFhWsmJk2ahG7duuG9996TfO2Kigqkp6cjLS1N8rUt\nRWpqKjZu3IiysjLJ187NzUVTUxMmT54s+dpEJB9+pGxGSkpK8PTTT6OoqOjhXcidJYRAdHQ0wsPD\nsWrVKknWtFR/+tOf8MUXX+Czzz6T7Nm1lZWVCAwMxGeffYaAgABJ1iQiZXDCNSMjRozAa6+9hilT\npuDOnTudXk8IgbS0NDx48ACvvvqqBAktW1paGlpaWvDSSy9J8tF/TU0NpkyZgtTUVJYtURfAwjUz\nKSkpmDx5MsaPH4/r1693eJ3m5mYsXboUX375JQ4fPozu3btLmNIyWVtb4+DBgzhx4gSWLFmCpqam\nDq9VXl6OyMhIREVF4ZVXXpEwJREphYVrZqysrLB+/XosWLAAwcHB2Lp1q8HT1JkzZxAcHIyKigp8\n+eWXcHBwMFJay9O3b1/k5+ejqqqqQw8bEEJg27ZtCAoKwty5c/HnP//ZoO05ich08TtcM3bx4kXM\nnz8fTU1NSE5Oxpw5c9CrV69fPVYIgb/85S/485//jDNnziA9PR1z587lm7mRCCGwZ88erFy5Ev7+\n/nj55ZcRFRX1m9/t1tXVYffu3di8eTOsra3x/vvvY8SIETKnJiJjYuGaubYi3bJlC/7nf/4H//Iv\n/4KgoCAMHDgQ3bp1w71793Du3DkUFRVh0KBBsLa2xvPPP8+PKWWiVquxc+dOAL9sejFq1CgEBASg\nT58+0Ol0uHnzJoqKinDp0iVMnDgRycnJjyxmIjJfLNwupL6+/mG5VlVVQavVolevXhgxYgSCgoLg\n4uKCwsJCxMfHo7S0VK8HplPHabVa+Pj4IDc3F2FhYfjpp59QVFSEkpISPHjwACqVCo6OjggKCoK/\nvz/s7e2VjkxERsTCtUDh4eFYsWIFZsyYoXSULu3AgQN45513cOLECX50T0S8acoSpaamYsOGDUbb\ntYp+kZ6ejtTUVJYtEQFg4Vqk2NhY3L59GwUFBUpH6bJOnjyJyspKTJs2TekoRGQiWLgWSKVSISUl\nBenp6UpH6bLS09OxcuVKfk9ORA/xO1wLVV9fD3d3dxQUFOj94HTSj0ajQUhICMrKyn7zZ1pEZHk4\n4VooOzs7LF68GBkZGUpH6XIyMjKwcOFCli0R/QNOuBbs1q1b8PPzQ2lpKR/LJ5GamhoMGTIEJSUl\ncHV1VToOEZkQTrgWzMXFBXFxccjKylI6SpexdetWTJkyhWVLRP+EE66Fu3jxIiZMmACNRgNbW1ul\n45i15uZmeHh44OjRo/D391c6DhGZGE64Fm7YsGEICAjA7t27lY5i9vbu3Qs/Pz+WLRH9KhYuITU1\nFWq1mhthdIIQ4uFGF0REv4aFS4iKioJKpUJeXp7SUcxWfn4+tFotJk2apHQUIjJRLFyClZXVw+0e\nqWM2bNiAlJQUbuNIRL+JN00RgF9u+PH09MThw4cREBCgdByzcuHCBTzzzDMoKytDjx49lI5DRCaK\nEy4BAGxsbLBs2TKo1Wqlo5gdtVqNpUuXsmyJ6JE44dJD3LTBcNw8hIj0xQmXHnJwcEBCQgIyMzOV\njmI2Nm3ahFmzZrFsiahdnHDpH7RtvK/RaNC7d2+l45i0uro6uLu748SJE/Dy8lI6DhGZOE649A88\nPDzw9NNPIycnR+koJm/79u0YO3Ysy5aI9MIJl/5JYWEh4uPjUVpayue5/gatVgsfHx/k5uYiLCxM\n6ThEZAY44dI/CQ0NhaurKw4cOKB0FJN16NAhODo6YsyYMUpHISIzwcKlX9W2EQY/APl1bds4cqML\nItIXC5d+VWxsLG7fvo2CggKlo5ickydPorKyEtOmTVM6ChGZERYu/SqVSoWUlBSkp6crHcXkpKen\nY+XKlfx+m4gMwpum6DfV19fD3d0dBQUF8Pb2VjqOSWj72VRZWRl69eqldBwiMiOccOk32dnZYfHi\nxcjIyFA6isnIyMjAwoULWbZEZDBOuPRI3Lrwb7j1JRF1BidceiQXFxfExcUhKytL6SiK27p1K6ZM\nmcKyJaIO4YRL7bp48SImTJgAjUYDW1tbpeMoorm5GR4eHjh69Cj8/f2VjkNEZogTLrVr2LBhCAgI\nwO7du5WOopi9e/fCz8+PZUtEHcbCJb2kpqZCrVZb5EYYQoiHG10QEXUUC5f0EhUVBZVKhby8PKWj\nyC4/Px9arRaTJk1SOgoRmTEWLunFysrq4XaPlmbDhg1ISUnhNo5E1Cm8aYr01nbj0JEjRxAQEKB0\nHFlcuHABzzzzDMrKytCjRw+l4xCRGeOES3qzsbHB8uXLoVarlY4iG7VajaVLl7JsiajTOOGSQSxp\n8wdu+kFEUuKESwZxcHBAQkICMjMzlY5idJs2bcKsWbNYtkQkCU64ZLC2Dfw1Gg169+6tdByjqKur\ng7u7O06cOAEvLy+l4xBRF8AJlwzm4eGByMhI5OTkKB3FaLZv347w8HCWLRFJhhMudUhhYSHi4+NR\nWlra5Z4Lq9Vq4ePjg9zcXISFhSkdh4i6CE641CGhoaFwdXXFgQMHlI4iuUOHDsHR0RFjxoxROgoR\ndSEsXOqwto0wutqHJG3bOHKjCyKSEguXOiw2Nha3b99GQUGB0lEkc/LkSVRWVmLatGlKRyGiLoaF\nSx2mUqmwcuVKpKenKx1FMunp6XjppZe63PfSRKQ83jRFndL285njx4/D29tb6TidYgk/dyIi5XDC\npU6xt7dHUlISMjIylI7SaRkZGVi4cCHLloiMghMudVpX2ALRkrasJCJlcMKlTnNxcUFcXByysrKU\njtJhW7duxZQpU1i2RGQ0nHBJEm2PsdNoNLC1tVU6jkHaHjt49OhR+Pv7Kx2HiLooTrgkieHDhyMg\nIAC7d+9WOorB9u7dCz8/P5YtERkVC5ckk5qaCrVabVYbYQghHm50QURkTCxckkxUVBRUKhXy8vKU\njqK3/Px8aLVaTJo0SekoRNTFsXBJMlZWVg+3ezQXGzZsQEpKCrdxJCKj401TJKm2G5COHDmCgIAA\npeM8UtuNXmVlZejRo4fScYioi+OES5KysbHB8uXLoVarlY7SLrVajaVLl7JsiUgWnHBJcuawiURX\n2KyDiMwLJ1ySnIODAxISEpCZmal0lN+0adMmzJo1i2VLRLLhhEtGYcoPAmh74MKJEyfg5eWldBwi\nshCccMkoPDw8EBkZiZycHKWj/JPt27cjPDycZUtEsuKES0ZTWFiI+Ph4lJaWmszzZbVaLXx8fJCb\nm4uwsDCl4xCRBeGES0YTGhoKV1dXHDhwQOkoDx06dAiOjo4YM2aM0lGIyMKwcMmo2jbCMJUPUtq2\nceRGF0QkNxYuGVVsbCxu376NgoICpaPg5MmTqKysxLRp05SOQkQWiIVLRqVSqbBy5Uqkp6crHQXp\n6el46aWXTOb7ZCKyLLxpioyu7Wc4x48fh7e3tyIZTPlnSkRkGTjhktHZ29sjKSkJGRkZimXIyMjA\nwoULWbZEpBhOuCQLJbdSNIetJomo6+OES7JwcXFBXFwcsrKyZL/21q1bMWXKFJYtESmKEy7Jpu1x\neBqNBra2trJcs+1xgUePHoW/v78s1yQi+jWccEk2w4cPR0BAAHbv3i3bNffu3Qs/Pz+WLREpjoVL\nskpNTYVarZZlIwwhxMONLoiIlMbCJVlFRUVBpVIhLy/P6NfKz8+HVqvFpEmTjH4tIqL2sHBJVlZW\nVg+3ezS2DRs2ICUlhds4EpFJ4E1TJLu2G5mOHDmCgIAAo1yj7QatsrIy9OjRwyjXICIyBCdckp2N\njQ2WL18OtVpttGuo1WosXbqUZUtEJoMTLinCmJtRKLnJBhHRb+GES4pwcHBAQkICMjMzJV9706ZN\nmDVrFsuWiEwKJ1xSjDEeKND2oIQTJ07Ay8tLkjWJiKTACZcU4+HhgcjISOTk5Ei25vbt2xEeHs6y\nJSKTwwmXFFVYWIj4+HiUlpZ2+jm1Wq0WPj4+yM3NRVhYmEQJiYikwQmXFBUaGgpXV1ccOHCg02sd\nOnQIjo6OGDNmjATJiIikxcIlxbVthNHZD1vatnHkRhdEZIpYuKS42NhY3L59GwUFBR1e4+TJk6is\nrMS0adMkTEZEJB0WLilOpVJh5cqVSE9P7/Aa6enpeOmllzr9PTARkbHwpikyCW0/5zl+/Di8vb0N\nOtcYPy8iIpIaJ1wyCfb29khKSkJGRobB52ZkZGDhwoUsWyIyaZxwyWR0ZEtGY24RSUQkJRYumZQF\nCxbA09MTaWlpOH78OE6fPo3i4mLU1NRACIHHH38c/v7+CA4OxpgxY7Bx40Z899132LFjh9LRiYge\niYVLJuWzzz7DzJkzYWNjgyFDhiA0NBSBgYFwcnICAFRXV+Ps2bM4deoUvv/+e7S2tuKDDz7A5MmT\nFU5ORPRoLFwyCVqtFhkZGVi/fj1mz56NZcuWtXvz1NWrV7Fp0ybs3LkTr776KlJSUqBSqWRKTERk\nGBYuKe7OnTuIi4uDlZUVcnJyMGTIEIPO12g0WLBgAZqbm3Hw4EE4OjoaKSkRUcfxLmVS1O3btxER\nEYHQ0FB8+eWXBpct8MtDEPLz8zFu3DiMHz8e1dXVRkhKRNQ5nHBJMVqtFk8//TRGjx6N//zP/5Rk\nS8bXX38dX3/9NY4dO8aPl4nIpHDCJcX893//NwDgnXfekWz/43Xr1qFHjx5Qq9WSrEdEJBVOuKSI\n8vJyjBo1CoWFhR36GPlRysrKEBISglOnTsHDw0PStYmIOooTLikiKysL8+bNk7xsAcDd3R0LFizA\nli1bJF+biKijWLgku6amJuTk5GDJkiV6n3P06FGMHj0affr0gZeXF7799ttHHp+UlITt27ejoaGh\ns3GJiCTBwiXZnThxAh4eHhg6dKhex58+fRqLFy/GwoUL8dNPP+Gbb76Bp6fnI8/x9PSEr69vpx75\nR0QkJRYuya6oqAijR4/W+/iPPvoI8+bNw+LFi2Fra4sBAwZg4MCB7Z4XEhKCoqKizkQlIpIMC5dk\nV1xcjMDAQL2P/+STT9DU1ISAgAAEBwdj69ataG5ubve8wMBAnD17tjNRiYgkw6d1k+xqamoe7o3c\nntu3b+PixYsAgB07dqB79+6YN28e7O3tMXfu3Eee6+TkhJqamk7nJSKSAidcMmltz7h94YUXEBgY\niOHDhyMpKQl79uxROBkRkWFYuCQ7BwcHVFVV6XWsjY0NPDw80K3b3/5XFULotVFGVVUVHBwcOpyT\niEhKLFySXUBAgEHfrSYlJSEnJwfnz5/HpUuXsG3bNsybN6/d886ePWvQd8VERMbE73BJdkFBQfjw\nww/1Pv7ll1/GnTt3MHnyZAwYMACJiYmYNm1au+f99a9/xZo1azoTlYhIMtzakWTX1NQENzc3fPPN\nN3r/FtdQ165dQ2hoKMrLy9GzZ0+jXIOIyBD8SJlk16NHDyxYsADZ2dlGu8bWrVvxwgsvsGyJyGRw\nwiVFtD284OTJk/Dy8pJ0bY1Gg9GjR/PhBURkUjjhkiLc3NzwxhtvIDExETqdTrJ1dTodEhMT8cor\nr7BsiciksHBJMcuXLwcAvPrqq5Dqg5ZVq1ahqakJKSkpkqxHRCQV3qVMilGpVDhw4AAiIiIA/PIg\n+r//va0hdDod3njjDRw6dAhff/01VCqVhEmJiDqP3+GS4u7cuYO4uDhYWVkhJyfH4GfkXrt2DYmJ\niWhubsbBgwfh6OhopKRERB3Hj5RJcY8//ji+/PJLPPfccwgNDUVqaipKS0vbPe/q1at4+eWXMXr0\naEyePBnHjh1j2RKRyeKESybl+vXryMrKejjpjh49GqNGjYKjoyOsrKxQXV2NM2fO4NSpUygtLcX8\n+fPx4osv8gYpIjJ5LFwySY2NjTh+/DiKiopQXFyMmpoaCCHg4OCAgIAABAUFYcyYMfydLRGZDRYu\nERGRDPgdLhERkQxYuERERDJg4RIREcmAhUtERCQDFi4REZEMWLhEREQyYOESERHJgIVLREQkAxYu\nERGRDFi4REREMmDhEhERyYCFS0REJAMWLhERkQxYuERERDJg4RIREcmAhUtERCQDFi4REZEMWLhE\nREQyYOESERHJgIVLREQkAxYuERGRDFi4REREMmDhEhERyYCFS0REJAMWLhERkQxYuERERDJg4RIR\nEcmAhUtERCQDFi4REZEMWLhEREQyYOESERHJgIVLREQkAxYuERGRDFi4REREMmDhEhERyeB/AdsO\nUlB+yPlAAAAAAElFTkSuQmCC\n",
       "text": [
        "<matplotlib.figure.Figure at 0x10e673bd0>"
       ]
      }
     ],
     "prompt_number": 47
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Now 6 is the representative of the merged group.  With a bad choice of `union` operations, this procedure can give you trees of depth $O(n)$, which as both `union` and `find` run in time based on the maximum depth of the trees, is bad.  To fix this, there are usually two supplemental tricks used:  first, when merging two sets, keep track of the depth of each tree and make sure we make the deeper tree the represenative of the merged set.  Second, we can do path compression during `find` operations - every time we run a `find` we update $S$ to point directly to its representative rather than going through any intermediates."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "##### Takeaway\n",
      "\n",
      "* Supports *constant* time ($O(1)$) testing of set composition\n",
      "* No good way to split sets - think if that's something you'll need to do\n",
      "* Simple implementation, no standard library support, so think about writing your own ahead of time\n",
      "* If you do, use some tricks (path compression and height-dependent root merging) to ensure good performance\n",
      "* Use when you need to quickly answer whether two items are in the same set, or ask what set a particular item is in"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "#### Segment Trees"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Segment trees are optimized for doing calculations on intervals.  For this one, the implementation is actually going to be important as there aren't great libraries out there, so I'm going to start with that.\n",
      "\n",
      "Suppose we have an array $A$ with $n$ elements that we know is going to be dynamically changing through the course of our problem.  We're going to want to repeatedly query the array to know what is the minimum value over some interval $[i,j]$.  The brute force way to solve this problem is to simply iterate over each element of the array from $i$ to $j$ and find the minimum in that interval.  Unfortunately, this solution is often too slow - it takes $O(n)$ time for each query.  What kind of data structure can let us answer this query more efficiently?  \n",
      "\n",
      "A segment tree holds a subset of the intervals on $A$ so that every possible interval we might query is representable as the union of a small number of intervals present in the tree.  We'll build it as a complete binary tree where the root of the tree is $[0,L]$ - the interval covering the whole range of $A$.  Then the children of each node will split the interval of their parent into two disjoint equal-sized pieces.  So if our root node is $[0,6]$, it will have children $[0,3]$ and $[4,6]$.  We then keep splitting the intervals until the leaves of the tree are intervals that contain only a single element. Then we calculate minimum of our array over each interval in the tree.  The leaves of the tree are trivial - the minimum is simply the value of the element at each position.  The minimum at larger intervals are then calculated by taking the minimum of the value at each of its children.\n",
      "\n",
      "Once we've built this structure in $O(n log n)$ time, we can now do two operations very quickly: update the values in $A$ and find the minimum over an arbitrary interval.  Updates are done by changing the value of the leaf associated with the element being updated and then cascading upward as we did originally.  Interval queries are done by interval splitting.  Let's look at an example."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "A = [18, 17, 21, 19, 15, 11, 20]\n",
      "idx = [0, 1, 2, 3, 4, 5, 6]\n",
      "\n",
      "#This is just visualization code!  Don't try to take this as actually building a segment tree!\n",
      "def build_segment_tree(i, j, G):\n",
      "    G.add_node((i,j))\n",
      "    if i == j:\n",
      "        return\n",
      "    mid = (i + j) // 2\n",
      "    build_segment_tree(i, mid, G)\n",
      "    build_segment_tree(mid+1, j, G)\n",
      "    G.add_edge((i,j), (i,mid))\n",
      "    G.add_edge((i,j), (mid+1,j))\n",
      "\n",
      "G = nx.DiGraph()\n",
      "build_segment_tree(idx[0], idx[-1], G)\n",
      "#TODO - fix layout so L/R paths work correctly\n",
      "labels = dict((u, \"[%i, %i]\\n%i\" % (u[0], u[1], min(A[u[0]:u[1]+1]))) for u in G.nodes())\n",
      "print A\n",
      "nx.draw_graphviz(G, prog='dot', labels=labels, node_color='white', node_size=1200, arrows=False, node_shape='s')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[18, 17, 21, 19, 15, 11, 20]\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAd4AAAFBCAYAAADZrs5VAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XlYVPX+B/D3DIggw64ILihoqCQohjx1FYRMUFwprmUQ\nqSiaGt7bzZTHUMubS4v3ZkrhdYMw7KZ5c4HAMhbpp2YuuIC4IKKZKYMKJttwfn/0c34uF5yBmXMO\nw/v1PPOkM57v+Xw6A+85Z845X4UgCAKIiIhIFEqpCyAiImpLGLxEREQiYvASERGJiMFLREQkIgYv\nERGRiBi8REREImLwEhERiYjBS0REJCIGLxERkYgYvERERCJi8BIREYmIwUtERCQiBi8REZGIGLxE\nREQiYvASERGJiMFLREQkIgYvERGRiBi8REREImLwEhERiYjBS0REJCIGLxERkYgYvERERCJi8BIR\nEYmIwUtERCQiBi8REZGIGLxEREQiYvASERGJiMFLREQkIgYvERGRiBi8REREImLwEhERiYjBS0RE\nJCIGLxERkYgYvERERCJi8BIREYmIwUtERCQiBi8REZGIGLxEREQiYvASERGJiMFLREQkIgYvERGR\niBi8REREImLwEhERiYjBS0REJCIGLxERkYgYvERERCJi8BIREYmIwUtERCQiBi+RCXF0dIRCoZDF\nw9HRUer/HUSypBAEQZC6CCIyDIVCAbn8SMupFiI54R4vERGRiBi8REREImLwEpkopVIJlUqFhIQE\no6+ruLgYKpUK5ubm2LBhg9HXR9SaMXiJTFhBQQGWLl2q/fvZs2cRGBgIBwcHDBs2DOfOndNrvPT0\ndPj7+8POzg69e/fG/v37AQCenp6oqqpCQEAAFAqFQXsgMjUMXqI2QhAEhIWFwcvLCydPnkS/fv0Q\nFham8wlQhw8fRmxsLKZNm4Zr164hLy8PHh4eRq6ayPSYS10AEYkjJycHZWVlSExMhFKpRGJiIlQq\nFbKzsxEcHPzY5b/++mtER0cjNjYWAODq6mrskolMEvd4idqIM2fOwMvLC0rlHz/2SqUSXl5eKCoq\n0mn5Xbt2oaamBgMHDoSfnx+SkpJQW1trzJKJTBL3eInaiPLycvTs2fOB5zw8PKBWq3Va9tSpUwCA\nlJQUtGvXDtHR0bC2tkZUVJQxyiUyWdzjJWojnJycUFJS8sBz58+fh5OT02OXtbGxAQBMnjwZvr6+\n6N+/P2bMmIG0tDSj1Epkyhi8RG1Enz59UFhYCI1GAwDQaDQoLCxE3759H7ushYUF3N3dtYepgT9O\n1uIZzET6Y/AStRFBQUFwc3PDnDlzUFZWhtmzZ6Nbt24ICgoCAGRnZz8QrA+bMWMGNm7ciIKCAhQW\nFmL9+vWIjo4WqXoi08HveIlM2MOXCqWnpyMmJgbe3t4YMGAAMjIytK+VlZVhyJAhjY41b948qNVq\nhIWFwdXVFTExMQgPD29yfUT0KE6SQGRC7p+YwMrKCu3bt8fcuXPxzjvvPHbZ6dOnY+LEiRgxYoTe\n6z179iwGDx6M+vp6JCYmIjo6mpMkEDWCwUtkQuQUdnKqhUhO+B0vERGRiBi8REREImLwEhERiYjB\nS0REJCIGL1EbtWbNGvj5+cHS0hJTpkzRPl9XV4eIiAjtDTNycnIkrJLI9DB4idqorl27IiEhAVOn\nTn3ktcDAQKSmpsLFxYV3pyIyMN5Ag6iNunfzi8OHD+Py5cva59u1a4e4uDgAgJmZmSS1EZky7vES\ntXG81pZIXAxeojaOh5KJxMXgJWrjuMdLJC4GL1Ebxz1eInExeInaKI1Gg+rqatTX10Oj0aCmpkY7\nV29NTQ2qq6sf+TMRtRwnSSAyIfpMTLBkyRK8++67jzy3aNEi9OzZE5cuXdKOp1AoUFJSAjc3N6PU\nQtSWMHiJTIicwk5OtRDJCQ81ExERiYjBS0REJCIGLxERkYgYvERERCLivZqJTIiDg4Nsrst1cHCQ\nugQiWeIeL5EJUavVEASh0cfKlSsRGRnZ5L953GPfvn3w9PREfX19k/9OrVZL/b+DSJYYvERtRE1N\nDT7++GPMmzevReMEBQXBwcEBO3bsMFBlRG0Lg5eojdiyZQu8vb0xYMCAFo2jUCgQHx+PZcuW8Tpd\nomZg8BK1AQ0NDfjggw8wf/58g4w3duxY1NbWIisryyDjEbUlDF6iNmDXrl1QqVQICgoyyHhKpRIL\nFizA8uXLDTIeUVvC4CVqA95//3289dZbBj3j+aWXXkJpaSl+/PFHg41J1BYweIlMXH5+Pq5du4bn\nn3/eoOOam5vjrbfe4l4vkZ44SQKRiRs/fjxGjRqFmTNnGnzs6upquLu7IzMzEz4+PgYfn8gUMXiJ\nTFhhYSGCg4NRUlICKysro6xj5cqVOH78OL744gujjE9kahi8RCZs6tSp8PDwwNtvv220ddy+fRse\nHh44ePAgevXqZbT1EJkKBi+Ribpy5Qq8vb1x7tw5ODo6GnVdb7/9Nm7cuIHPPvvMqOshMgUMXiIT\n9dZbb6G2thb//Oc/jb6u69evw9PTE6dOnUKXLl2Mvj6i1ozBS2SCbt26BQ8PDxw9ehRubm6irHPu\n3LmwsLDABx98IMr6iForBi+RCVq5ciVOnjyJzz//XLR1Xrp0CQMHDhTl0DZRa8bgJTIxNTU1cHd3\nx7fffiv6JT5TpkyBu7s7Fi1aJOp6iVoTBi+RidmwYQO2bduGjIwM0dddVFSEwMBAlJSUwNraWvT1\nE7UGvHMVkQkx9GQI+urbty8CAwPxr3/9S5L1E7UGDF4iE7Jr1y7Y2tpi2LBhktUQHx+PDz/8EDU1\nNZLVQCRnDF4iEyEIAlauXGnwyRD09dRTT+HJJ59EamqqZDUQyRmDl8hE5Ofn47fffkN4eLjUpSA+\nPh4rV66ERqORuhQi2WHwEpmI999/H2+++SbMzMykLgXDhg2Dk5MTtm/fLnUpRLLDs5qJTMDp06fx\n7LPPGnUyBH3t2rULixYtwpEjRyQ99E0kN9zjJTIBH374IV5//XXZhC4AjB49GvX19cjMzJS6FCJZ\n4R4vUSt3+fJl+Pj4yPKOUVu2bEFSUhJyc3OlLoVINhi8REbm6OiIiooKqcsAADg4OECtVhtsPFPu\njchYGLxERqZQKCCXHzND12LKvREZC7/jJSIiEhGDl4iISEQMXiIRKZVKqFQqJCQkGH1dxcXFUKlU\nMDc3x4YNG4y+PlPujciQGLxEIisoKMDSpUu1fz979iwCAwPh4OCAYcOG4dy5czqPFRUVBVdXVzg4\nOCA4OBhJSUna1zw9PVFVVYWAgADRrqN9uLd7UlJSoFQq9Q7J9PR0+Pv7w87ODr1798b+/fsBSNMb\nkaEweIkkJAgCwsLC4OXlhZMnT6Jfv34ICwvT+SSh+Ph4lJSUQK1WY8WKFZg/fz5OnTpl5Kr1U1FR\ngWXLlqF///56heThw4cRGxuLadOm4dq1a8jLy4OHh4cRKyUSB4OXSEI5OTkoKytDYmIiunbtisTE\nRFy+fBnZ2dk6Lf/kk0/C0tISDQ0NUCgUMDc3h6WlpXGL1lN8fDzmzp0LJycnvZb7+uuvER0djdjY\nWFhaWsLV1RVdunQxUpVE4mHwEknozJkz8PLyglL5x4+iUqmEl5cXioqKdB5j1qxZUKlUGDp0KNLS\n0tCrVy9jlau3Q4cO4ciRI5g5c6bey+7atQs1NTUYOHAg/Pz8kJSUhNraWiNUSSQuc6kLIGrLysvL\n0bNnzwee8/Dw0OtGEImJifjoo4/wn//8BxMnTkR+fj68vLwMXKn+NBoNZs+ejbVr1+r9PWx5ebn2\nkHlKSgratWuH6OhoWFtbIyoqyhjlEomGe7xEEnJyckJJSckDz50/f17vw7JWVlaYNGkSgoODZTMj\nUGJiInx8fODv7699Ttfvrm1sbAAAkydPhq+vL/r3748ZM2YgLS3NKLUSiYl7vEQS6tOnDwoLC6HR\naGBmZgaNRoPCwkL07du3WePduXMHrq6uBq6yefbt24ecnBykp6cDANRqNY4ePYrjx49j9erVTS5r\nYWEBd3d37SF44I/Q5hnMZAq4x0skoaCgILi5uWHOnDkoKyvD7Nmz0a1bNwQFBQEAsrOzHwif+12/\nfh1bt25FVVUVKioqkJycjIMHD2LSpEkidtC4zZs3o6ioCMePH8exY8fg5+eHJUuW4L333gPQdG8A\nMGPGDGzcuBEFBQUoLCzE+vXrER0dLVb5REbDPV4ikT18uDU9PR0xMTHw9vbGgAEDkJGRoX2trKwM\nQ4YM+a/jKBQKfPbZZ3jttddgY2ODMWPGYPfu3bC2tm5yfcZ0/7rs7OweeM3CwgK2trbaw8hN9QYA\n8+bNg1qtRlhYGFxdXRETE4Pw8PBG10fUaghEZFT3/5hZWloKdnZ2wqJFi3Radtq0aUJWVlaz1ltc\nXCzY2dkJ1tbWQnJy8iO1GIIp90ZkLJydiMjI5DRrDmcnIpIev+MlIiISEYOXiIhIRAxeIiIiETF4\niYiIRMTgJZKRNWvWwM/PD5aWlpgyZYr2+S1btsDGxkb7sLa2hlKpxNGjRyWsVj+N9VZXV4eIiAjt\nDTNycnIkrJLI+Bi8RDLStWtXJCQkYOrUqQ88HxkZicrKSu0jMTERvXr1gq+vr0SV6q+x3gAgMDAQ\nqampcHFx4d2pyOTxBhpEMnLvBhGHDx/G5cuXG/13mzdvbnV3cWqst3bt2iEuLg4AYGZmJkltRGLi\nHi+RDDV1PWppaSny8vJaXfDew2ttqa1j8BLJUFOHW1NSUhAYGIgePXqIWJHh8FAytXUMXiIZamqv\nMCUlBa+++qqI1RgW93iprWPwEslQY3uF+fn5uHr1KiIiIkSuyHC4x0ttHYOXSEY0Gg2qq6tRX18P\njUaDmpoaaDQa7evJycmIiIh4ZAai1qCp3mpqalBdXf3In4lMklSzMxC1Ffr8mC1evFhQKBQPPN55\n5x1BEATh7t27gr29vbBv3z5RajH0eE311qNHD0GhUAhKpVL739LSUqPVQiQlzk5EZGRymjWHsxMR\nSY+HmomIiETE4CUiIhIRg5eIiEhEDF4iIiIRMXiJiIhExEkSiIxo1apVsLCwkM1NIxwcHAw+nlx6\ns7GxkboEIp1wj5fISDZs2IDVq1fj3LlzEAShRQ8ALR5DEASo1WqD9qhWqw1SV0v7KygogJWVFdLT\n0w3aH5Ex8DpeIiPYtm0b4uLikJ2dDU9PzxaPZ+rXqBqivwMHDmDcuHHYtm0bAgMDDVQZkeExeIkM\nLDMzE6+88gqysrIwcOBAg4zJ4NXN999/j0mTJiEjIwNPPfWUASojMjweaiYyoPz8fERFRWHHjh0G\nC13S3fDhw5GUlIQxY8agsLBQ6nKI/iueXEVkIMeOHUN4eDhSU1MxZMgQqctps8LDw1FZWYnQ0FDk\n5uaiZ8+eUpdE9AAGL5EBFBcXIywsDImJiQgNDZW6nDYvOjoaN2/exIgRI5CXlwcXFxepSyLSYvAS\ntdClS5cQEhKCv//97616nlxTExcXh5s3byIkJAQ5OTkGv5SKqLl4chVRC/z2228ICAjAzJkz8de/\n/tVo6+HJVc0jCAL+9re/4cCBA8jKyoJKpTL4Ooj0xeAlaqabN28iODgYY8eOxbvvvmvUdTF4m08Q\nBEybNg1lZWXYtWsX2rdvb5T1EOmKwUvUDL///jtCQ0Ph6+uLjz/+2Oh3b2LwtoxGo8GLL74IQRDw\n5Zdfwtyc37KRdBi8RHqqra3F+PHj4ezsjE2bNkGpNP5VeQzelqupqcG4cePQpUsXbNiwQZTtRvTf\nMHiJ9KDRaDBp0iTU1dXhq6++Em3PicFrGHfu3EFISAgGDx6Mf/zjH7K5zzS1LfzIR6QjQRAwY8YM\nlJeXIy0tjYcrWyFra2vs2bMH2dnZRv9enqgx/M1BpANBEDBv3jycPHkSe/fuhaWlpdQlUTPZ29sj\nMzMTAQEBsLe3x9y5c6UuidoYBi+RDpYtW4bMzEzk5ORw+jkT0LlzZ+zduxcBAQGws7PD5MmTpS6J\n2hAGL9FjrF27Fps2bUJeXh4cHR2lLocMpEePHsjKykJwcDBsbW3x/PPPS10StREMXqImpKamYsWK\nFcjNzYWrq6vU5ZCB9e3bF+np6QgNDYWNjQ1GjBghdUnUBvCsZqJG7Ny5E7Gxsdi3bx+8vLwkrYVn\nNRtXXl4enn/+eezcuRPPPPOMZHVQ28Czmon+ix9++AHTpk3D7t27JQ9dMr6AgACkpKRgwoQJKCgo\nkLocMnEMXqKHHDp0CC+++CL+/e9/w8/PT+pySCSjRo3CJ598glGjRuHs2bNSl0MmjN/xEt3n5MmT\nGDduHDZu3IigoCCpyyGRTZw4Ebdu3cKIESOwf/9+dOvWTeqSyAQxeIn+z4ULFzBy5EisWrUKY8aM\nkbocksj06dO14Zubm4tOnTpJXRKZGJ5cRQTgl19+QUBAAN5880289tprUpfzCKlPPjI2Ofa3cOFC\nfPvtt9i3bx/s7OykLodMCIOXJOfo6IiKigqpywAAODg4QK1WG3RMU+7PlHsTBAEqlQq///67wcZs\nLmO8L0k6DF6SnJz2doxRiyn3Z8q9GWvM1lwHGQbPaiYiIhIRg5eIiEhEDF6SFaVSCZVKhYSEBKOv\nq7i4GCqVCubm5tiwYYPR1weYdn/szTCkeF+SuBi8JDsFBQVYunSp9u9nz55FYGAgHBwcMGzYMJw7\nd07nsdasWQM/Pz9YWlpiypQpD7zm6emJqqoqBAQEiDoh+v39FRcXY/z48XB2doaHhwfeeOMNlJaW\n6jxWVFQUXF1d4eDggODgYCQlJWlfk6K/h7cdALz//vvw8vKCra0tBg0ahFu3buk8Xnp6Ovz9/WFn\nZ4fevXtj//79AOTTGwCkpKRAqVTqFZJBQUGwsrKCjY0NbGxs0K9fP+1rUr0vSTwMXpI1QRAQFhYG\nLy8vnDx5Ev369UNYWJjOJ5p07doVCQkJmDp1qpErbZ5bt25hwoQJKC4uxk8//YS7d+9i/vz5Oi8f\nHx+PkpISqNVqrFixAvPnz8epU6eMWLF+Vq1aha+++goffvghbt26hdTUVJ3nMj58+DBiY2Mxbdo0\nXLt2DXl5efDw8DByxfqpqKjAsmXL0L9/f71CUqFQYO3ataisrERlZSUKCwuNWCXJDW+gQbKWk5OD\nsrIyJCYmQqlUIjExESqVCtnZ2QgODn7s8uHh4QD++CV++fJlY5ert8GDB2Pw4MHavy9cuBDu7u64\nc+cOrK2tH7v8k08+CQDQaDRQKBQwNzfXOdjEsH37drz33nsICQkBAL3ue/31118jOjoasbGxACDL\n2aHi4+Mxd+5c/Pvf/9Z7WZ6l3HZxj5dk7cyZM/Dy8oJS+cdbValUwsvLC0VFRXqN01p+yR04cAAu\nLi46he49s2bNgkqlwtChQ5GWloZevXoZsULdXb9+HUeOHEF+fj48PDwwZswY7NmzR+fld+3ahZqa\nGgwcOBB+fn5ISkpCbW2tESvWz6FDh3DkyBHMnDmzWcvHx8eje/fuiIuLw/Hjxw1cHckZg5dkrby8\nHD179nzgOQ8PD71vJtAaviu7fPkyXn/9daxevVqv5RITE6FWq5GcnIyJEyfi9OnTRqpQP7m5uaip\nqcHp06eRl5eHOXPmIDIyEmVlZY9dtry8HKdOnUJWVhY2bdqEzZs3IykpqVl7lsag0Wgwe/ZsrFmz\nplnvrZUrV6KkpAQ///wzunTpglGjRkGj0RihUpIjBi/JmpOTE0pKSh547vz583ByctJrHLnv8V6/\nfh3PPfcc5s6dqz08rg8rKytMmjQJwcHB2L59uxEq1J+NjQ0AYMGCBejatStGjhyJUaNGYevWrTov\nO3nyZPj6+qJ///6YMWMG0tLSjFqzrhITE+Hj4wN/f3/tc/q8x/z9/WFtbQ1nZ2csWLAAHTt2xO7d\nu41RKskQv+MlWevTpw8KCwuh0WhgZmYGjUaDwsJC9O3bV69x5LzHW1FRgZCQEISHh2PBggUtGuvO\nnTuy+S60T58+UCgU2q8JgD/CSZdtYWFhAXd392YtK4Z9+/YhJycH6enpAAC1Wo2jR4/i+PHjeh+x\nAHhnqraGe7wka0FBQXBzc8OcOXNQVlaG2bNno1u3btop+7Kzsx/45fwwjUaD6upq1NfXQ6PRoKam\nRlaH9G7fvo3Q0FAMHToUy5cvf+T1pvq7fv06tm7diqqqKlRUVCA5ORkHDx7EpEmTjF22Tnr06IHQ\n0FCsWLECv/76K7777jtkZWUhKioKwOO33YwZM7Bx40YUFBSgsLAQ69evR3R0tFjlN2nz5s0oKirC\n8ePHcezYMfj5+WHJkiV47733ADTd261bt5CZmYnq6mrcuHEDH374IW7cuIFx48aJ2QJJiMFLsvPw\nJ//09HScPn0a3t7eKCwsREZGhva1srIyDBkypNGxli5dig4dOmDlypVITU2FlZWV9pdjY+sztvvX\nt2PHDhw+fBibNm3SXtNpa2urPQO7qf4UCgU+++wzdO/eHQMGDMDBgwexe/fuR07MErO/h9e1ZcsW\n1NfXw9vbGx9//DE+//xzuLi4AHj8tps3bx5Gjx6NsLAwREdHIyYm5pHD8FL1ZmdnB2dnZzg7O6Nz\n586wsLCAra2t9hB5U73V1dUhISEBzs7O8PPzw6VLl/DNN988EtTcAzZhApHE7n8bWlpaCnZ2dsKi\nRYt0WnbatGlCVlZWs9ZbXFws2NnZCdbW1kJycvIjtRiKKfdnyr3dP6Yp9kbS4exEJDk5fb9lyjPc\nAJydSA5jtuY6yDB4qJmIiEhEDF4iIiIRMXiJiIhExOAlIiISEYOXWpXGpvnbsmWL9nIcGxsbWFtb\nQ6lU4ujRoxJWq7+mpjHMyMjQTiH4wgsvoKKiQqIqm6e2thYxMTHo2bMnOnXqhFdeeQX5+fna1w8e\nPAg/Pz84OjpizJgxuH79uoTV6q+xbVdXV4eIiAjtDUFycnIkrJLkgMFLrUpj0/xFRkZqp1irrKxE\nYmIievXqBV9fX4kqbZ7G+rt69SoiIyMRFxeHEydOwMLCQnsjitaivr4ebm5uyM3NxZUrVxAUFISX\nXnoJGo0GVVVVGDlyJMLCwnDs2DG0b98eL730ktQl66WpKSgDAwORmpoKFxcX2dx9i6TDW0ZSq6Lr\nNH+bN2+WzV2O9NFYf2lpaQgJCcHw4cMB/DGzja+vLy5fvoxu3bpJUqu+OnTogMWLF2v/HhMTgxUr\nVmDv3r349ddf4eTkhHfffRfAH3uPXbt2RUlJCdzd3aUqWS+Nbbt27dohLi4OAGBmZiZJbSQv3OOl\nVqmpaxpLS0uRl5fXKoP3nof7EwQBDQ0N2r/X19dDEAScOXNG7NIM5sqVK7hy5Qp69eqFM2fOwMfH\nR/uaq6srHB0dW2V/vN6WHofBS61SU4frUlJSEBgYiB49eohYkWE93N+LL76IrKwsZGZm4sqVK1ix\nYgUAoLKyUoryWqy2thaRkZGYPn06nnjiiUanfywvL5emwBbgoWR6HAYvtUpN7VWkpKTg1VdfFbEa\nw3u4v27duuHzzz/H6tWrMXToUHh6eqJ9+/YICAiQqMLma2hoQFRUFGxsbLBq1SoAQMeOHR+Z/vHC\nhQt6T/8oB9zjpcdh8FKr1NheRX5+Pq5evYqIiAiRKzKs/9bf2LFjsWfPHpSUlODpp5/GoEGDWl0w\nCYKAmJgY3LhxA9u2bdN+59mnTx+cOHFC++9++eUXqNVq9OnTR6pSm417vPQ4DF5qVR43zV9ycjIi\nIiIemaGntWisv5qaGpw8eRIajQZ79uzBkiVLWuWHi1mzZqGoqAi7du1C+/bttc+/8MILUKvVeOed\nd1BaWoo5c+bg2WefbTUnVgFNvzdrampQXV39yJ+pjRJ5UgaiR+jzNly8eLGgUCgeeLzzzjuCIAjC\n3bt3BXt7e2Hfvn2i1GKMMRvr7+bNm4KPj49gbW0teHp6CsuXLzd6LYYe7+LFi4JCoRCsrKwElUql\nfXzxxReCIAjCgQMHhKeeekqwt7cXRo8eLVy/ft1otRhjzKbemz169BAUCoWgVCq1/y0tLTVKHSR/\nnJ2IJCenmVdMeYYbgLMTyWHM1lwHGQYPNRMREYmIwUtERCQiBi8REZGIGLxEREQiYvASERGJiJMk\nkKQaGhpgZWUlm5sOODg4GGVMU+3PlHu7N6Yc+uvQoQMEQZBFLdRy3OMlyQiCgDlz5sDf3x+///47\nBEFo0ePemC15qNVqg/epVqsl7+3u3bsICgrCxIkTDXpZiiF6M9TDVLddeXk5PDw8sHz5coP3R9Jg\n8JJkFi5ciEOHDmHnzp2wsrKSuhyTZmlpiZ07d+LIkSOIj4+XuhzSg6OjI7KysrBhwwasXbtW6nLI\nAHiomSTx/vvv4z//+Q9yc3Nha2srdTltgo2NDTIyMhAYGAh7e3ssWLBA6pJIR66urvjuu+8QGBgI\nOzs7REVFSV0StQCDl0S3bt06fPrpp9i/fz86duwodTltipOTE7KyshAQEAB7e3vMnDlT6pJIR+7u\n7vj2228xfPhw2NraYty4cVKXRM3EW0aSqLZu3Yq//e1vyMnJQe/evQ06tinfVs/QvZ0/fx7Dhg3D\nBx98gEmTJhlsXHqUobfdTz/9hNGjR+PLL79EcHCwwcYl8TB4STTp6emYMmUKvvvuO3h7ext8fAav\nfk6ePInnnnsO69evx5gxYww6Nv0/Y2y77OxsTJw4Ebt374a/v79Bxybj48lVJIrc3FxMnjwZ33zz\njVFCl/TXv39/7Ny5E1OnTkVOTo7U5ZAegoKCsGHDBowbNw6nTp2SuhzSE4OXjO7nn39GREQE0tLS\n8PTTT0tdDt3H398fW7duxZ///GccPnxY6nJID2PHjsWqVasQGhqKCxcuSF0O6YHBS0ZVVFSEMWPG\nICkpCcOHD5e6HPovnn32WfzrX//CmDFjcPr0aanLIT28/PLLWLhwIUaMGIFffvlF6nJIRzyrmYzm\n4sWLCAkJwcqVKxEeHi51OdSE8ePHo7KyEqGhocjNzYW7u7vUJZGOXnvtNdy8eRMhISHIycmBk5OT\n1CXRYzCTLcNBAAASz0lEQVR4ySh+/fVXjBgxAm+++Saio6OlLod0EBUVhZs3b2LEiBHIy8uDq6ur\n1CWRjhYsWICKigqEhYXhu+++g42NjdQlURN4VjMZXEVFBYYNG4aIiAgsWrRItPXyrGbD+Pvf/44v\nv/wSOTk5cHR0FGWdpkysbScIAmbMmIFz584hPT0dlpaWRl8nNQ+DlwyqqqoKISEhePrpp/HRRx+J\nelN3Bq9hCIKAefPmYf/+/fjuu++gUqlEWa+pEnPbaTQaREZG4u7du9i2bRvatWsnynpJPwxeMpia\nmhqMHTsW3bp1w4YNG0SfSYXBaziCIGD69Om4ePEidu/ezb2nFhB729XW1mLChAlwcnJCcnIylEqe\nQys3DF4yiPr6erz44otQKBTYunUrzM3FP32AwWtYGo0GkyZNQl1dHb766itJtqkpkGLb/f777xg5\nciR8fHzwySefcDpBmeFHIWqxhoYGTJ8+HVVVVdiyZQt/QZsIMzMzpKamorq6GjExMWhoaJC6JNJR\nhw4dsGvXLvz444+inmdBumHwUosIgoA33ngDxcXF+Prrr9G+fXupSyIDsrCwwPbt23H+/Hn85S9/\nMdkjCqbIzs4OmZmZ2LZtGz766COpy6H7MHipRd59911kZ2djz549sLa2lrocMoIOHTpg9+7dyMvL\nw5IlS6Quh/TQqVMnZGVl4ZNPPsH69eulLof+D48JUrN9/PHH2LJlC/Ly8mBvby91OWRE9vb2yMzM\n1E4n+Ne//lXqkkhH3bt3x969exEUFAQ7Ozv8+c9/lrqkNo/BS82yefNmfPTRR8jLy0Pnzp2lLodE\n4OzsjL179yIgIAB2dnaYOnWq1CWRjp544gmkp6cjJCQENjY2GDlypNQltWk8q5n09vXXX2P27Nn4\n4Ycf0LdvX6nL0eJZzeIoLi5GUFAQVq9ejYiICKnLkT05bbsff/wR48ePx44dOzB06FCpy2mzGLyk\nl7179yIyMhLffvstBg0aJHU5D5DTLzhDk1tvR48eRWhoKD7//HOEhoZKXY6syW3b3fsZzszMhK+v\nr9TltEk8uYp09j//8z94+eWXsX37dtmFLonL19cXO3bsQFRUFH788UepyyE9jBgxAp9++inCwsJw\n5swZqctpkxi8pJOCggJMmDABKSkpCAgIkLockoEhQ4YgNTUV4eHhOH78uNTlkB5eeOEFLFu2DCEh\nIbh06ZLU5bQ5PNTcSjg6OqKiokLqMgAADg4OUKvVBhvPlHsDTLs/U+4NkE9/ptwbYJz+5IzB20rI\n6XsiQ9diyr0Za8zm4raTfky51CGX3gB51SIGHmomIiISEYO3FVIqlVCpVEhISDD6uoqLi6FSqWBu\nbo4NGzYYfX2m3Btg2v2xN8Pg+9L0MXhbqYKCAixdulT797NnzyIwMBAODg4YNmwYzp07p/NYd+7c\nQVRUFDp16gRvb2/s3r1b+5qnpyeqqqoQEBAg2gwnD/cWGxuLvn37wszMDMnJyXqNtWbNGvj5+cHS\n0hJTpkx54DUpegMe7K+8vBxDhgxBx44d0blzZ0yYMAHZ2dk6jxUVFQVXV1c4ODggODgYSUlJ2tek\n3nbFxcUYP348nJ2d4eHhgTfeeAOlpaU6jVNbW4uYmBj07NkTnTp1wiuvvIL8/Hzt61L3dr+UlBQo\nlcpmhcjZs2dhaWmJV155RfucHN6XwP+HsY2NDWxsbBAbG6vzWEFBQbCystIu269fP+1rUvUnJwxe\nEyAIAsLCwuDl5YWTJ0+iX79+CAsL0/k7k7i4OFy6dAn5+fmIjY3Fyy+/jJKSEiNXrbuBAwciMTER\ngwYN0vsHtWvXrkhISJDtXZZUKhU2btyI3377DaWlpRgzZgxeffVV1NbW6rR8fHw8SkpKoFarsWLF\nCsyfPx+nTp0yctW6uXXrFiZMmIDi4mL89NNPuHv3LubPn6/TsvX19XBzc0Nubi6uXLmCoKAgvPTS\nS6ivrzdy1fqpqKjAsmXL0L9//2aFyOzZs+Hv7y/bADpx4gQqKytRWVmJdevW6bycQqHA2rVrtcsW\nFhYascrWh8FrAnJyclBWVobExER07doViYmJuHz5sk57Tnfv3sXWrVuxfPlyeHp64vXXX8czzzyD\nzZs3G71uXc2aNQvPPvtssyZjDw8Px/jx4+Hk5GSEylquffv26NOnD5RKJRoaGmBmZoZ27drBwsJC\np+WffPJJWFpaoqGhAQqFAubm5rKZtH7w4MGYMmUK7O3t4eTkhIULF2L79u24c+fOY5ft0KEDFi9e\nDDc3N1hYWCAmJgaWlpb4/vvvRahcd/Hx8Zg7d26z3l9bt26Fg4MDhg8fLtsTi1oyFaRce5IDBq8J\nOHPmDLy8vKBU/rE5lUolvLy8UFRU9NhlL126hLt378Lb21v7nLe3t07LtiZy/yXg4+MDOzs7JCQk\nICcnR69lZ82aBZVKhaFDhyItLQ29evUyUpUtc+DAAbi4uDRrFqsrV67gypUr8PDwMEJlzXPo0CEc\nOXIEM2fO1HvZ27dvY/HixfjHP/4h6/dmYGAgnnzySbz33nu4evWqXsvGx8eje/fuiIuL43XeD2Hw\nmoDy8nL07Nnzgec8PDx0ui6uvLwc9vb2sLW11T7n7u6O8vJyQ5cpKbkeyrunoKAAZWVliI6OxrBh\nw/Ta00hMTIRarUZycjImTpyI06dPG7HS5rl8+TJef/11rF69Wu9la2trERkZienTp+OJJ54wQnX6\n02g0mD17NtasWdOs91ZCQgKmTZuGLl26yPa9mZubi9LSUmzbtg2nT59GXFyczsuuXLkSJSUl+Pnn\nn9GlSxeMGjUKGo3GiNW2LgxeE+Dk5PTId7Lnz5/X6fCXk5MTbt68idu3b2ufu3DhAjp27GjwOqUk\n572Ke1xcXPDuu++isrJS79swWllZYdKkSQgODsb27duNVGHzXL9+Hc899xzmzp2L8PBwvZZtaGhA\nVFQUbGxssGrVKiNVqL/ExET4+PjA399f+5yu77Fjx47h+++/x1/+8he9lhPb0KFDYW5ujn79+mHV\nqlXIyMjQ+QO5v78/rK2t4ezsjAULFqBjx44PnLTZ1nFaQBPQp08fFBYWQqPRwMzMDBqNBoWFhTrN\nHOTm5gYrKysUFBRoZys5ceIE/vSnPxm7bFHJda/iYXV1dairq4OLi0uzlr9z5w5cXV0NXFXzVVRU\nICQkBOHh4ViwYIFeywqCgJiYGNy4cQMZGRkwMzMzUpX627dvH3JycpCeng4AUKvVOHr0KI4fP/7Y\nvfqcnBxcvHgRbm5uAICqqirtz+zhw4eNXntLNPc737Z2g4zH4R6vCQgKCoKbmxvmzJmDsrIyzJ49\nG926dUNQUBAAIDs7W/v978Pu7Sm9/fbbOHv2LD755BMcOHAAkydPFq+Bx6irq0N1dTUaGhpQW1uL\n6upq7Q9xU70BfxwSrK6uRn19PTQaDWpqamR1yOvgwYPIz89HbW0tLl68iLfffhs+Pj7o3bs3gKb7\nu379OrZu3YqqqipUVFQgOTkZBw8exKRJk8RsoVG3b99GaGgohg4diuXLlz/y+uO23axZs1BUVIRd\nu3ahffv2xixVb5s3b0ZRURGOHz+OY8eOwc/PD0uWLMF7770HoOneYmNjceHCBe2yM2fOxOjRo5GZ\nmSlmC006ffo0jh07Bo1Gg+LiYrz55psICwtDp06dADTd361bt5CZmYnq6mrcuHEDH374IW7cuIFx\n48aJ2YKsMXhbqYc/Paanp+P06dPw9vZGYWEhMjIytK+VlZVhyJAhjY61evVqdOvWDc888wzWrVuH\ntLS0R74zFvPT6sPrGjFiBDp06IADBw4gNjYWHTp0QF5eHoDH97Z06VJ06NABK1euRGpqKqysrLS/\nHBtbn7Hdv76amhrMnj0bHTt2xNixY2FtbY2NGzdqX2+qP4VCgc8++wzdu3fHgAEDcPDgQezevfuR\nk5ek2nY7duzA4cOHsWnTJu31nLa2trh8+TKApnsrLS1FUlISjh8/DhcXF+3yaWlpja7P2O5fl52d\nHZydneHs7IzOnTvDwsICtra2sLGxAdB0b1ZWVg8sq1KpYGVl9chXQ1K+L69du4aXXnoJdnZ2mDhx\nIp544okHDvU31V9dXR0SEhLg7OwMPz8/XLp0Cd98880jQd2m94AFahXu31SWlpaCnZ2dsGjRIp2W\nnTZtmpCVldWs9RYXFwt2dnaCtbW1kJyc/EgthmDKvT08pqn1Z8q93T+mKfcmCKbZn5xxkoRWQk7f\nkfBG+9KP2VzcdtKPKZc65NIbIK9axMBDzURERCJi8BIREYmIwUtERCQiBi8REZGIGLwmqKmp8L7/\n/ns8//zzcHFxwQsvvIAffvhBoiqbp7HetmzZor3kxMbGBtbW1lAqlTh69KiE1eqvqW2XkZGhnWbv\nhRdeQEVFhURVNk9TU/3V1dUhIiIC7u7uUCqVet+vWg4a23YXL16EUql84P358CVtctdYb6aw3aTA\n4DVBjU2Fp9FoMHXqVIwZMwYlJSUYOXIkpk6d2qIZSMTWWG+RkZHaKcgqKyuRmJiIXr16wdfXV6JK\nm6ex/q5evYrIyEjExcXhxIkTsLCwQFRUlERVNs/jpvoLDAxEamoqXFxcWs2dxu73uCkob9++rX1/\nLly4UOTqWqap3lr7dpMCg9cENTYV3unTp1FeXo6pU6fCysoKU6dOxfXr11vVTES6TvO3efNmREdH\ni1SV4TTWX1paGkJCQjB8+HB07twZ8fHx+Pbbb7U3o2gNmprqr127doiLi8OQIUNkdWtIfTzuvdma\nPuA+rLHeTGG7SYHBa8Ievi6uf//+cHZ2xrp163D79m2sW7cOrq6u8PLykqjC5mvqmr/S0lLk5eW1\nyuC95+H+BEF44Bd3fX09BEHAmTNnxC7NYOQ41Z8hNPbe7NGjBwYPHox//vOfuHnzpshVGUZbutbW\nmBi8Juzhwz4KhQI7d+7EW2+9BQcHByxcuBA7d+6UqLqWaeqQVkpKCgIDA9GjRw8RKzKsh/t78cUX\nkZWVhczMTFy5cgUrVqwAAFRWVkpRXovJcao/Q3l423Xq1AmHDx/GpUuX8OmnnyIjI6PVfcd7Dw8l\nGwaD14Q9/On0woULCAgIwFdffYXKykp88cUX+NOf/oRLly5JVGHzNfXJOyUlBa+++qqI1Rjew/11\n69YNn3/+OVavXo2hQ4fC09MT7du3R0BAgEQVNp9cp/ozlIe3nbW1NQYNGgSlUgk/Pz8sX74cKSkp\nspqsQ1fc4zUMBq8Je/jT6d69e+Hr66uddGDkyJEYOHAgsrKyJKqw+Rr75J2fn4+rV68iIiJC5IoM\n67/1N3bsWOzZswclJSV4+umnMWjQIJ3mXJYT4b6p/rZt22aS3ws+bq9QEATto7XhHq9hMHhNUGNT\n4Y0ePRqHDh3Cvn37UF1djb179+Knn37C6NGjpS5ZZ4+b5i85ORkRERGPzNDTWjTWX01NDU6ePAmN\nRoM9e/ZgyZIlrfLDRVNT/dXU1KC6uvqRP7cW/23b1dfX49ChQzhz5gwaGhpw7NgxLFy4EJMnT4a5\neeuZDr2pn7vWvt0kIcZMDNRy+myqxYsXCwqF4oHHO++8IwiCIGzatEkIDQ0VOnbsKIwaNUpISUkx\nai2GHq+p3u7evSvY29sL+/btE6UWY4zZWH83b94UfHx8BGtra8HT01NYvny50Wsx9HgXL14UFAqF\nYGVlJahUKu3jiy++EARBEHr06CEoFApBqVRq/1taWmqUWowxZmPbLi0tTXB3dxesra2FZ555Rvjg\ngw+E8vJyo9VhjDGb+rlr6XbTtxZTwNmJWgk5zd7BGW6kH7O5uO2kH1MudcilN0BetYiBh5qJiIhE\nxOAlIiISEYOXiIhIRAxeIiIiETF4iYiIRNR6LiRr4xwcHGRz8bqDg4PBxzPV3u6Naar9mXJv98aU\nQ3+m3BtgnP7kjJcTERERiYiHmomIiETE4CUiIhIRg5eIiEhEDF4iIiIRMXiJiIhExOAlIiISEYOX\niIhIRAxeIiIiETF4iYiIRMTgJSIiEhGDl4iISEQMXiIiIhExeImIiETE4CUiIhIRg5eIiEhEDF4i\nIiIRMXiJiIhExOAlIiISEYOXiIhIRAxeIiIiETF4iYiIRMTgJSIiEhGDl4iISEQMXiIiIhExeImI\niETE4CUiIhIRg5eIiEhEDF4iIiIRMXiJiIhExOAlIiISEYOXiIhIRAxeIiIiETF4iYiIRMTgJSIi\nEhGDl4iISEQMXiIiIhExeImIiETE4CUiIhIRg5eIiEhEDF4iIiIRMXiJiIhExOAlIiISEYOXiIhI\nRAxeIiIiETF4iYiIRMTgJSIiEhGDl4iISEQMXiIiIhExeImIiETE4CUiIhIRg5eIiEhEDF4iIiIR\nMXiJiIhExOAlIiISEYOXiIhIRAxeIiIiETF4iYiIRMTgJSIiEtH/AsjAeLWy0fz/AAAAAElFTkSu\nQmCC\n",
       "text": [
        "<matplotlib.figure.Figure at 0x10dd38bd0>"
       ]
      }
     ],
     "prompt_number": 98
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Now suppose we want to do a query on this tree using the interval $[1,4]$ - that is, what's the minimum value in the array between those indexes, inclusive?  We start at the root of the tree, and at each node there are three possibilities:\n",
      "\n",
      "* The interval we're querying is identical to that of the node we're at, in which case we simply return the minimum associated with this node\n",
      "* The query interval is larger than the node we're at and the midpoint of the node's interval is within the query interval.  In this case, we split the query interval at this midpoint and recurse the resulting left and right query intervals down to the left and right children of this node, returning the minimum returned by both of these recursions.\n",
      "* The query interval is larger than the node we're at at the midpoint is outside the query interval.  In this case, we simply recurse the query interval down to the appropriate node.\n",
      "\n",
      "So for the query interval $[1,4]$, this gets split into the disjoint intervals $[1,1]$, $[2,3]$, and $[4,4]$ by recursing down the tree, with the minimum over the query returned as the minimum over these ending nodes.\n",
      "\n",
      "Anytime you see a problem where rapid calculation over intervals would be useful, think about whether a segment tree would solve the problem.  It's trivial to implement this using other queries - maximum over a range, sums over a range, products over a range - are all easily manageable."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "##### Takeaway\n",
      "\n",
      "* Efficient performance of range minimum query (RMQ) operations on dynamic arrays\n",
      "* Can be extended to other queries - maxima, sums, products over an interval range\n",
      "* Complex to implement - do so ahead of time and include extensive bug-testing!\n",
      "* Applicable to lots of different interval problems!"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Lab Work"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "* [TOJ 1067 - Disk Tree](http://acm.timus.ru/problem.aspx?space=1&num=1067) (an implementation problem)\n",
      "* [TOJ 1126 - Magnetic Storms](http://acm.timus.ru/problem.aspx?space=1&num=1126) (an algorithm problem)"
     ]
    }
   ],
   "metadata": {}
  }
 ]
}