Answer To: { "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "name":...
Swapnil answered on Dec 05 2021
Assign/.ipynb_checkpoints/Question File-checkpoint.ipynb{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "IIqniH2KkacL"
},
"source": [
"Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\\rightarrow$Run All).\n",
"\n",
"Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"id": "vZ2QllLpkacL"
},
"outputs": [],
"source": [
"NAME = \"Yuxuan Guo\"\n",
"COLLABORATORS = \"\""
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "JhnyL4GOkacL"
},
"source": [
"---"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "cU91rlxQkacM",
"nbgrader": {
"checksum": "767690caa09bf309165134adec898cd2",
"grade": false,
"grade_id": "cell-fc6b5241f439f72f",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"# Homework 11: Scheduling with Dependencies\n",
"\n",
"Copyright Luca de Alfaro, 2019-20. \n",
"License: [CC-BY-NC-ND](https://creativecommons.org/licenses/by-nc-nd/4.0/)."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "ica_ZmxrkacM",
"nbgrader": {
"checksum": "93460885ba39aaf770bbcf46acb31f4a",
"grade": false,
"grade_id": "cell-a13bd1c44a595199",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Submission\n",
"\n",
"[Please submit to this Google Form](https://docs.google.com/forms/d/e/1FAIpQLSdVfcA_LZdtjJoLKBSkyHwbvxXvow-CX4pQEMmW3UVm7X_JrA/viewform?usp=sf_link).\n",
"\n",
"Deadline: Friday December 4, 11pm (check on Canvas for updated information)."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "Kny6AHUmkacM",
"nbgrader": {
"checksum": "90a74a81d08e34489013a1201369ad0a",
"grade": false,
"grade_id": "cell-dcea49d1e015f68d",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Test Format\n",
"\n",
"This test contains 4 questions, for a total of 90 points. "
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "FKxK7Pb0kacM",
"nbgrader": {
"checksum": "637cf59cf5df5ba15cbc30a73b035287",
"grade": false,
"grade_id": "cell-7783f146ca3d6158",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"Assume you have to prepare Pasta Carbonara. My version of the recipe goes like this: \n",
"\n",
"> Dice onions and pancetta, and fry in a mix of olive oil and butter, slowly. Separately, put in a bowl as many eggs as there are dinner guests; you can either put in the bowls the yolks only, or you can add a few whites if you wish. Beat the eggs. \n",
"> Bring water to a boil, and when it boils, salt it. Put the pasta in (I like Penne Rigate). When cooked, colander the water away, and quickly unite in the bowl the beaten eggs, the pasta, and the pancetta. Mix well and serve immediately. \n",
"\n",
"If you have to invite people over, you could do this recipe sequentially, and first worry about cooking the pasta: warming the water, putting the pasta in, then colandering it. Then you could worry about cooking the pancetta and onions. When that's done, you can start to beat the eggs. Finally, you could unite everything. Technically, that would work, but there would be two problems. The first is that, of course, the pasta would be rather cold by the time it would be served, a capital sin (pasta must be served immediately after it is cooked). Secondly, even if you rehash the order so that you first cook the pancetta, then beat the eggs, then cook the pasta, then technically this works -- but it would take you well over one hour to have everything ready. You want to do things in parallel, cooking the pancetta while heating up the water for the pasta, and so forth. You want to discover what are the things that need to be done one after the other, and what are the things that can be done in parallel, and in which order to do everything. \n",
"\n",
"Great cooking, by the way, is much about the perfect timing, not only the perfect preparation. You have to have the various preparations ready at the same time, to unite them just right. We will worry about timing in the second part of this chapter; first, we worry about what we can do and in which order.\n",
"\n",
"As an aside for those of you who are more interested in compiling code than in cooking, the problem of how to compile C or C++ code is very similar. A makefile defines dependencies between tasks: you have to have compiled pathlib.c before you can link the result together with something else. The task of the make program is to figure out how to parallelize the compilation, so that independent tasks can happen in different processes (possibly on different CPU cores), while respecting the precedence constraints between tasks. We will mention this application in some of the exercises of the chapter. \n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "ZDoY3oEIkacM",
"nbgrader": {
"checksum": "c746ef312885249b098a4a4fbf9f588c",
"grade": false,
"grade_id": "cell-fe45e7ce127db0d4",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Scheduling dependent tasks"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "cIxy_GYJkacM",
"nbgrader": {
"checksum": "13ab8e8184a5ce432629a168358998e9",
"grade": false,
"grade_id": "cell-ac839becba0a561a",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"We first disregard the problem of cooking (or compiling) time, and ask about the order in which we should be doing the tasks. We want to create a _Scheduler_ object, that can tell us what to do at the same time. What operations should this object support? \n",
"\n",
"* **add_task:** we should be able to add a task, along with the task dependencies. \n",
"* **reset:** indicating that we are about to run the sequences of tasks again.\n",
"* **available_tasks:** this property should return the set of things that we can do in parallel. \n",
"* **mark_completed:** used to notify the scheduler that we have completed a task. This should return the set of new tasks that we can do due to this task being completed; we can do these tasks in parallel alongside with the others that we are already doing. \n",
"* **all_done:** returns True/False according to whether we have completed all tasks. \n",
"\n",
"Choosing these operations is perhaps the most important step in the design of the scheduler. The operations need to have a simple, clear definition, and be useful in a concrete implementation of the service which will run the tasks. Of the above operations, they are all uncontroversial, except for the choice of behavior of _completed_. In theory, there is no need for _completed_ to return the set of _new_ tasks that can now be undertaken. If one remembers the set of tasks $T_1$ one can a do before a task $t \\in T_1$ is completed, and marks $t$ as completed, one can simply ask the scheduler for the set of tasks $T_2$ that can now be done, and add those in $T_{21t} = T_2 \\setminus (\\{t\\} \\cup T_1)$ for execution. However, we guess (as we have not yet written the task execution engine) that being told this set of tasks directly will simplify the design of the task execution engine. "
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "yk-RsN-TkacM",
"nbgrader": {
"checksum": "79aecd3e08b0a5afe9f42889882e0bda",
"grade": false,
"grade_id": "cell-307dbeebce53643f",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"Our scheduler class will be implemented in similar fashion to our graph class, with tasks corresponding to graph vertices, and dependencies represented as edges.\n",
"The difference is that here, given a vertex (that is, a task) $v$, it will be useful to be able to access both:\n",
"\n",
"* the _predecessors_ of $v$, that is, the tasks $u$ that are declared as prerequisites of $v$, and \n",
"* the _successors_ of $v$, that is, the tasks $u$ such that $v$ was declared as a prerequisite for $u$. \n",
"\n",
"When we add a task, we would have to initialize its set of successors and predecessors to empty. This is somewhat tedious, and so we resort to a defaultdict, which is a special type of dictionary such that, if the mapping for a key has not been defined, it returns a default value; in our case, an empty set. [You can read more about defaultdict and related types here](https://docs.python.org/3.7/library/collections.html#collections.defaultdict). \n",
"\n",
"Our first implementation of the class is as follows. We let you complete the `available_tasks` and `mark_completed` methods. \n"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"deletable": false,
"editable": false,
"id": "_yCelWBbkacM",
"nbgrader": {
"checksum": "a3122da716c36329d70b6398881d9f6c",
"grade": false,
"grade_id": "cell-c1f62e6e5511e278",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"outputs": [],
"source": [
"from collections import defaultdict\n",
"import networkx as nx # Library for displaying graphs.\n",
"import matplotlib.pyplot as plt\n",
"\n",
"class DependencyScheduler(object):\n",
"\n",
" def __init__(self):\n",
" self.tasks = set()\n",
" # The successors of a task are the tasks that depend on it, and can\n",
" # only be done once the task is completed.\n",
" self.successors = defaultdict(set)\n",
" # The predecessors of a task have to be done before the task.\n",
" self.predecessors = defaultdict(set)\n",
" self.completed_tasks = set() # completed tasks\n",
"\n",
" def add_task(self, t, dependencies):\n",
" \"\"\"Adds a task t with given dependencies.\"\"\"\n",
" # Makes sure we know about all tasks mentioned.\n",
" assert t not in self.tasks or len(self.predecessors[t]) == 0, \"The task was already present.\"\n",
" self.tasks.add(t)\n",
" self.tasks.update(dependencies)\n",
" # The predecessors are the tasks that need to be done before.\n",
" self.predecessors[t] = set(dependencies)\n",
" # The new task is a successor of its dependencies.\n",
" for u in dependencies:\n",
" self.successors[u].add(t)\n",
"\n",
" def reset(self):\n",
" self.completed_tasks = set()\n",
"\n",
" @property\n",
" def done(self):\n",
" return self.completed_tasks == self.tasks\n",
"\n",
"\n",
" def show(self):\n",
" \"\"\"We use the nx graph to display the graph.\"\"\"\n",
" g = nx.DiGraph()\n",
" g.add_nodes_from(self.tasks)\n",
" g.add_edges_from([(u, v) for u in self.tasks for v in self.successors[u]])\n",
" node_colors = ''.join([('g' if v in self.completed_tasks else 'r')\n",
" for v in self.tasks])\n",
" nx.draw(g, with_labels=True, node_color=node_colors)\n",
" plt.show()\n",
"\n",
" @property\n",
" def uncompleted(self):\n",
" \"\"\"Returns the tasks that have not been completed.\n",
" This is a property, so you can say scheduler.uncompleted rather than\n",
" scheduler.uncompleted()\"\"\"\n",
" return self.tasks - self.completed_tasks\n",
"\n",
" def _check(self):\n",
" \"\"\"We check that if t is a successor of u, then u is a predecessor\n",
" of t.\"\"\"\n",
" for u in self.tasks:\n",
" for t in self.successors[u]:\n",
" assert u in self.predecessors[t]\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "WxGmfJPCkacM",
"nbgrader": {
"checksum": "f7194367628d4362f83e04121a68a6e4",
"grade": false,
"grade_id": "cell-1d75cf1333aa8c76",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Question 1: implement `available_tasks` and `mark_completed`. "
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"deletable": false,
"id": "W3lz1UGRkacM",
"nbgrader": {
"checksum": "f830262ac9c7f13eb8f07e85e0e1ac11",
"grade": false,
"grade_id": "cell-5c9e5f503f616888",
"locked": false,
"schema_version": 1,
"solution": true
}
},
"outputs": [],
"source": [
"### Implementation of `available_tasks` and `mark_completed`.\n",
"\n",
"def scheduler_available_tasks(self):\n",
" \"\"\"Returns the set of tasks that can be done in parallel.\n",
" A task can be done if all its predecessors have been completed.\n",
" And of course, we don't return any task that has already been\n",
" completed.\"\"\"\n",
" # YOUR CODE HERE\n",
" return ({t for t in self.tasks \n",
" if self.predecessors[t].issubset(self.completed_tasks)}\n",
" - self.completed_tasks)\n",
"\n",
"def scheduler_mark_completed(self, t):\n",
" \"\"\"Marks the task t as completed, and returns the additional\n",
" set of tasks that can be done (and that could not be\n",
" previously done) once t is completed.\"\"\"\n",
" # YOUR CODE HERE\n",
" for p in self.predecessors[t]:\n",
" if p in self.uncompleted:\n",
" raise IllegalCompletion(t)\n",
" \n",
" self.completed_tasks.add(t)\n",
" return {u for u in self.successors[t] \n",
" if self.predecessors[u].issubset(self.completed_tasks)}\n",
"\n",
"DependencyScheduler.available_tasks = property(scheduler_available_tasks)\n",
"DependencyScheduler.mark_completed = scheduler_mark_completed\n"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"deletable": false,
"id": "RnTGjkVhkacM",
"nbgrader": {
"checksum": "9cbfd3fceef4fc700ee6fd8765c94e66",
"grade": false,
"grade_id": "cell-ab6c2cd521650cd4",
"locked": false,
"schema_version": 1,
"solution": true
}
},
"outputs": [],
"source": [
"# Here is a place where you can test your code. \n",
"\n",
"# YOUR CODE HERE"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "fbDAHS7IkacM",
"nbgrader": {
"checksum": "9abcbb7a57e188e7f19741fdef160c7f",
"grade": false,
"grade_id": "cell-3e19369eeb9a643d",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"Let us check if this works."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"deletable": false,
"editable": false,
"id": "5OGt-_BgkacM",
"nbgrader": {
"checksum": "34c28ee0d4c755735562b962526341d2",
"grade": false,
"grade_id": "cell-92b59a47fe7f0336",
"locked": true,
"schema_version": 1,
"solution": false
},
"outputId": "ac6123c0-6313-4ebd-c8e5-4a85b59bc0a6"
},
"outputs": [],
"source": [
"# Let us ensure that nose is installed.\n",
"try:\n",
" from nose.tools import assert_equal, assert_true\n",
" from nose.tools import assert_false, assert_almost_equal\n",
"except:\n",
" !pip install nose\n",
" from nose.tools import assert_equal, assert_true\n",
" from nose.tools import assert_false, assert_almost_equal\n"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 353
},
"deletable": false,
"editable": false,
"id": "6vuF6du9kacM",
"nbgrader": {
"checksum": "af201e981d4b861bf954b7e2384b3e9a",
"grade": false,
"grade_id": "cell-d9857dde3e277260",
"locked": true,
"schema_version": 1,
"solution": false
},
"outputId": "1f85633c-afa2-40fb-e026-17c3729ff9d6"
},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAd0AAAE/CAYAAAADsRnnAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3Xl0lPXd9/FPyAJkY98JJIAsoWJFqiwlYQnBQGbwRrmlhQcLR8Fzq1BRyqO0j8V6rJweit51Qcstp2oFSqU6E8KSGwiJgEVwQwRZyhIKsoUlK1lmnj/GGQNMQpaZ65pJ3q9zPEFyJflwPIePv+v6/b5XiNPpdAoAAPhdM7MDAADQVFC6AAAYhNIFAMAglC4AAAahdAEAMAilCwCAQShdAAAMQukCAGAQShcAAINQugAAGITSBQDAIJQuAAAGoXQBADAIpQsAgEEoXQAADELpAgBgEEoXAACDULoAABiE0gUAwCCULgAABqF0AQAwSJjZAYJCQYG0a5eUny81aya1by+NGCE1b252MgBAEKF0a/L119KyZdKqVVJ4uOR0SiEhrs85ndLs2dLjj0vx8abGBAAEhxCn0+k0O0TAqaiQHn5Y+tvfpLIyqbLS+3UREa6V74IF0uLFPxQyAABeULo3qqiQ0tOl3FypuLh2XxMZKU2fLi1fTvECAKrFRqobPfFE3QpXcl373nvSH//ov1wAgKDHSreq06elXr2ka9fq9/XR0dK5c1LLlr7NBQBoFFjpVvXGGw3/HmvXNvx7AAAaJVa6bhUVUocO0uXLXj99WtITknIkRUt6UtJcbxcOGCB9842/UgIAghgrXbdjx6Tycq+fckiySLpD0r8lbZH0sqRN3i4+eLDa7wMAaNooXbfLl6Uw78eWP5V0XtL/kxQhqZekRySt9nZxRIR05YqfQgIAghnDMdwiIlwDL7w4Idft5dZVfq9S0khvFzscru8FAMANKF23zp2r3bUcJylB0uHafJ+QECkmxofBAACNBbeX3Tp1kgYN8vqpuyXFSloiqUSuVe7Xct12vk6zZtIDDzAgAwDgFaVb1cKFXlepoZLskr6Qa8XbXtLDkm56ctuihfTUU34OCQAIVhwZqqq83HWbOT+/7l8bEiIlJrpekgAAgBesdKsKD5fWravfRKnoaAZjAABqROneKDnZ9Sq/yMjaXR8SIsXGSps2uQZjAABQDUrXm0mTpK1bpcGDXave0NCbr4mIcD3DTU6WPv1UGjbM+JwAgKDCM91b2b/f9SL7jAypsFAOSWdLStRl/nzpscd4gT0AoNYo3TpyOByKjY3V6dOnFRsba3YcAEAQ4fZyHTVr1kz9+/fXN7zUAABQR5RuPQwcOJDSBQDUGaVbD4mJidq/f7/ZMQAAQYbSrYfExERWugCAOqN062HgwIGsdAEAdcbu5XpwOByKiYnRmTNn2MEMAKg1Vrr14N7BfPDgQbOjAACCCKVbT2ymAgDUFaVbTxwbAgDUFaVbT6x0AQB1RenWEytdAEBdsXu5niorKxUTE6Nz584pOjra7DgAgCDASreeQkND1a9fPx04cMDsKACAIEHpNgBDMgAAdUHpNgDjIAEAdUHpNgArXQBAXVC6DcBKFwBQF+xebgD3Dubz588rKirK7DgAgADHSrcBQkND1bdvX3YwAwBqhdJtIG4xAwBqi9JtIDZTAQBqi9JtIFa6AIDaonQbiJUuAKC22L3cQBUVFYqJidGFCxfYwQwAqBEr3QYKCwtT3759dfDgQbOjAAACHKXrAzzXBQDUBqXrAzzXBQDUBqXrA6x0AQC1Qen6AKULAKgNdi/7gHsH88WLFxUZGWl2HABAgGKl6wNhYWHq06ePvv32W7OjAAACGKXrI2ymAgDcCqXrIzzXBQDcCqXrI6x0AQC3Qun6CCtdAMCtsHvZR8rLyxUbG6v8/Hy1bNnS7DgAgADEStdHwsPD1bt3b3YwAwCqRen6ELeYAQA1oXR9iM1UAICaULo+xEoXAFATSteHWOkCAGrC7mUfKisrU6tWrXTp0iW1aNHC7DgAgADDSteHIiIi1KtXL3YwAwC8onR9jOe6AIDqULo+lpiYyHNdAIBXlK6PDRw4kJUuAMArStfHWOkCAKrD7mUfKysrU2xsrK5cuaLmzZubHQcAEEBY6fpYRESEEhISdOjQIbOjAAACDKXrBwzJAAB4Q+n6AceGAADeULp+wGYqAIA3lK4fcGwIAOANu5f94Nq1a2rVqhU7mAEA12Gl6wfNmzdXfHy8Dh8+bHYUAEAAoXT9hOe6AIAbUbp+wnNdAMCNKF0/4dgQAOBGlK6fMCADAHAjdi/7SWlpqVq3bq2rV68qIiLC7DgAgADAStdPWrRooR49erCDGQDgQen6EZupAABVUbp+xLEhAEBVlK4fsdIFAFRF6foRx4YAAFWxe9mPSkpK1LZtW129elXh4eFmxwEAmIyVrh+1bNlS3bt315EjR8yOAgAIAJSunzEkAwDgRun6Gc91AQBulK6fcWwIAOBG6foZx4YAAG7sXvaz4uJitWvXTgUFBQoLCzM7DgDARKx0/SwyMlLdunVjBzMAgNI1ApupAAASpWsIjg0BACRK1xCsdAEAEqVrCFa6AACJ3cuGYAczAEBipWuIyMhIdenSRf/617/MjgIAMBGlaxBuMQMAKF2DsJkKAEDpGoSVLgCA0jUIK10AALuXDVJUVKQOHTqooKBAoaGhZscBAJiAla5BoqKi1KlTJ3YwA0ATRukaiFvMANC0UboGYjMVADRtlK6BWOkCQNNG6RqIlS4ANG3sXjZQYWGhOnbsyA5mAGiimL5voOjoaHXs2FHHjh1Tnz59zI4DND4XLkgrV0q7dkn5+VJ0tNS3r/Tww1JiotnpAErXaO7nupQu4ENffSX97neS3S41ayaVlPzwuU2bpOXLXaW7aJF0331SSIh5WdGk8UzXYAMHDmQzFeBLa9dKw4ZJ69ZJ165dX7iSVFHh+r29e6X/83+kRx+VKivNyYomj9I1WGJiIpupAF+x2aSHHpKKiyWH49bXFxVJ770nzZ4tsZ0FJqB0DcaxIcBH8vKkn/3s5pXtrRQXS6tXS3/9q39yATWgdA2WmJiogwcPylGb/ysHUL1XX3XdOq6P4mJp8WJWuzAcpWuwmJgYtWvXTsePHzc7ChC8yspcm6PKyrx+Ok/SZEkdJLWT9Li3i86ckXbv9ltEwBtK1wQMyQAaKCOj2lVqpaR0ST0lHZf0b0lTvV1YUiL993/7KSDgHaVrAp7rAg109Gi1z3J3Szot6Q+SoiS1kPRTbxc6HNKBA/5KCHhF6ZqAY0NAAxUUyFnN89w8uVa5tRpCUFjow1DArTEcwwSJiYl6/fXXzY4BBLTy8nKdOnVKx44d0/Hjx3Xs2DHPr1P37dNCSc29fF2cpJOSKlSLv+BiY32cGqgZpWuCqjuYmzXjZgOapsrKSp0+ffq6Uq368cyZM+rcubPi4+OVkJCg+Ph4jRs3TvHx8Rpw7Jgi5s6VCgpu+r53S+oi6f9KWiwpVNJeSSNuvDA0VPrxj/38pwSuxwsPTBIXF6ecnBwlJCSYHQXwC4fDobNnz1Zbqnl5eWrfvv11pVr1Y/fu3RUREeH9m1dWSp06SRcvev30SUlzJeVKCpH0c0k3bZmKjHTNaB40yFd/ZOCWWOmaxL2ZitJFsHI6nbpw4UK1pXrixAnFxMQoISHBU6ZDhgzRAw88oISEBPXo0UMtWrSo3w8PDZXmzZNefFEqLb3p0z0kfXir73HbbRQuDMdK1yTz589Xly5dtGDBArOjANW6dOnSTYXq/vXx48cVERHhdZUaHx+v+Ph4RUVF+S/cuXNSnz5ebzHfUmSk9P770qRJvs8F1ICVrkkSExP18ccfmx0DTVxBQYHXVar7o8PhuK5Me/furZSUFE+ptmrVyrzwHTu6zuumpbkmTNVSsaTSGTPUlsKFCShdkwwcOFBvvfWW2THQyBUXF+vEiRPVlmpJSYmnQN3l+tOf/tTz723atFFIIL8GLynJVbxWq2s6VTUTqiS5XufXsqUOpKTo/sxM5eblKS4uzrisgLi9bJrLly8rLi5OV65cYQcz6u3atWs6efLkTbd+3R8vX76sHj16XPdcterHDh06BHap1tbJk9LLL0srVrgmVVU9f+t+bjxunLRwoTRihJYtW6bly5crJydHnTp1MiczmiRK10Tdu3fXjh071LNnT7OjIEBVVFQoLy+v2lvA58+fV7du3ap9rtqlS5em9T91paXS3/8uffaZdP686xxur17StGlS587XXbp48WKtW7dO2dnZatOmjUmB0dRQuiZKTU3VL3/5S02YMMHsKDCJ+6xqdaV65swZderUqdpS7datm8LCeEpUH06nU08//bR27NihrKwsxcTEmB0JTQCla6Inn3xS3bp109NPP212FPiJ0+nUd999V22p5uXlqV27dtWWalxcXPVnVdFgTqdTs2fP1tGjR5WZmVn/I0xALVG6Jvrzn/+sXbt26e233zY7CurJ6XTq4sWLXo/UHDt2zHNWtboBED179uQvepNVVlZq+vTpKiws1Lp16xQeHm52JDRilK4JnE6nsrOz9cEHH2jVqlXq2LGjbr/9dv3tb38zOxq8uHz5crW7f48fP66wsLBqNyr17NlT0dHRZv8RcAvl5eW6//77FRUVpffee0+hoaFmR0IjRemaoLS0VO3bt1dpaakqKysVEhKi2bNna/ny5WZHa5IKCwurLdVjx46psrKy2lI1/awqfKa0tFQTJ05Ur1699NZbbzWOXd0IOJSuSdasWaNZs2apuLhY0dHR+uijjzRmzBizYzVKJSUlnlWpt1ItLi6u9vZvfHy82rZty1/ATURhYaHGjRunYcOGaenSpfx3h89RuiaaPn263n//fUVERKigoIBnSfV041nVGz9WPavqrVQ7duzIX67wuHTpkkaNGqXJkyfrueeeMzsOGhlK10RFRUWeV5ft27fP7DgBi7OqMNrZs2eVlJSkOXPmaP78+WbHQSNC6Zrp6lWdePFFRR44oA7NmkkxMVL//tKMGVL37manMwxnVRGI8vLyNHLkSC1atEiPPPKI2XHQSFC6Zjh4UFqyRFqzRmrWTCoq+uFzzZu7ZsQmJ0vPPOP6GOScTqfnvaqcVUUwOXLkiJKTk7V06VJNnTrV7DhoBChdo334oWskXVmZVFFR87WRkdKCBdJzz7mKOEB5O6t643tVo6OjOauKoPT1118rJSVFf/7zn2WxWMyOgyBH6RrJZpOmTpVKSjy/FS9phaSU6r4mMlKaP1/63e/8n68GtzqrGh4eXmOpclYVwezTTz/VxIkTtXr1ak4ZoEEoXaMcPy796EfX30pWLUpXchXv2rWSH2c0c1YVqNn27ds1ZcoU2Ww2DR061Ow4CFKUrlGefFJ6/fWb3vcZr1qUriT95CfS7t2ef62oqNDSpUs1cOBApaen3/LHc1YVaLgNGzboF7/4hTZv3qw77rjD7DgIQpSuEUpLpQ4drn/H5/fiJc2R9K6kM5Luk/SGpJuecLZsKe3dKw0YoAMHDmjKlCk6ePCgHnjgAa1evZqzqoBB1q5dq3nz5ik7O1t9+/Y1Ow6CDKVrhNWrpdmzpYKCmz4VLyla0gZJUZIskkZLeuHGC8PC5JwzR4+Wl2vlypUqLy+XJEVFRal169acVQUMtHLlSv32t79VTk4O78NGnXC40Qjffut1lev2uKS473+9SNIT8lK6FRUq3b1bf/nqKzkcDoWEhMjpdCo8PFw7duzgrCpgoJkzZ6qgoEApKSnKzc1V586dzY6EIMHSxwiXLkk13FCIq/LrnpJOV3Ndy7IylZSUKCcnR7NmzVJMTIyKiorUo0cPChcw2Ny5c/WLX/xC48aNU35+vtlxECQoXSO0bl3jOdu8Kr8+KalrdRfGxiokJETDhw/XihUrlJ+fr6+++opnsYBJnn32WU2YMEH33nuvCrw8PgJuROkaoW9fqYZzqq9JOiUpX9KLkh70ck1FSIiORkaqsMpt6rCwMPXv39/HYQHUVkhIiF566SXdddddslgsKqlyBh/whtI1wn/8R423l38uKVVSr+//+bWXa5xhYfr91avq2rWr0tLS9MYbb+jUqVP+yQug1kJCQvTaa6+pe/fueuCBB1R2w7FAoCp2Lxtl3jzpjTek73cd19ldd0l79ujq1avatGmTbDabMjMz1bNnT1ksFlmtVg0ePJhbzYBJysvLNWXKFEVERGjVqlUKDQ01OxICEKVrlGPHXBOpiovr/rWRka6XI9wwBKOiokI7d+6UzWaTzWZTcXGx0tPTZbVaNWbMGOYZAwYrLS2VxWJRXFycVqxYwTE93ITSNdI//uF62UFdnvtERkpPPCG99NItL/32229lt9tls9n05ZdfasyYMbJYLJo4caI6derUgOAAaquoqEipqakaMmSIXn75Ze4+4TqUrtH+/nfpoYeka9ekysqar3W/7OD55+v8lqGLFy8qMzNTNptNWVlZGjBggKxWq6xWqxITE/mLAPCjy5cva/To0bJYLHr++efNjoMAQumaYf9+6fe/lz74wPU+3aq3nCMiXL83YoT07LOSD95ocu3aNW3fvt2zCg4NDZXVapXFYlFSUpLCw8Mb/DMAXO/8+fNKSkrSrFmztGDBArPjIEBQuma6fFl65x1pzx4pP1+KiZH69ZNmzpT8NFrO6XRq3759stlsstvtOnTokMaPHy+r1aq0tDS1adPGLz8XaIpOnTqlpKQkLVy4UHPmzDE7DgIApdvEnTlzRhkZGbLb7crOztZdd93lWQX36dPH7HhA0Dt69KiSk5O1ZMkSTZs2zew4MBmlC4/i4mJt2bJFNptNGRkZatOmjec40tChQzkCAdTT/v37NXbsWL355puaNGmS2XFgIkoXXjkcDu3Zs8dzG/r06dOaOHGiLBaLUlNTFRMTY3ZEIKjs3btXaWlpev/995WScss3aKORonRRKydOnPBsxPrkk080YsQIWSwWz5lEALeWm5ur+++/Xx9++KGGDx9udhyYgNJFnbmnYtntdmVmZiouLs7zHHjw4MEMBABqsGnTJs2YMUMbN27UnXfeaXYcGIzSRYO4p2K5V8GFhYXXTcVq2bKl2RGBgLNu3To99thj2rp1qwYMGGB2HBiI0oVPuadi2e12ffHFFxo9erSsVitTsYAbvPPOO1q0aJFycnKUkJBgdhwYhNKF31y8eFEbNmyQzWbT5s2bNWDAAM9u6IEDBzIVC03ea6+9pj/+8Y/Kzc1V167VvkkbjQilC0OUlZVp+/btnt3QzZo18xTwyJEjFRERYXZEwBQvvfSS3n33XW3fvl3t27c3Ow78jNKF4dxTsdzPgd1TsSwWi9LS0tS2bVuzIwKGevbZZ7V582Zt2bJFrVq1MjsO/IjShenOnDmj9evXy2azKTs7W4MHD/bshr7tttvMjgf4ndPp1BNPPKEvv/xSmzZtUmRkpNmR4CeULgKKeyqWezNW69atPQU8bNgwpmKh0XI4HJo5c6a+++472Ww2NW/e3OxI8ANKFwHL4XBo7969nufA//73vzVhwgRZrVamYqFRqqio0IMPPihJWrNmjcLCwkxOBF+jdBE03FOx7Ha7du7cqREjRnhWwUzFQmNx7do1TZo0SZ06ddLKlSsZNtPIULoISlevXtXmzZtls9k8U7Hcu6GZioVgV1xcrHvvvVeDBg3Sn/70J47XNSKULoJeRUWFdu3a5dkNffXqVc9c6LFjxzIVC0HpypUrGjt2rFJTU/Xiiy+aHQc+Qumi0Tl06JCngD///HONGTNGFotF6enpTMVCULlw4YKSk5M1ffp0PfPMM2bHgQ9QumjU3FOx7Ha7Nm3apP79+8tqtTIVC0Hj9OnTSkpK0pNPPqnHHnvM7DhoIEoXTUZZWZlycnJks9lks9kUEhLi2YiVlJTEVCwErGPHjikpKUkvvPCCHnroIbPjoAEoXTRJTqdTX3/9tec40rfffqvU1FRZrVamYiEgHThwQGPGjNGrr76q+++/3+w4qCdKF5D03XffeaZibdu2jalYCEiff/65xo8fr3fffVfjx483Ow7qgdIFblBSUqItW7bIZrMpIyNDrVq18hxHYioWzLZjxw7dd999WrdunUaOHGl2HNQRpQvUwD0Vy70bmqlYCARZWVmaNm2aMjMzNWTIELPjoA4oXaAOTpw4oYyMDNlsNu3atUvDhw/3nAnu0aOH2fHQhHz44Yd69NFHtWXLFg0cONDsOKglSheoJ/dULLvdrvXr16t79+6e58B33XUXU7Hgd3/961+1cOFCbd++Xb179zY7DmqB0gV8oLKyUrt27fLshr5y5QpTsWCI5cuXa8mSJcrNzVX37t3NjoNboHQBP3BPxbLb7frss880evRoWa1WTZw4UZ07dzY7HhqZP/zhD3r77be1fft2dezY0ew4qAGlC/hZfn6+NmzYIJvNps2bN6tfv36e3dA/+tGPmIoFn/jNb36jjIwMbdu2Ta1btzY7DqpB6QIGck/Fcu+GluQpYKZioSGcTqd++ctfas+ePdq8ebOioqLMjgQvKF3AJO6pWO4Cdk/FslgsmjBhAlOxUGcOh0MPP/yw8vLyZLfb1aJFC7Mj4QaULhAg3FOx7Ha7tm7dqsGDB3tWwUzFQm1VVlbqZz/7mcrKyrR27VqFh4ebHQlVULpAACopKdHWrVs9u6FjY2M9x5GGDRumsLAwsyMigJWVlem+++5T27Zt9c4773B8LYBQukCAczgc+uyzzzwFnJeX55mKNX78eKZiwauSkhKlpaVpwIABev3119mwFyAoXSDInDx50jMVa+fOnRo2bJhnFcxULFR19epVpaSkaNSoUVqyZAnFGwAoXSCIFRQUaPPmzbLZbMrMzFS3bt08z4GZigVJunjxokaNGqWpU6dq0aJFZsdp8ihdoJFwT8Vy74a+cuWK0tPTZbVamYrVxJ05c0ZJSUl64oknNHfuXLPjNGmULtBIHT582DMVa+/evRo9erQsFovS09OZitUEnThxQklJSfrtb3+rmTNnmh2nyaJ0gSbAPRXLbrdr06ZN6tu3r+c58O23386zvibi0KFDGjVqlF555RVNmTLF7DhNEqULNDFlZWXKzc2VzWaTzWaT0+n0FHBycjJTsRq5L7/8UqmpqVq5cqUmTJhgdpwmh9IFmjCn06n9+/d7jiMdOHBAqampslqtSktLU7t27cyOCD/45JNPZLVatXbtWiUnJ5sdp0mhdAF4nD17VhkZGbLb7dq2bZt+/OMfe3ZD9+3b1+x48KGtW7dq6tSpysjI0N133212nCaD0gXglXsqlnszVkxMjKeAmYrVONjtdj3yyCPKysrS7bffbnacJoHSBXBL7qlY7uNI7qlYFotF48ePV2xsrNkRUU+rV6/WU089pezsbGZ8G4DSBVBn7qlYdrtdO3bs0NChQz2bsXr27Gl2PNTRihUr9MILLyg3N1dxcXFmx2nUKF0ADVJQUKCsrCzZbDatX79eXbt29RTwkCFDmIoVJJYtW6bly5crJydHnTp1MjtOo0XpAvCZyspKffLJJ57d0JcuXbpuKlZkZKTZEVGDxYsXa926dcrOzlabNm3MjtMoUboA/ObIkSOe58B79+7VqFGjZLVamYoVoJxOp5566int3LlTWVlZvMHKDyhdAIa4dOmSNmzYIJvN5pmK5d4NzVSswOF0OjV79mwdPXpUmZmZatGihdmRGhVKF4Dh3FOx3KvgyspKWa1WWa1WpmIFgMrKSk2bNk1FRUVat26dwsPDzY7UaFC6AEzldDr1zTffeJ4Df/PNN0pNTZXFYtGECROYimWS8vJyTZ48WdHR0XrvvfcUGhpqdqRGgdIFEFDOnj2r9evXy263a+vWrbrjjjs8u6H79etndrwmpaSkRBMnTlTv3r311ltv8QjAByhdAAGrpKRE27Zt86yCo6OjPQU8fPhwpmIZoKCgQOPGjdPw4cO1dOlSireBKF0AQcHpdF43FevkyZNKS0uT1WplKpaf5efna/To0Zo8ebKee+45s+MENUoXQFDKy8tTRkaGbDabZyqWxWKRxWJRfHy82fEanbNnz2rkyJF69NFHNX/+fLPjBC1KF0DQc0/FstvtysjIUNeuXT3HkZiK5TsnT55UUlKSFi1apEceecTsOEGJ0gXQqFRWVuqf//ynbDabbDYbU7F87PDhwxo1apSWLl2qqVOnmh0n6FC6ABo191Qsu92uPXv2aNSoUbJYLEpPT1eXLl3MjheU9u3bp5SUFP3P//yP0tPTzY4TVChdAE3GpUuXtHHjRtlsNm3cuFG33XabZygHU7HqZvfu3UpPT9eaNWs0evRos+MEDUoXQJNUXl6u3Nxcz21o91Qsi8Wi5ORkNW/e3OyIAS87O1v/+Z//KZvNpqFDh5odJyhQugCaPPdULPdxpG+++Ubjxo2T1WplKtYtZGZmaubMmcrKytKgQYPMjhPwKF0AuMG5c+e0fv162Ww2pmLVwtq1azVv3jxlZ2erb9++ZscJaJQuANSgtLRUW7du9ayCo6OjPceRmIr1g7fffluLFy9WTk6OevbsaXacgEXpAkAtOZ1Off75556xlMePH9eECRNksVh07733NvmpWK+88opeffVV5ebm8r7kalC6AFBP7qlYdrtdH3/8MVOxJL3wwgtas2aNtm/frrZt25odJ+BQugDgA4WFhcrKypLNZtP69evVuXNnz3Pgn/zkJ01mKpbT6dTChQuVnZ2tLVu2KCYmxuxIAYXSBQAfqzoVy263Kz8/XxMnTpTValVKSkqjn4rldDr1X//1Xzpw4IA2bNigli1bmh0pYFC6AOBnR48e9WzE2rNnj5KTk2W1Whv1VCyHw6EZM2bo0qVL+sc//qGIiAizIwUEShcADFR1KtamTZvUp08fz27oQYMGNaqpWOXl5ZoyZYoiIiK0atUqhYaGmh3JdJQuAJjEPRXLvQquqKjwFHBjmYpVWloqi8WiuLg4rVixosk8264OpQsAAcDpdOrAgQOesZTuqVgWi0UTJkxQ+/btzY5Yb0VFRUpNTdWQIUP08ssvN6rVfF1RugAQgNxTsex2u7az58swAAAGpElEQVRs2aJBgwZ5Xs4QjFOxLl++rNGjR8tisej55583O45pKF0ACHClpaXatm2bZzd0ZGSk5zjSiBEjgmYq1vnz55WUlKRZs2ZpwYIFZscxBaULAEHE21SstLQ0Wa1WjR8/Xq1atTI7Yo1OnTqlpKQkLVy4UHPmzDE7juEoXQAIYqdOnVJGRoZsNps+/vhj3XPPPZ5VcKBOxTp69KiSk5O1ZMkSTZs2zew4hqJ0AaCRcE/FstvtysjIUOfOnT27oQNtKtb+/fs1duxYvfnmm5o0aZLZcQxD6QJAI+SeiuU+jnTx4kWlp6fLYrEoJSVFUVFRZkfU3r17lZaWpvfff18pKSlmxzEEpQsATYB7Kpbdbtenn36q5ORkWSwWpaenq2vXrqblys3N1eTJk/XRRx9p+PDhpuUwCqULAE3M5cuXPVOxNm7cqN69e3ueA99xxx2Gn6PduHGjZsyYoU2bNunOO+809GcbjdIFgCasvLxcH3/8sWcoR3l5uec58KhRowybivXBBx/o8ccf19atWzVgwABDfqYZKF0AgKQfpmK5nwPv379fKSkpslqthkzF+stf/qJf//rXysnJUUJCgpxOp5xOZ0BtAGsoShcA4NW5c+eUmZkpm83mmYrlXgX369fPL7ehX331VS1btkwfffSRpk6dqgcffFC/+c1vfP5zzELpAgBuyT0Vy70KbtmypWcspa+nYj3zzDNaunSpHA6HEhISdPjwYZ99b7NRugCAOnE6nfriiy88z4HdU7EsFovuvffeBk3FOnXqlO655x599913cjgcat68uY4cOaLu3bv/cFFxsfTPf0oXL0rNmknt2klDh0pB8FYmShcA0CDuqVh2u125ubm65557ZLFYZLFYlJCQUKfv9cknn+i+++5TUVGRCgsLFRISomXLlmnevHnSoUPSyy9L77wj3fhuXqdTmjNHevxxqWdPH/7pfIvSBQD4TGFhof73f/9XNptN69evV8eOHT3Hke6+++5abYpyOp3asWOH3nzzTa1atUo9u3fX0YkTpZUrpYoKqbzc+xdGRLhWvk8/LT3/vBSArxCkdAEAflFZWandu3d7Xs5w4cKFaqdiFRYW6vXXX9eTTz6p8PBwz+8XFRTIOXmyonfudN1Wro3ISOnnP5feeivgipfSBQAY4l//+pdnI9ann36qpKQkWa1WpaenKzs7W9OnT9fYsWNlt9vVokUL1xc99ZS0fHntC9ctMlJ67jnpV7/y/R+kAShdAIDh3FOx7Ha7NmzYIIfDoStXrqh58+a68847lZWVpeiSEikuTrp2rX4/JCpKOnfOVcABgtIFAJiquLhYbdu21bUq5dq+fXudmTtXYb//vVRSUr9vHB0tvfKKNGuWj5I2XOMZ8wEACEr79u3TtWvXFBYWpm7dumnEiBFK/ulPFfqnP1VbuC9J6i0pRlKipH94u6iwUHrpJb/lrg9WugAAU5WXl+vIkSPq1avXD7Oe8/Kk/v2rfZa7VtIISZ2///UsSUckdbnxwtBQqaBAatnST+nrhpUuAMBU4eHhGjBgwPUvV7h8WaphytUUSV3lKrEHJd0mabe3CyMipEuXfBm3QShdAEDgCQ93DbyoxjuSfiyp9ff/fC3pgrcLHQ5X8QYI3w3LBADAVzp2rHbX8glJj0jaImmYpFC5CthrRTscUuvWfgpZd6x0AQCBp21bacgQr58qkhQiqcP3/75SrpXuTUJCpPT0Gm9TG43SBQAEpl/9SoqJuem3EyU9Jdcqt5OkfXJtqrpJZKRrJGQAYfcyACAwVVRIXbpIF7w+rb213r2lw4cDahQkK10AQGAKC5PWravfRKmoKOmDDwKqcCVKFwAQyEaOlFatqlvxRkdL69dLd9zhv1z1ROkCAAKb1Spt2ybdeadryMWN79KVXEeMWrRwvcx+1y4pOdn4nLXAM10AQPD4+mtp2TLJbndNmgoJkWJjpSlTpLlzpdtuMzthjShdAAAMwu1lAAAMQukCAGAQShcAAINQugAAGITSBQDAIJQuAAAGoXQBADAIpQsAgEEoXQAADELpAgBgEEoXAACDULoAABiE0gUAwCCULgAABqF0AQAwCKULAIBBKF0AAAxC6QIAYBBKFwAAg1C6AAAYhNIFAMAglC4AAAahdAEAMAilCwCAQShdAAAMQukCAGAQShcAAINQugAAGITSBQDAIJQuAAAGoXQBADAIpQsAgEEoXQAADELpAgBgEEoXAACDULoAABiE0gUAwCCULgAABqF0AQAwyP8HHrPAJ2O9v5cAAAAASUVORK5CYII=\n",
"text/plain": [
"