Last active
February 12, 2020 11:17
-
-
Save t-flora/628da0a774531abdd50c6641891ff786 to your computer and use it in GitHub Desktop.
CS110 5.2 Quicksort
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "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": {}, | |
| "outputs": [], | |
| "source": [ | |
| "NAME = \"Tiago Flora\"\n", | |
| "COLLABORATORS = \"Chloe Go\"" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "---" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "deletable": false, | |
| "editable": false, | |
| "nbgrader": { | |
| "checksum": "1a4c3cfc3c34bf644ee45d91835b6f70", | |
| "grade": false, | |
| "grade_id": "cell-61b183447ded09ef", | |
| "locked": true, | |
| "schema_version": 1, | |
| "solution": false | |
| } | |
| }, | |
| "source": [ | |
| "# CS110 Pre-class Work 5.2\n", | |
| "\n", | |
| "## Question 1.\n", | |
| "Using Figure 7.1 in Cormen et al. as a model, perform manually the partition process on the following list: A = [1,5,6,2,3,8,9,4,7]. You just need to specify the followings:\n", | |
| "1. The array after the process is done.\n", | |
| "2. The value of $i$ after the process is done." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "deletable": false, | |
| "nbgrader": { | |
| "checksum": "06dce98d07f8f042785a795b32e7ef75", | |
| "grade": true, | |
| "grade_id": "cell-7aa520f8af13679b", | |
| "locked": false, | |
| "points": 0, | |
| "schema_version": 1, | |
| "solution": true | |
| } | |
| }, | |
| "source": [ | |
| "" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "deletable": false, | |
| "editable": false, | |
| "nbgrader": { | |
| "checksum": "21059776e9083caf84e8abb5b6fb893e", | |
| "grade": false, | |
| "grade_id": "cell-6c0a9dfd6980c336", | |
| "locked": true, | |
| "schema_version": 1, | |
| "solution": false | |
| } | |
| }, | |
| "source": [ | |
| "## Question 2.\n", | |
| "Code up a Python implementation of `partition(A, p, r)`, closely follow the pseudo-code in Cormen et al., p.172. Your function should return the index of the pivot in the array." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 2, | |
| "metadata": { | |
| "deletable": false, | |
| "nbgrader": { | |
| "checksum": "395997ac94ed1416c67b22f7977c07a5", | |
| "grade": false, | |
| "grade_id": "cell-1ceb2600756c60ff", | |
| "locked": false, | |
| "schema_version": 1, | |
| "solution": true | |
| } | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def partition(A,p,r):\n", | |
| " \"\"\"\n", | |
| " Assume r<len(A) and p>=0\n", | |
| " \"\"\"\n", | |
| " # Determine a pivot to compare elements and define groups later on\n", | |
| " x = A[r]\n", | |
| " i = p-1\n", | |
| " \n", | |
| " # We compare all elements in the (sub)array to the pivot\n", | |
| " for j in range(p, r):\n", | |
| " # If an element is smaller than the pivot, we increment the second marker (i) and swap the elements\n", | |
| " # in the j-th and i-th positions\n", | |
| " if A[j] <= x:\n", | |
| " # Increment i and swap elements\n", | |
| " i += 1\n", | |
| " A[i], A[j] = A[j], A[i]\n", | |
| " \n", | |
| " # When we reach the end of array, we swap the pivot with the first element of the \"larger\" group\n", | |
| " A[i+1], A[r] = A[r], A[i+1]\n", | |
| " \n", | |
| " # Return the final position of the pivot in the array\n", | |
| " return(i+1)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 3, | |
| "metadata": { | |
| "deletable": false, | |
| "editable": false, | |
| "nbgrader": { | |
| "checksum": "34aa315313b6f9d8de8efe0922e5b563", | |
| "grade": true, | |
| "grade_id": "cell-a57b60117a7b82fb", | |
| "locked": true, | |
| "points": 1, | |
| "schema_version": 1, | |
| "solution": false | |
| } | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "A = [1,5,6,2,3,8,9,4,7]\n", | |
| "assert(partition(A, 0, len(A)-1)==6)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "deletable": false, | |
| "editable": false, | |
| "nbgrader": { | |
| "checksum": "3496e310776eba92a8290d114db627cd", | |
| "grade": false, | |
| "grade_id": "cell-cd490c45f6733522", | |
| "locked": true, | |
| "schema_version": 1, | |
| "solution": false | |
| } | |
| }, | |
| "source": [ | |
| "## Question 3.\n", | |
| "\n", | |
| "Code up your own Python implementation of `quicksort(A, p, r)`, using `partition(A,p,r)`." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 4, | |
| "metadata": { | |
| "deletable": false, | |
| "nbgrader": { | |
| "checksum": "7e40c51fd1bd31c790aa0dd8abde1fb7", | |
| "grade": false, | |
| "grade_id": "cell-8c39ebb8cd1aa83a", | |
| "locked": false, | |
| "schema_version": 1, | |
| "solution": true | |
| } | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def quick_sort(A,p,r):\n", | |
| " \"\"\"\n", | |
| " Inputs: \n", | |
| " A: An array to be sorted\n", | |
| " p: The index from which we want to sort (usually 0)\n", | |
| " r: The index of the last element we want to sort\n", | |
| " \n", | |
| " Quicksort recursively calls itself to partition the array into smaller subarrays\n", | |
| " of \"larger\" and \"smaller\" elements compared to their pivots of reference\n", | |
| " \"\"\"\n", | |
| " # Termination condition of the recursion is having p = r\n", | |
| " if p < r:\n", | |
| " \n", | |
| " # Call on partition to divide the array into smaller subarrays (divide step)\n", | |
| " q = partition(A,p,r)\n", | |
| " \n", | |
| " # Recursively call on quick_sort for the two groups obtained in each partition\n", | |
| " quick_sort(A,p,q-1)\n", | |
| " quick_sort(A,q+1,r)\n", | |
| " \n", | |
| " # Return the sorted array\n", | |
| " return(A)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 5, | |
| "metadata": { | |
| "deletable": false, | |
| "editable": false, | |
| "nbgrader": { | |
| "checksum": "80923d1142f0ef958a616db1105a8c1a", | |
| "grade": true, | |
| "grade_id": "cell-4f822430efd456ee", | |
| "locked": true, | |
| "points": 1, | |
| "schema_version": 1, | |
| "solution": false | |
| } | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "A = [0]\n", | |
| "assert(quick_sort(A, 0, 0) == [0])\n", | |
| "A = [3,1,2]\n", | |
| "assert(quick_sort(A, 0, 2) == [1,2,3])" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "deletable": false, | |
| "editable": false, | |
| "nbgrader": { | |
| "checksum": "741cfe874ccaef343713f81ec963360c", | |
| "grade": false, | |
| "grade_id": "cell-53941fba9302c591", | |
| "locked": true, | |
| "schema_version": 1, | |
| "solution": false | |
| } | |
| }, | |
| "source": [ | |
| "## Question 4. \n", | |
| "Explain (using experimental plots) the running time of `quick_sort` when: \n", | |
| "1. all elements of array A have the same value (e.g., [1,1,1])?\n", | |
| "2. array A contains distinct elements sorted in decreasing order (e.g., [5,4,2,1])?\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 6, | |
| "metadata": { | |
| "deletable": false, | |
| "nbgrader": { | |
| "checksum": "f5ddaf0e684d72d229df078b18f321f8", | |
| "grade": true, | |
| "grade_id": "cell-b58035dd5fa02329", | |
| "locked": false, | |
| "points": 0, | |
| "schema_version": 1, | |
| "solution": true | |
| } | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "import time\n", | |
| "import matplotlib.pyplot as plt" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 12, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "# 1. Create list for running times when all elements have the same value\n", | |
| "time_samevalues = []\n", | |
| "\n", | |
| "# 2. Create another list for running times when elements are in descending order\n", | |
| "time_descending = []\n", | |
| "\n", | |
| "for k in range(1,101): # Running loop to create 30 lists\n", | |
| " \n", | |
| " # Create a list with the same elements\n", | |
| " list_samevalues = [1 for i in range(k*10)] \n", | |
| " \n", | |
| " # Create another list with descending elements\n", | |
| " list_descending = list(range(k*10, 0, -1))\n", | |
| " \n", | |
| " # Time metering for a list of equal inputs\n", | |
| " starting_time_same = time.time()\n", | |
| " quick_sort(list_samevalues, 0, len(list_samevalues)-1)\n", | |
| " ending_time_same = time.time()\n", | |
| " time_samevalues.append(ending_time_same - starting_time_same)\n", | |
| " \n", | |
| " # Time metering for a list of descending inputs\n", | |
| " starting_time_desc = time.time()\n", | |
| " quick_sort(list_descending, 0, len(list_descending)-1)\n", | |
| " ending_time_desc = time.time()\n", | |
| " time_descending.append(ending_time_desc - starting_time_desc)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 14, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYgAAAEWCAYAAAB8LwAVAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nOydeXhV1dW435U5gZAEwgxhEKKMhiGgQhGLAlqnWhW0xbHO+KlttfZrHVs/rfXXVuuIFecBpVVBcURxRAmTzDITwhAyz8NN7vr9sc9NbpKb5CbkZmK/z3Ofe4a9z17n3HPPOmutvdcWVcVisVgsltoEtbUAFovFYmmfWAVhsVgsFp9YBWGxWCwWn1gFYbFYLBafWAVhsVgsFp9YBWGxWCwWn1gF0cEQkQ9E5PJWaut/ReTfrdFWAzL0FpEvRaRARP5fG8uSICKFIhLcSLnpIpLWWnI1hIhMEZEdjtznB+D4V4jI117rhSIy1FmOFJGlIpInIm852/4iIpkicrilZTla/P19jyVC2lqAjoiI7AV6A5VAIfAhMF9VCwPdtqqeGYjjish04BVVHeDV1v8Foq0mci2QCXTTNh60o6qpQNe2lMEbEXkBSFPVPzVQ7H7gcVV9tDVkUlXv63Mh5n/SQ1UrRGQg8FtgkKoeaQ15vBGRFZh73OdLT2v+vs4z5Neq+mlrtNdcrAXRfM5x/gxJwDjgD20sT2dlELClOcpBRDrtC1AT3nIHAZub2cbRXr9BwHZVrfBaz2qOchCDfV61NqpqP038AHuB073WHwbe91pfgXk78KxfAXztta7A9cAOIAd4AhDvssAjzr49wJm+ju1H2SHAl0AB8KnTzis+zqcLUAK4MRZRIdAPuNdTHhjsyH0lsN9p73ogGdgA5GLeVL2PexWw1Sn7EebNEUCAfwBHgDyn/mgfcr0AuIByR6bTgXDgn8BB5/NPINwpPx1IA34PHAZe9nHMYOd6ZQK7gZuc8wqp57f1dQ08ZbsDzzty5ADveMvhdYz/AbYAA4B44D3nemUDXwFBTrkRzu+bi3mon1vrWjwFLAOKMJaV97VZ6uNcdzm/aYlTJtz5XZc4be8Erql1rouBV4B8vO5hrzI9nPr5wCrgz9S9t4cB9zmyuZy2r6PmPfaCU/4k4FvnnH8Apte61x8AvnHqDgNigOeAQ8AB4C9AcGP/B+c4lUCp0/7jPs6t9u+7wjm/bzD/oY+B+Fplr3V+/0PAb2v9Xn/xWq+6J4CXa/0udwARznXPcq5FCtC7zZ91bS1AR/zg9RDB/Ok3Ao/WurEbUxDvAbFAApABzPYq6wKuwTzMbnBuQKl9bD/KrnT+LGHAVMyfuo6CqH0De227l7oPx6edm3mm82d7B+gF9Mc88E91yp+PeQCNwLgy/wR86+ybBaxxzl+cMn3rkav2H+1+4DunzZ6Yh8ufvc6hAvgr5mEY6eN41wPbgIGYB/znNF9BvA8sAuKAUK9zr7qWwF3AWqCns/6gcw1Dnc9PnGsQ6lyv/3V+r59iHkrHe12HPGAKxvKPqH1tGrtXnfUvgCed+kmYe2+G17m6nN8uqJ7r9wbwJualYjTmIV1HQdS+dr7uMcw9kwWc5bR3hrPuuVYrgFRgFOYeCsXcb8847ffCKKnrmvrfqeda1f59V2CUbCIQ6aw/VKvs644sY5xr6Xku1PhtfJx77d/lOmApEOXIPgHjVm3TZ5012ZrPOyJSgHmbPgLc08T6D6lqrhq/5+eYP6uHfar6rKpWAi8CfTG+XF/4LCsiCZi3+7tVtVxVv8a8+R0tf1bVUlX9GPMm+7qqHlHVA5i34XFOueuAB1V1qxoXw/8BSSIyCPMnjgZOwPx5t6rqIT/b/yVwv9NmBuZNdZ7Xfjdwj6qWqWqJj/oXA/9U1f2qmo15YDcZEekLnAlcr6o5qupS1S9qFpG/Y5ThaY6sYM69L8aacqnqV2qeECdh/N8POb/XZ5iXiEu8jvmuqn6jqm5VLW2GzAMxLwq/d37D9cC/qXn9VqrqO04bJbXqBwO/wNxTRaq6CXPPNZdfActUdZnT3ifAaozC8PCCqm527qHumGt+q9P+EYwlOterfFP+O/7wvKpud67Fm9T8nwLc58iyEWNNXlLnCP7hwlhnw1S1UlXXqGp+88VuGayCaD7nq2o05s3gBIzroCl49+IopmZwrGqfqhY7i/UFz+or2w/I9toGRpkdLeleyyU+1j1yDgIeFZFcEfG4UwTo7zz8Hse4vNJFZIGIdPOz/X7APq/1fc42DxmNPDz7UfM67KuvYCMMxFzfnHr2x2LcDw+qap7X9r9hLIWPRWS3iNzpLZequmvJ1t9r/Wh/P889UdDMNnpi3uRb4vqBuUcu8twjzn0yFfNQ9yXPIIwVccir/DMYS8JDU/47/tDQ/7S2fLXvxabwMsYN+4aIHBSRh0UktJnHajGsgjhKnLfGFzCuHA9FGFPRQ5/WlMnhENBdRLzlGNhA+ZbuIbQfY/rHen0iVfVbAFV9TFUnYNwHicDtfh73IOZB4SHB2eahsfM4RM3rkFBrv7+/3X7M9Y2tZ38OcDbwvIhMqRJOtUBVf6uqQ4FzgN+IyAznHAbWCsQmYFw4VdVrtdHU3+ygI3N0E9rwJgPjwmvo+jWF/Zg4kfc90kVVH6pHnv1AGSYO4CnfTVVH+dleIHrB1b4WnnuxsfuohiyONXmfqo4ETsHcO5e1sKxNxiqIluGfwBki4jE/1wMXiEiUiAwDrm5tgVR1H8Zcv1dEwkTkZMwDqT7SgR4iEtNCIjwN/EFERgGISIyIXOQsJ4vIZOcNqQgTy6j087ivA38SkZ4iEg/cjQnu+cubwP+IyAARiQPurLV/PTBXREJFZCKmq2YdHJfYB8CTIhLnlJ9Wq8wKjEvsbRGZDCAiZ4vIMBERTEyo0vl8j7kWdzjHmo75vd5o4FzSgaH+nriq7sfEbB4UkQgRGYu5N1/1s34l8F/MPRUlIiOBoxmT8wpwjojMEpFgR6bpIjLAV2Hnmn8M/D8R6SYiQSJynIic6md7TbpefnKXcy1GYTpwLHK2rwfOEpHuItIHuLUhWUTkNBEZ47jx8jEuJ3//EwHDKogWwPEvv4QJSILxi5ZjboIX8fMPGAB+CZyMCfz9BXPzlvkqqKrbMA/f3Y753lxT2XO8tzHB4jdEJB/YhPEfA3QDnsW8Ze9z5HvE13F88BeM4tuA6Ryw1tnmL89iTPkfnLr/rbX/LuA4R7b7gNcaONY8zB95GyYOVfshgONXvxJYIiITgOGYHmWFmE4ET6rqClUtB87FXKNMTCD5Mud3qY/ngJHO7/VOQyftxSWYAOtB4G1MvOYTP+sCzMe4WQ5jLOfnm1C3Bo7COg8TmM/AWAi30/Bz6TJMEH8L5jdaTE2XVEM8ClwoIjki8lhz5a7FFxiX4XLgESc2B8Zl9AMmGP0x1YrDw4OYF51cEfkdxsJYjFEOW53jNuXFJyB4ovuWYwARWQRsU9WmBtQ7LSIyGNMdMlSr++tbLA1yrNw31oLoxDiunOMcU3w25m3N3zdNi8VyjNNpR5paAGO2/hfTfS4NuEFV17WtSBaLpaNgXUwWi8Vi8Yl1MVksFovFJ53GxRQfH6+DBw9uazEsFoulQ7FmzZpMVe3pa1+nURCDBw9m9erVbS2GxWKxdChEpN7R8NbFZLFYLBafWAVhsVgsFp9YBWGxWCwWn3SaGIQvXC4XaWlplJY2OTOypYWJiIhgwIABhIa2eYJKi8XiJ51aQaSlpREdHc3gwYMxudEsbYGqkpWVRVpaGkOGDGlrcSwWi590ahdTaWkpPXr0sMqhjRERevToYS05i6WD0akVBGCVQzvB/g4WS8ej0ysIi8Vi6Qyk7M0mp6i8zvaFX+9h2UZ/Z+xtGlZBBJgHHniAUaNGMXbsWJKSkvj+++/bWqR6mT59uh1saLG0Q0pdlVyy4Due/nJXnX1Pf7GLz7YdCUi7nTpI3dasXLmS9957j7Vr1xIeHk5mZibl5XXfACwWi6Uh9mYVUeFWth0qqLE9r9jFkYIyEnsfzbTb9WMtiABy6NAh4uPjCQ8PByA+Pp5+/cxEbffffz/JycmMHj2aa6+9Fk9W3enTp3Pbbbcxbdo0RowYQUpKChdccAHDhw/nT3/6U9WxX3nlFSZNmkRSUhLXXXcdlZU1Zyf84IMPuPjii6vWV6xYwTnnmBlHb7jhBiZOnMioUaO45x7fcwd17Vp9wy1evJgrrrgCgIyMDH7xi1+QnJxMcnIy33zzDQBffPEFSUlJJCUlMW7cOAoKCnwd1mKxNIO9mUUA7Eiv+b/afsSsD+8dXadOS3DMWBD3Ld3MloP5LXrMkf26cc859c+XPnPmTO6//34SExM5/fTTmTNnDqeeaqbPnT9/PnfffTcA8+bN47333qt6gIeFhfHll1/y6KOPct5557FmzRq6d+/Occcdx2233caRI0dYtGgR33zzDaGhodx44428+uqrXHZZ9RznZ5xxBtdddx1FRUV06dKFRYsWMWfOHMC4vbp3705lZSUzZsxgw4YNjB071q9zvuWWW7jtttuYOnUqqampzJo1i61bt/LII4/wxBNPMGXKFAoLC4mIiGjWNbVYLHXZ7SiIg3mlFJS6iI4w44m2OwojMUAKwloQAaRr166sWbOGBQsW0LNnT+bMmcMLL7wAwOeff87kyZMZM2YMn332GZs3b66qd+655wIwZswYRo0aRd++fQkPD2fo0KHs37+f5cuXs2bNGpKTk0lKSmL58uXs3r27RtshISHMnj2bpUuXUlFRwfvvv895550HwJtvvsn48eMZN24cmzdvZsuWLX6f06effsr8+fNJSkri3HPPJT8/n4KCAqZMmcJvfvMbHnvsMXJzcwkJOWbePSyWgLMno6hqeXt6YdXyjvRCuoaH0C8mMC9kx8y/uKE3/UASHBzM9OnTmT59OmPGjOHFF19k7ty53HjjjaxevZqBAwdy77331hgj4HFJBQUFVS171isqKlBVLr/8ch588MEG254zZw5PPPEE3bt3Jzk5mejoaPbs2cMjjzxCSkoKcXFxXHHFFT7HJ3h3S/Xe73a7WblyJZGRkTXK33nnnfzsZz9j2bJlnHTSSXz66aeccMIJTbtYFovFJ3uziugXE8HBvFJ2pBcwYVAcYCyIYb26BqwbubUgAsiPP/7Ijh07qtbXr1/PoEGDqh648fHxFBYWsnjx4iYdd8aMGSxevJgjR0zPhezsbPbtq5uxd/r06axdu5Znn322yr2Un59Ply5diImJIT09nQ8++MBnG71792br1q243W7efvvtqu0zZ87k8ccfr3FOALt27WLMmDH8/ve/Z+LEiWzbtq1J52SxWOpnT2YRU4fHExkaXMOC2J5eGLAANRxDFkRbUFhYyM0331zlchk2bBgLFiwgNjaWa665hjFjxjB48GCSk5ObdNyRI0fyl7/8hZkzZ+J2uwkNDeWJJ55g0KBBNcoFBwdz9tln88ILL/Diiy8CcOKJJzJu3DhGjRrF0KFDmTJlis82HnroIc4++2wGDhzI6NGjKSw0N+Vjjz3GTTfdxNixY6moqGDatGk8/fTT/POf/+Tzzz8nODiYkSNHcuaZZzbjilksltrkl7rILCxnaM+uDOvVtSrukF1UTmZhWcDiD9CJ5qSeOHGi1u7Dv3XrVkaMGNFGEllqY38Pi6XpbEjL5dzHv+GZeRP4eHM6X+3IYNUfT+e73VnMXfAdL141iVMTfU4I5xciskZVJ/raZ11MFovF0o7Z4/RgGhrfhcTeXTlSUEZucXlVl9dAupisgrBYLJZ2zO6MIkRgYPeoKnfS9vRCtqcXEh0eQp9ugetSbhWExWKxtGP2ZhXRPzaSiNBgEvt4FEQB29MLGN47cD2YIMAKQkRmi8iPIrJTRO70sT9cRBY5+78XkcHO9l+KyHqvj1tEkgIpq8VisQSSglIXb67eT1PjvnsyixgS3wWAfjERdA0PYUd6ATuOFAY0QA0BVBAiEgw8AZwJjAQuEZGRtYpdDeSo6jDgH8BfAVT1VVVNUtUkYB6wV1XXB0pWi8ViCTRLfjjIHYs3sOmA/xkdVJU9GdUKQkQY1qsrK3dnkV1UHrAUGx4CaUFMAnaq6m5VLQfeAM6rVeY84EVneTEwQ+raS5cArwdQTovFYgk4qVnFAGw8kOd3nayicgrKKqoUBJigtGcsRCAD1BBYBdEf2O+1nuZs81lGVSuAPKBHrTJzqEdBiMi1IrJaRFZnZGS0iNAtTXBwMElJSYwaNYoTTzyRv//977jd7rYWq4oXXniB+fPnA/D000/z0ksvtbFEFkvnJDXbKIhNB/1XEJ4eTDUVRLTP5UAQyIFyviIntZ1vDZYRkclAsapu8tWAqi4AFoAZB9FMOQNKZGRk1WjjI0eOcOmll5KXl8d9993XxpLV5frrr29rESyWTkuVgmiCBeHJwTQ0vtpS8CiFbhEh9IoO91mvpQikBZEGDPRaHwAcrK+MiIQAMUC21/65dCL3Uq9evViwYAGPP/44qkplZSW33347ycnJjB07lmeeeQYwacKnTZtGUlISo0eP5quvvgLgww8/ZPz48Zx44onMmDEDgKKiIq666iqSk5MZN24c7777LmAsgwsuuIDZs2czfPhw7rjjjio5nn/+eRITEzn11FOr0nUD3HvvvTzyyCOASdPx+9//nkmTJpGYmFglQ3FxMRdffDFjx45lzpw5TJ482U4yZLH4wX5HQWw7VICr0j8vwu7MIkKDhX6x1V1ZPQoisXd0wKfyDaQFkQIMF5EhwAHMw/7SWmWWAJcDK4ELgc/UCfGLSBBwETCtRaT54E44vLFFDlVFnzFw5kNNqjJ06FDcbjdHjhzh3XffJSYmhpSUFMrKypgyZQozZ87kv//9L7NmzeKPf/wjlZWVFBcXk5GRwTXXXMOXX37JkCFDyM42evSBBx7gpz/9KQsXLiQ3N5dJkyZx+umnAyZP0rp16wgPD+f444/n5ptvJiQkhHvuuYc1a9YQExPDaaedxrhx43zKWlFRwapVq1i2bBn33Xcfn376KU8++SRxcXFs2LCBTZs2kZRkO5dZLI2RV+wiv7SCsQNi2JCWx/b0Akb1i2m03t7MIhK6RxESXP0u37tbOL2iwxkzoPH6R0vAFISqVojIfOAjIBhYqKqbReR+YLWqLgGeA14WkZ0Yy2Gu1yGmAWmqurv2sTs6nm5uH3/8MRs2bKhK1peXl8eOHTtITk7mqquuwuVycf7555OUlMSKFSuYNm0aQ4YMAaB79+5Vx1iyZEnVm39paSmpqamASeoXE2NuopEjR7Jv3z4yMzOZPn06PXuaoflz5sxh+/btPuW84IILAJgwYQJ79+4F4Ouvv+aWW24BYPTo0X7PI2GxHMvszzHWw5mj+7IhLY/NB/L9UhCmi2vNQLSI8PZNU4iJDA2IrN4ENFmfqi4DltXadrfXcinGSvBVdwVwUosJ08Q3/UCxe/dugoOD6dWrF6rKv/71L2bNmlWn3Jdffsn777/PvHnzuP3224mNjfVpTqoq//nPfzj++ONrbP/+++9rpAoPDg6moqICwG+z1FPfu25nyd1lsbQmnvjDT4bH88TnIWw8kMfFyQMbrON2K3uzipiWGF9nX//YSB81Wh47kroVycjI4Prrr2f+/PmICLNmzeKpp57C5XIBsH37doqKiti3bx+9evXimmuu4eqrr2bt2rWcfPLJfPHFF+zZswegysU0a9Ys/vWvf1U9uNetW9egDJMnT2bFihVkZWXhcrl46623mnQOU6dO5c033wRgy5YtbNzYwm47i6UT4lEQCT2iGNWvm189mf677gBlFW6SBsYFWrx6sem+A0xJSQlJSUm4XC5CQkKYN28ev/nNbwD49a9/zd69exk/fjyqSs+ePXnnnXdYsWIFf/vb3wgNDaVr16689NJL9OzZkwULFnDBBRfgdrvp1asXn3zyCXfddRe33norY8eORVUZPHgw7733Xr3y9O3bl3vvvZeTTz6Zvn37Mn78+DrzWTfEjTfeyOWXX87YsWMZN24cY8eOrXJjWSwW3+zPLiY2KpRuEaGM7h/Dq9/vo6LSXSO24E1ucTn/t2wr4xNiOXN0n1aWthqb7tvSJCorK3G5XERERLBr1y5mzJjB9u3bCQsLa7Su/T0sxyrznvuevBIXS+ZP5Z11B7h10Xo+unUax/fxPY7hf9/eyKKU/bx381RG9O0WUNkaSvdtLQhLkyguLua0007D5XKhqjz11FN+KQeL5VgmLaeEkc6DfnR/873xQJ5PBbEuNYfXV6Vy1ZQhAVcOjWEVhKVJREdH23EPFksTqHQraTnFzBplXEVD4rsSFRbMpgN5XDhhQI2yFZVu/vTOJnpHR3DbGYltIW4NOn2QurO40Do69newHKsczi/FVakkdI8CIDhIGNm3m88R1a+n7GfzwXzuOnskXcPb/v29UyuIiIgIsrKy7MOpjVFVsrKyiIgI3MQmFkt7xTOCemD36q6po/vHsOVQPpXu6mdTbnE5/+/jHzlpaHfOGtN2gWlv2l5FBZABAwaQlpZGe03kdywRERHBgAEDGi9osXQyqrq4OhYEGAXxwrd7+XRrepXr6R+fbCe/xMU954wKeAoNf+nUCiI0NLRq5LHFYrG0BWnZxQQJ9PMa3HbGyN6M6NuNG19dy4MXjOHEAbG88n0qv5w8qM0D0950agVhsVgsbU1qdjF9YyIJ9RrzEBMZypvXncSNr67ljsUb6NPNzBT3m3YQmPamU8cgLBaLpa3Zn1NSw73kIToilIVXJHPRhAEczi/ldzMTievSvrqMWwvCYrFYAkhqdjGnHd/T577Q4CAevnAs104byrBegZ0drjlYBWGxWCwBoqS8koyCMp8WhAcRCfjc0s3FupgsFoslQKTleLq41q8g2jNWQVgsFksAcLuVnUcKgY6rIKyLyWKxWFqQd9Yd4K53NlFQVlG1bZBVEBaLxWJ5fVUq3SJDuXLqEKLDQxgS34UeXcMbr9gOCaiLSURmi8iPIrJTRO70sT9cRBY5+78XkcFe+8aKyEoR2SwiG0XE5mmwWCzNYvXebNzuwKfcySt2sXpfDueP68dvzkjkmmlDOX1k74C3GygCpiBEJBh4AjgTGAlcIiIjaxW7GshR1WHAP4C/OnVDgFeA61V1FDAdcAVKVovF0nnZnl7AhU+v5NOt6QFva8X2I1S6lRkjOq5S8CaQFsQkYKeq7lbVcuAN4LxaZc4DXnSWFwMzxCQhmQlsUNUfAFQ1S1X9n/bMYrFYHA7mlgCwN6so4G19tu0IPbqEceKA2IC31RoEUkH0B/Z7rac523yWUdUKIA/oASQCKiIfichaEbkjgHJaLJZOTFZhOQAHc0tb9LivfLePB97fUpUtuqLSzYofM5h+fC+Cg9pHsr2jJZBBal9XqLYTsL4yIcBUIBkoBpY70+Itr1FZ5FrgWoCEhISjFthisXQ+souMgkjLKWmxY+7KKOS+pZtxVSqTh/Tg9JG9WbMvh7wSF6eP6NVi7bQ1gbQg0oCBXusDgIP1lXHiDjFAtrP9C1XNVNViYBkwvnYDqrpAVSeq6sSePX0PZbdYLMc2mUVlQLWr6WhRVe5buoWIkGCGxnfh/ve2UOqqZPm2I4QGC1OHx7dIO+2BQCqIFGC4iAwRkTBgLrCkVpklwOXO8oXAZ2rstY+AsSIS5SiOU4EtAZTVYrF0UqpcTHktoyA+2ZLOl9szuPWMRO4/bzSp2cX8+6vdLN+azuQhPYiOCG2RdtoDAXMxqWqFiMzHPOyDgYWqullE7gdWq+oS4DngZRHZibEc5jp1c0Tk7xglo8AyVX0/ULJaLJbOS1ahsSByi10UlVXQ5Sim8ix1VfLn97cwvFdXLjt5EKHBQZw5ug+PfbaT8go3vzppUEuJ3S4I6EA5VV2GcQ95b7vba7kUuKieuq9gurpaLBZLs/HEIMC4mY4mMd6zX+5mf3YJr/16ctX8Dn/82Qg+//EIADNO6BzdWz3YXEwWi6VTk1lYzqAeJtXFgaOIQ5RVVPL8t3s5fUQvThlWHWcYEBfFH88awXlJ/Ujo0TFTatSHVRAWi6VTk1VUxpj+McDRKYhPtqSTXVTu04007+TBPDp3XLOP3V6xCsJisXRaissrKHW5GdG3G8FBclQ9md5YtZ/+sZH8ZPix02PSKgiLxdJp8fRg6hkdTp9uEc0eLJeaVczXOzO5eOLATjMIzh+sgrBYLJ2WTKcHU3zXMPrHRXKgmYPlFq1OJUjg4uQBLSley7D+ddi5vPFyzcAqCIvF0mnx9GDq0SWc/rGRzYpBVFS6eWt1GtOP70XfmMiWFvHo+fwB2LAoIIe2CsJisXRaPC6mHl3D6B8byeH8UiqbmPb7s21HOFJQxtzkgY0Xbm1cJZC3H3oMC8jh7YRBFoul0+JJs9GjSzj9YiOpdCvp+aX0i61pCbjdyi///T27MwsJCQoiNFgIDhKCRMgsLKNXdDg/PaEd5ljK3m2+exwXkMNbBWGxWDotWYXlRIUFExkWTL9YM+fYwdySOgriq52ZrNydxYwTehETFUpFpVKpCgrDenXlnBP7ERLcDh0uWTvNd3erICwWi6VJZBeV06NrGAAD4oxSOJBbwsRa5d5YlUpcVChP/mo84SHBrSzlUeBREAGyINqhSrRYLJaWIbOwjO5dzHzQHquhdqA6o6CMT7ak84vxAzqWcgDI2g1d+0B489OHNIRVEBaLpdOSVVhOfBdjQUSFhRAXFVpnsNx/1qZR4VbmTmqHQejGyNoZsAA1WAVhsVg6Md4uJjBWhPdYCFVlUcp+kgfHMaxXYN7CA0rWzoC5l8CPGISITAR+AvQDSoBNwKeqmh0wqSwWi+UoUVWyiqpdTGAURGpWcdX6d7uz2ZNZxPzTAvcWHjBKcqA4s20sCBG5QkTWAn8AIoEfgSOYqUA/EZEXRcTO82mxWNol+aUVuCqVeC8Lon9sZA0X0xspqURHhHDWmL5tIeLRkRXYLq7QsAXRBZiiqj6HHopIEjAcSA2EYBaLpf1yILeE85/4htevOYlhvbq2tTg+8UwU1KOWgigoqyCvxMX3u7NYtvEQl0xKIG5OpQgAACAASURBVDKsgwWnwasHU+AsiHoVhKo+0VBFVV3f8uJYLJaOwI70AjIKyth0IK/dKgjvNBse+jtdXR/+cBuvrUpl7IBYbj09sU3kO2qyd4EEQdzggDXRaJBaRB4WkW4iEioiy0UkU0R+5c/BRWS2iPwoIjtF5E4f+8NFZJGz/3sRGexsHywiJSKy3vk83dQTs1gsgSOvxAXAkYLmZUdtDTKdNBvdu9QMUgO8+n0qZ4zozRvXnFRjf7tCFda9AoVHfO/P2gmxCRAS7nt/C+BPL6aZqpoPnA2kAYnA7Y1VEpFg4AngTGAkcImIjKxV7GogR1WHAf8A/uq1b5eqJjmf6/2Q02KxtBK5xUZBpOeXtbEk9ZNV5MnkWv0AHRLfheiIEK6aMoSnfjWhfbuW0jfDuzfBigd97w9wF1fwT0GEOt9nAa83offSJGCnqu5W1XLgDeC8WmXOA150lhcDM0Tk2Em2brF0UDwK4khB+1UQ2T4siJjIUNbfPZO7zxnZ/ud12PGR+d64GMqLa+5ThaxdAVcQ/qTaWCoi2zBdXG8UkZ6AP3Zlf2C/13oaMLm+MqpaISJ5QA9n3xARWQfkA39S1a/8aNNisbQCuSXm4Xskv21dTGtTc7jn3c24Kt0AREeEsGDeROK6hJFVVE50RAhhITXfg9u9YvCw/WMIj4GyPNi6FE6cU72vMB3KCwOWg8lDoxaEqt4JnAxMVFUXUExdS8AXvn6F2nl26ytzCEhQ1XHAb4DXRKRbnQZErhWR1SKyOiMjww+RLBZLS+CJQWS0sQXx9Ipd7M0qIqF7FAPiokjZm8Nba8x7aWZhWQ33UoeiOBvSVsHkayFuCKx7ueb+rF3mO4BdXKHhcRBTPcuqmqOqlc5ykaoedgLXoxs4dhrgPXZ9AHCwvjIiEgLEANmqWqaqWU57a4BdmNhHDVR1gapOVNWJPXseO/PEWixtTV5VDKLtLIgj+aUs33aESycnsOCyifz78olMHBTH66v2o6pmFHV7DUADlBXWv2/nclA3JM6Gcb+CvV9Vp/aGVuniCg1bEL8QkW9F5G4R+ZmITBKRaSJylYi8DLyHGUBXHynAcBEZIiJhwFxgSa0yS4DLneULgc9UVUWkpxPkRkSGYsZb7MZisbQLch0Loqi8kqKyijaR4a01aVS6lbnJ1eN1L5mUwJ7MIlbuziKrsLz99lDa9y08lAC7V/jev+MjiIqHfuMh6VLTnXXdq9X7s3ZCcDjEBHYK1HoVhKreBvwM4+65CPgzxt0zHHhGVaepakoD9SuA+cBHwFbgTVXdLCL3i8i5TrHngB4istM5tqcr7DRgg4j8gAleX29Te1gs7Yfc4nI83UnaIlDtditvpKRy0tDuDInvUrX9Z2P70i0ihNdX7SerqIwe7dXFtPNT0Ep4/3dQUV5zn7vS7B9+BgQFQbd+MOx0WP+a2QfGxdR9KAQFthdWg0FqVc0BnnU+TUZVlwHLam2722u5FKN8atf7D/Cf5rRpsVgCT16Ji4FxUaRmF3Mkv7TGQ7o1+HZXFvuzS/jdzONrbI8IDeaC8QN47ftUKtzuGmk22hX7VkJELGTtgO+egKm3Ve9LSzF5lobPrN427lfw5mXw9vUQ3hX2fwcJJwdcTJvN1WKxNAlVJa/ERWJvM4K6LSyI11NSiY0KZdaoPnX2XTIpgfJKN26lfcYgKsrgwBrz0D/hbPjiYchLq96//SOQYDjup9XbEs+E3qNh+4ewZQmERJq6AcbOKGexWJpEcXklrkpleO9oPt16pNUD1VmFZXy8+TDzThpMRGhdF8vxfaKZMCiONfty6N4eXUwH10FlmbEAJl0LT0yGD/8Av3jO7N/xsdkXGVtdJyQMbvim1UW1FoTFYmkSngD1oO5RhIUE+dXVVVX5+ZPf8OSKnUfd/pIfDuKqbHiCn0smmcB1n24RR93eUbHjE3h6KpQVVG/b9635TjgJ4gbBtN/C1iXwl57mk74JEmf6Pl4r4898EFHAbzHjEq4RkeHA8ar6XsCls1gs7Y7cYhNUjY0KpVd0uF8upv3ZJaxLzWV/djHX/GQoocHNfzf9dlcWg3tEkdi7/gl+LhjXn57R4SQPjmt2Oy3Ctvfh8EbY9B+YcIXZlvodxCdCl3izfsotpsdScZZZDw6DCZf7PFxr44+L6XlgDWawHJixC29hurlaLJZjDM8YiJjIMEdBNO5iWrXXdELMLCxn+dYjzB5dN3bgD263snpvNjNG9G6wXFCQcGpiOxgbdchJer3mRaMg3G4TYB55fnWZkDCYeGWbiNcY/qjx41T1YcAF4MwP0UHGqlsslpbG42IyFkSEXwn7Vu/NpltECH26RbAopflTyOzOLCSn2MWkwd2bfYxWo6LcJNzr0hMOrjWWRMZWKM1rlR5ILYE/CqJcRCJx0mSIyHFA+83QZbFYAkqet4LoFu5XPqZVe7OZOLg7F00cwBfbMziU53MessaPsycHgIlt7Tryh4ytUFkO0/9g3EZrX6qOPwzqPAriHuBDYKCIvAosB+4IqFQWi6Xd4snkGhsZRu9uEeSXVlDqqqy3fGZhGbszikge3J2LJgzErbB4dVqdcqWuSu5Y/AN3v7up3mOt3ptNfNewVh930SwOOu6l406DEefChkVm5HR0X4gd1Kai+Ys/yfo+AS4ArgBexyTtWxFYsSwWS3slt6ScsOAgIkKD6BltupE21JNptRN/mDQkjoQeUUwZ1oNFq/fjdlfn7swrcXH5wlW8uTqNl7/bR1pOsc9jrdqbzcRB3ekQswIcWm+yscYNMUHn0jzY9p5xL3UE+fG/m2t/IBgIA6aJyAWBE8lisbRn8opdxESFIiL0chREQ4HqVXtyCA8JYkx/069/TnICaTklLN1wkL2ZRWw+mMecZ1ayNjWHP5x5AgCL19S1MA7llZCWU0LykA4QfwBjQfQda5TBoKlGUUCHiT+Af91cFwJjgc2A29mswH8DKJfFYmmn5Ba7iI0084j1ijbjDBoKVK/el03SwNiqeRlmjuxNXFQot7xRPa19l7BgFl6RzE+G9+TrnZm8tTqNm386vMbcDSl7Tfyhzbuu+kOlywSoJ19r1oOCjBXx6b0weEqbitYU/OnmepKq1p4q1GKxHKPklbiIjTIKonc3x4KoJ1BdVFbB5oP53Di9et6CiNBgXv31SfyYnl+1bdzAOAY7cYU5yQOZ/9o6vt6ZWaOr6uq92USFBTOyb52pYdofR7aa0dJ9k6q3nXQTDEiG3qPaTq4m4o+CWCkiI1V1S8ClsVgs7Z7cEhf9Y02m/7ioMEKCpN7BcmtTc6h0K8m1uqWO7NeNkf18P+jPcCyMRSmpNRTEqj3ZjE+II+QoBtnVYf1rMHS6yZjaVLa8a3IonXxT3X2e8Q/9xlVvCwmDwVPrlm3H+HOlX8QoiR9FZIOIbBSRDYEWzGKxtE/yisurLIigIKFnA6OpU/ZkEyQwLiHW535fhIeYjKyfbEknq9AcN6/ExY/pBXUUzVFRlAnv3ADfPdX0uu5Kkz/p47ugIL3u/oPrIbxbddyhg+KPglgIzANmA+cAZzvfFovlGCS3xEWME4MAGky3sWpvNiP7dSM6ItTn/vqYkzwQV6WyeE0a5RVuUvZko9rC8Yecveb70PoGi/lk1+eQf8DM6fDDa3X3H1oPfU80sYcOjD8uplRVrT0TnMViOQYpr3BTXF5ZFaQG6Bkd4bNbalZhGetSc7l0ckKdfY2R2Dua8QmxPPjBNh78YBsAIUFCUhMskUapUhA/gGrTup6uewkiu5s5ode+DFNura5f6YLDm2DSNS0naxvhj4LYJiKvAUvxGkGtqrYXk8VyjOE9itpD727hrE3NqVP2kY+3U+lWfjm5eYPCHvrFWD7ZUu2+GdarK1FhLThDgUdBlOaZ5e5+uoOKsmDbMqMA+oyFd643I6Q9vZMytpkAtXf8oYPiz9WOxCgG7/yzfnVzFZHZwKOYMRT/VtWHau0PB14CJgBZwBxV3eu1PwHYAtyrqo/4IavFYgkgeSUmk2tMVPVEPL2iI8guKqe8wl3VlXXzwTzeSEnlylOGMKxX12a1ldg7usGMrUeNR0GAcQn5qyA2LAK3C8bNg7jB8MEdJo2GR0EcWGO+vXswdVAaVRCq2qw0gyISDDwBnIHJAJsiIktq9Ya6GshR1WEiMhf4KzDHa/8/gA+a077FYml5qtNseMUgnK6umYVl9IuNRFW5f+kW4qLCuGXG8DaR0y9y9po4QfoW42Ya9fPG66jCupeh/wTo7fT+H3MhrH8dzvyrUTQf32VSaXQfGlDxW4N6FYSI3KGqD4vIv3AS9Xmjqv/TyLEnATtVdbdzvDeA8zAWgYfzgHud5cXA4yIiqqoicj6wGyjy92QsFktgqVIQUTWD1ADp+aX0i43kg02H+X5PNg/8fDQxUU0LTrcquftg4EnmoX/Qz0D1gbVwZAuc/c/qbeMvg9ULTY+oHR+buR4ufbPDB6ihYQtiq/O9upnH7g/s91pPAybXV0ZVK0QkD+ghIiXA7zHWx++a2b7FYmlhPKm+vXsx9XZmbbt10Xpio8LYl1XECX2imZvc9OB0q1HpMmMYxg6GkHCTI8mfQPXaF8x80KO9sg31TYI+Y+DHZWZMxcUvQURM4GRvRepVEKq61FksVtW3vPeJyEV+HNvXla5tidRX5j7gH6pa2FBSLhG5FrgWICGhHd+MFksnoWo2ucjqGERi72gumTSQjIIyyiuVpIGx/G7m8TXSZLQ78vaDuk0MIbq3cRvl7YfYBp4j6Zth3atmch9vBSACZz4Me76CqbeZAXGdBH+C1H/AzCDX2LbapAHek8YOAA7WUyZNREKAGCAbY2lcKCIPA7GAW0RKVfVx78qqugBYADBx4sQ6bjCLxdIApXnm09BDsRb5JS5EIDqi+tERFhLEgxeMDYSEgSNnn/mOG2QsAjBupvquhSq8/zujGE77Y939g04xn05GQzGIM4GzgP4i8pjXrm5AhR/HTgGGi8gQ4AAwF7i0VpklwOXASuBC4DNVVeAnXnLcCxTWVg4Wi+UoWfFX+PF9uOUHv6t4BskFtWfrwB88PZjiBkNUD5BgE6geea7v8hvehNRv4ZzHIKqDZJNtARqyIA5i4g/nYuak9lAA3NbYgZ2YwnzgI0w314WqullE7gdWO4PvngNeFpGdGMthbvNOw2KxNJn8A5B/sEmDxLwzuXZocvaaWd6i+0JQMPQaUf+I6tI8+PhPpufSuHmtKmZb01AM4gfgBxF5TVVdzTm4qi4DltXadrfXcinQYDxDVe9tTtsWi6URSvPMlJiuEgiL8qtKbomrxhiIDkFJLnx6D5z6++qkfDl7IWagUQ5gAs3bPzTKUt2w8nE4YkZwk70bijLgl52jZ1JT8GccRLOUg8ViaeeU5jnfuX4riLzi8o6nIFY8CGtegG4D4NTbzbbcfca95KHvibD+FcjcAZ/cDds/gG79jesJYMZdnWJkdFNpwXHrFoulQ+FRECW5fqe7zitxMahHB5gP2sORbbDqWbO846NqBZGzF/qNry7Xzxn1vHCWUZhn/q16sp9jGKsgLJZjFW8Lwk9yvSYLaveowod3QnhXGDvHKIqiTAgKgZKcmhZE79Fme6XLDHIbfkabid2e8GfK0aXUHb+QhwlgP+PEESwWS0dC1UtB5PlVxe1WM5tcRwlS/7gMdn8Os/8KAyfBqgWw81MTkAbTxdVDWJRRDLGDIH5Y28jbDvHHgtgN9ARed9bnAOlAIvAsZq4Ii8XSkagoNQnnwLiY/KCgtAJVOkYMoqIMPvpf6HkCJF9tYgldesH2jyDUibd4WxAAw2a0upjtHX8UxDhVnea1vlREvlTVaSKyOVCCWSyWAOJtNfjpYsr1ZHLtCBbEt/8ycYZ5b0OwI+/wmbBtqUmLAXUVhKUO/vTZ6umk3QaqUnDHO6vlAZHKYrEEFm8F4acF4SuTa7skdz98+QiMOAeO+2n19sSZ5rw3vAmRcZ0mX1Ig8UdB/Bb4WkQ+F5EVwFfA7SLSBTNftcVi6Wg0w4LIcKYVbVcZWg+ug/9cA7mp1ds+/hOgMOv/apYdehoEhULGVhNrsDSKP+MglonIcOAETHK9bV6B6X/WX9NisbRbaiiIxoPUqsrTX+yiR5cwRvTtFkDBmkClC96+3szgtuszmPuqia1secfkS6qdVymiGww6GfZ8ad1LfuLvsMAJwChgLHCxiFwWOJEsFkvA8SiFkEi/XEzvrD/A6n053DH7eLqGO++Vhzea3lBtxXdPGuUw8wHjLnrhbKMw4gbDKfVMV5M423xbBeEXjSoIEXkZeASYCiQ7n4kBlstisQQSj1spNqFRF1NhWQUPLtvGiQNiuGiCk6B5/yp4eqp5c28L8tJgxUNw/Flwyny4ZjkMngoFh2D2QxAa4bte4myQoOqurpYG8acX00RgpJNl1WKxdAY8FkRsgnnYNsC/lu/gSEEZz8ybUJ3Fdf8q852W0jbdQz+801gvs51p7iPj4JeLIWcPxDcwzWmP4+CmFGtB+Ik/LqZNQJ9AC2KxWFqR0jwIDjeT5TRgQWw6kMfCb/Zw0YQBjEuIq95x6Iea363JzuWwdalJm+E92C04pGHl4CF+mClraRR/rlI8sEVEVgFlno2qWk/idIvF0u4pzTN++4jYeoPU3+zM5PqX19C9Sxh3zD6h5s62VBDrX4MuPeHkm1u/7WMMfxTEvYEWwmKxtDIeBREZC65iqCivMVXm4jVp3PmfDRzXsysLr0ymZ3R4dd3yIsjcDpHdzZwShRnQtWfryF1ZYdJlnPCzTjW1Z3vFn26uX7SGIBaLpRUpzSOjIoJ3V+fwazBupq69cLuVv3+yncc/38nUYfE8+avxdIuoNe7h8CZAIelSM2/CoR9g+OmtI/eB1UZWm0yvVag3BiEiXzvfBSKS7/UpEJH81hPRYrG0OKX5pBWHsiHTrK79cQ+FZRVc98oaHv98J3MmDmThFcl1lQNUu5XG/cpZr2cmtkCw/SOTV8l7hLQlYDQ0o9xU5zu69cSxWCytgbskl4Ol8YwamgBp8H//XUn68iIO5pZy7zkjufyUwUh905Ae+gGi4k0ivLghLRuHOLTBzHCXMNn3/h2fQMLJNk1GK+HXQDkRCRaRfiKS4Pn4WW+2iPwoIjtF5E4f+8NFZJGz/3sRGexsnyQi653PDyLy86aclMViaZiK4lzyNIrkEUMAmDYwlMLSCl68chJXTBlSv3IAoxD6nmjmse6X1HIK4oc34N8z4PnZ8N3TdQfh5R2A9I3WvdSK+DMfxM3APZgU325ns2JGVTdULxh4AjgDSANSRGSJqm7xKnY1kKOqw0RkLvBXTDrxTcBEVa0Qkb6YubGXqmpF007PYrH4IqgsnwK6kDjYDHz7n1N6ceOo0wkJbuSd0VVqchl5HtJ9T4TNb0NxNkR1b54wbjd8/gB89QgM/omxDj78PWTtMHM5eLqk7vzEfCfOal47libjTy+mW4DjVTWriceeBOxU1d0AIvIGcB7grSDOo7qX1GLgcRERVS32KhNB3QmLLBZLc3GVEqLlRHSLo2uM0/uoNLdx5QBwZAu4K4xigOrvwxtg6PT667kr4e3rID4RfvI7CHLaKi+Cd240+ZPGzYOf/d3M7Lb8XvjmUZOy+8LnTR6l7R9DzEDj2rK0Cv64mPZjZpBrKv2duh7SnG0+yzjWQR7QA0BEJjvzTWwErvdlPYjItSKyWkRWZ2RkNENEi+XYo7woB4D4+F7Vvnw/U35XuZOqFERSze31sfZF2PiWsRTenAdlhSYD68JZsOVdOOPPcO6/TNfVoCA443445zHY9Tk8fyZk74bdK8ycDg25vywtir8zyq0QkfepOVDu743U8/Ur1rYE6i2jqt8Do0RkBPCiiHxQe3pTVV0ALACYOHGitTIsFj/Yvi+N0UD/Pn3MAzk0yv95qQ9vgPCY6lQVUd0hJgEONtCTqTgblt8Pg6bCiLPNTG//Ph2KMqCy3Ez1mTizbr0Jl0PMAHjzcnhqKriKjIKwtBr+WBCpwCdAGBDt9WmMNGCg1/oA4GB9ZUQkBIgBsr0LqOpWoAgY7UebFoulEbbvM7mXhgxwDPqIWP8VxKEfoO/Ymm/xfcc2bEF89mcozYezHoaTbjA5kwoOmkF6v17uWzl4GDYDrv7I5FoK7QJDptVf1tLi+DNQ7r5mHjsFGC4iQ4ADwFzg0lpllgCXAyuBC4HPVFWdOvudIPUg4HhgbzPlsFgsXuxLM+9pMXHOxJCRsf65mCpdZpDcpGtqbu+bBNveM0ogotZcEQfXw+rnYfL10HuU2TZsBtzyg0k1Xl/WVW96j4LrvzIWR1hU4+UtLYY/vZgSgd8Bg73Lq2qDI1Wch/t84CMgGFioqptF5H5gtaouAZ4DXhaRnRjLYa5TfSpwp4i4MD2nblTVzKaenMViqYnbrRw6km5WPPGHiBi/Jg0icztUllXHHTz0c9ZTv6tpDZQXw/u/hS7xML1WL/fIOJpEVPfm95KyNBt/YhBvAU8D/wYqm3JwVV0GLKu17W6v5VLgIh/1XgZebkpbFoulcX5MLyDUVQCheCmI2EZTfgMmtTdAv3E1tw+cBNF9YfFVcPELMOx0KEiH1+eaKUEvXGisFEuHwx8FUaGqTwVcEovFEhBUlRJXJa5K5asdGUTj9CL3KIjIWEjf1PiB9q00WVR7HFdze0SMiSW8NgdevRim3Q7rX4XiLJj7GpxwVsuekKXV8EdBLBWRG4G3qdmLKbv+KhaLpT1wJL+U615Zw7rU6hjD/V3KUcKQEMf/30DK7xqkfgsJJ/nuZhrTH676ABZfDV88BF37wJXL6loblg6FPwricuf7dq9tCgxteXEsFktLseVgPle/mEJeiYtbTx9OdEQoYcHCWfuWIftjqh/0kbFQlm8GswUF+z5Y3gEzbmHyDfU3GB5tLIaNb8KQU43SsHRo/OnFNKQ1BLFYLC3HZ9vSufm1dXSLDGXx9acwsp9X76IDJRDute5xNZXm1R8ITl1pvged3HDDwSEmDbilU+BPL6bLfG1X1ZdaXhyLxXI0qCrPfb2H/1u2lVH9Ynju8on06larK6lnsiAPEU4AuSSnfgWx71sI6wq9xwRGcEu7xB8XU7LXcgQwA1gLWAVhsbQjyivc3LNkE6+v2s+Zo/vw94uTiAzz4TKqrSA8PYwaGiyX+p3prWTncj6m8MfFVGPiVxGJwXZBtVjaFbnF5dzwylpW7s7iptOO47dnHE9QUD05i0rzoJtXfMBjQdQXqC7JMUn6Rtms+8cazXkdKAaGt7QgFouleezJLOLqF1JIyynh7xefyAXjBzRcoT4Lor7R1KnfA2p6MFmOKfyJQSylOsleEDASM3jOYrG0AYfzSjmQWwIoh/PK+OM7GwkS4dVrJpM82I/RxnViEJ4gdX0K4lsICoUBE49adkvHwh8L4hGv5Qpgn6r6MezSYrG0NNvTCzj7X19TXuGu2jasV1cWXp5MQg8/8hS5SqGitJ4gdT0KYt9KM54hNPIoJLd0RPyJQXzhve5MP/pLVX01cGJZLJbaqCr3LtlMZGgwT/1yPKHBQQQHCeMSYokK89NbXJZvvr0VRGgkBIf5tiBcJSZdxsk3Hv0JWDoc9ab7FpFuIvIHEXlcRGaKYT5mfoiLW09Ei6VzsSujkPuWbsZV6W68sBfLNh7m211Z/G5mIjNG9GZaYk+mDIv3XzlAdSA6wis3kkj9o6n3fAluFySc0iRZLZ2DhuaDeBmTZnsj8GvgY0xivfNU9bxWkM1i6ZQsStnP89/sZfnWI37XKS6v4IH3tzCybzcunTyo+Y2X+rAgPOu1XUxbl8JbV0C3ATB4SvPbtHRYGnr1GKqqYwBE5N9AJpCgqgWtIpnF0klZtcekMVuUksrs0X38qvPk57s4mFfKY5eMI7i+7qv+4HEj1VYQkV6TBqnCl38z04P2nwhzXzVpNCzHHA0pCJdnQVUrRWSPVQ4Wy9FRXF7BpgN5RIeH8MX2DA7lldA3puHg70ebD7Pgy938fFx/JvrTS6khqlxMtS2IWDMhT0UZvHuTmT967Fw451H/JvWxdEoacjGdKCL5zqcAGOtZFpH81hLQYulMrN+fS4Vb+d2s43ErLF5df4dAVeXpL3Zx/StrGNmvG3edPfLoBahPQUTGQsFheOl8oxxm3A0/f9oqh2Ocei0IVa0nraPFYmkuKXtyEIHzx/Xno82HWbR6PzedNoygICGvxMWilFTKK9yEBgex6WA+S384yNlj+/LIRScSEdoCf8mGLIjCw1CSbSb4Gf2Lo2/L0uEJaGIVEZkNPIqZcvTfqvpQrf3hmJxOE4AsYI6q7hWRM4CHgDCgHLhdVT8LpKwWS2uQsjeb43tHExMZypzkgdzyxnq+3ZXFkJ5duPL5VWxPL6wqGyTwPz8dxq2nJ9afNqOplOZBUEjdMQ29ToCoeJjzSuMZWy3HDAFTECISDDwBnAGkASkiskRVt3gVuxrIUdVhIjIX+CswBxMQP0dVD4rIaMy81ja5vKVDU1HpZm1qDhdOMKkwZo3qQ0xkKI8u386+rGJKXJW89uvJJA/pXtUFtkldWP3BM4q69qQ/yb+GCVfWPx+E5ZikoRjE0TIJ2Kmqu1W1HHgDqN099jzgRWd5MTBDRERV16nqQWf7ZiDCsTYslg7LlkP5FJdXVgWaI0KD+fm4/qTszSEkSPjPDadwyrB4QoODiAoLaXnlUFkBGT/WdS95sMrBUotAupj6A/u91tOAyfWVUdUKEckDemAsCA+/ANapalmtuojItcC1AAkJCS0nucUSAFL25gCQPDiuatv1p5r5nW+Yfhy9a8/b0JKUFcLiK2Hf1zDjnsC1Y+lUBFJB+HKaalPKiMgojNtppq8GVHUBsABg4sSJtY9tsbQrUvZkMyAuska31j4xEdx7Rn+IDKByKDgMr10MhzfCz/4Ohsm7oQAAGNdJREFUyVcHri1LpyKQLqY0YKDX+gDgYH1lRCQEiAGynfUBwNvAZaq6K4ByWiwBR1VJ2ZvNpNrjGLZ/BH8bBtm7A9PwoR/g2RmQuRMuecMqB0uTCKSCSAGGi8gQEQkD5gJLapVZAlzuLF8IfKaqKiKxwPvAH1T1mwDKaLG0Cnsyi8gqKid5SC0FseNjk+to9xe+Kx4Nm9+BhbMBhSuXQeKslm/D0qkJmIvJiSnMx/RACgYWqupmEbkfWK2qS4DngJdFZCfGcpjrVJ8PDAPuEpG7nG0zVdX/5DUWSxuzIS2XF77ZS2lFJQdyS4Ga8QfApNIGSF0JE69smYZV4Yu/wooHYcAkkyqja6+WObblmCKg4yBUdRmwrNa2u72WSzEJAGvX+wvwl0DKZrEEkpLySm54ZS35JS56x0QQFhzEuSf247ieXb0KOVN5QrWiOFpcJSZVxqb/QNIv4ex/QIjtAGhpHnYGcovlKFE1/SPEa2zBU1/s4kBuCW9cexInDe3hu6JnKs8TzoZt70FeGsQ0Ml1obdyVUFlulouz4M3L4cAaOP0+mHJL3fEOFksTsArCYjkKMgrKuPHVNRSXV/LMvAkMiIsiNauYp7/YxTkn9qtfOUD1VJ6n3GwUxL6VMLaOQV0/+1PgzcugwKvvR2gUzHkZRpzT/JOyWBysgrBYmsmPhwu46oUUsorKCA0O4vwnvuXZyybw5IpdhAQJ/3vWCQ0fwDOV54BkCIs2CsNfBbHhLeNK6tbXjGvwWAqJs6HXiKM7MYvFwSoIi6UWX+/IZHjvrg0OXPtyewY3vrqWqLBg3rruFCLDgrjqhdVc/MxKXJXKHbOPbziNt/dUnkHBMHCSf3EIt9sEn798GAZNMbmToo4yBbjFUg+B7OZqsXQ4Vu3J5lfPfc/PHvua9fv/f3t3Hh9VdTZw/PdkhyRsYZOwkwiyCgRkcQVFFFv0dQFxAaUirby4V9u3bm1t5VP3alsUqSiy1yKoBYXSqsiSRFBEQFZJkCXIGiHbzPP+cW4ghAlJIENg5vl+PvNh7r3n3nsOdzLP3HPuOSfAHM3A7tx8xkz5gqZ1a/DemL50alqblIaJzL6nL91b1KVd40RGXtjqxCfKzjh2Ks8WvSFnDRzaU/Y+hXnwj5EuOHS9FW6bbcHBBJUFCGM8Pr/y5JzVNK4VR42YCIaMX8L7X5Xu2wl/mreOQwU+XhnW9Zi7hHrxMUwb1ZsPxl5EbFQ54xptXQoINPdGn2neu8T6AHJzYNJPYPW7rgH6p69AVMxJlNKYirMqJhOWtu07zM8nZ3JH35Zc19U9OTQ9PYtvth/g5Zu70rdNEne/ncmYKSvYnPMjY/qlICKszNrHjMwsfnZhK1IaBp6Gs0JTgm79HBq2hxpev4jk7q7Beuvn0O5qyM6EeY9AvjeJY+5Odwdx01vQ3qaEN6eH3UGYsPSHD9bwVfZ+7p/+JeP/u5H9hwp59qN19GxZj590PoekhFjeuesCruuazHMff8sDM74kr9DHE+99Tf2EWMb2Tz35k/uKIGs5NO91dF10DUju5u4gvn4X3rzajaHUoK17pVwOd3xgwcGcVnYHYcLOko0/8MGq7Yy5LIXv9hzij/9ay/T0LPYdKuCJn7Y/0p8hNiqS52/qQpsG8Tz70bcs37yHbfsO8/xNXUiMi67cSf1+N95S4Y+Q8y0U5EKLPsemad4bFr/kRl1t3ts1QMfXr6JSG1N5FiBMWCny+Xlq7mqS69RgTL8UYiIjaJAQy8TFmxl2QXM6NDl2rgQRYUy/VFrVT+CBGStJa1GX67pWcu6qQ3vcl/6m/5Q4cMTxAaJNP1j8InS5GX7ykvWANtXOAoQJK1PTs1i74yB/uaXbkTmeH7vmPAZ1bkzH5DIm0gEGdT6Hbi3qkBAbdUyP6XLtWgNTb4YD21zjclIKRMVBrSbuVVLrS2DsSqjb0npAmzOCBQgT0nbn5vPcR+vIL3JTeC5cs4teretxVcfGR9KICN1blP+46An7NQTy7XyYdafr3TziA9fXoTz1ynk81pjTyAKECWlvLt7CtPQskuu4L/emdWvwu8EdK3cXcDLSJ8CHD0PjTjB0KtS2KdXN2ccChAlZRT4/MzOzuKxtQyaO6HF6Tur3w8InXWPzuQPh+jcgNqHc3Yw5E9ljriZkLVqXw84D+Qzp0az8xFWh4EfXGL34JUgbCUPeseBgzmp2B2FC1rTlW2mQGEu/dqdhspx9W2HaMNi5Ggb8HnqPsYZmc9azAGFC0o79eSxat4vRl7QhOrKKbpQ3f+pmZmvQ9tj13y2B6beCrxCGzYDUK6rmfMZUs6BWMYnIQBFZJyIbROTRANtjRWS6t32ZiLT01ieJyCIRyRWRV4KZRxOaZmZk4VeqpnpJFf4zDiZdA69dCmveP7pt5RQ3RlJcbbhroQUHE1KCdgchIpHAq8AVQDaQLiJzVPWbEslGAntVNUVEhgLjgCFAHvAY0NF7GVNhfr8yPSOLvilJtEiKP7WDFebBnDGwaiZ0ugn2bHR3C5c/CXn74bPnodXFboykGnXLO5oxZ5VgVjH1BDao6iYAEZkGDAZKBojBwJPe+1nAKyIiqvoj8JmIpAQxf+Yspqq88dlmZmZkoyiCIOJ+7Bf6/GTvPcwjA8uZsKc8B3e6YJC9HPo9Bhc9CEV5MPvnsOAJl6bbcBj0HERWcugNY84CwQwQyUBWieVs4IKy0qhqkYjsB5KA3RU5gYiMAkYBNG/e/FTza84SBUV+fjN7FTMysuneoi4NE2Pxq6IKEeICRZ+UJK7s0Lj8g5Xl+xUw7RY4vBdunAQdrnXro2vA9RMhOQ1i4qH7CGuMNiErmAEi0F+NnkSaMqnqa8BrAGlpaRXez5y99h0qYPTkTJZu2sPY/qnc1z+ViIoMrw3u9mLHKvc4arHiL3dV8BVAUb4bVG/BExDfAO6cD+d0PvY4ERHQZ0zVFMiYM1gwA0Q2ULKFsClQevaV4jTZIhIF1AZOMKWWCWebcnIZOSmDbXsP8+KQ87m2MoPmFRXAhw/CF29VLH3zPq5dIaHByWXWmBAQzACRDqSKSCtgGzAUGFYqzRxgOLAEuAH4t6ranYA5zucbd/PzyV8QFSFMuesC0lpWYqrNQ3tgxu2w5VPoex+0vtTbUOqjFhnjBtKLioOG57m5oo0JY0ELEF6bwhhgPhAJTFTV1SLyWyBDVecAbwBvi8gG3J3D0OL9RWQLUAuIEZFrgQGlnoAyIUpVmZ6exfLN7may0K/8a9V2WtWPZ+KIHjSrV7PiB/thI0y5yXVku248dBla/j7GGAAkVH6wp6WlaUZGRnVnw5yiQp+fx2Z/zbT0LBrViiUmynXV6Zxchz9e34lalZmoZ+symOoFhKFToEXvIOTYmLObiGSqalqgbdaT2lQrv18p8LmhuHPzixg7dQWfb/yBey5rw4NXtK14AzS4nswS6RqRV/8T3r3bjaJ6yyxIahOkEhgTuixAmGqzZvsBRr2dQdaew0fWRUcKz93Yheu7N634gXyF8K9HIGMioC5IqA+a9XJ3DvFJVZ95Y8KABQhTLRau2cnYqStIiIvi4SvbHnna9KKUBnRqWvbMbsc5vA9mDnfTeXa9DWo3c4+rxtWGnqMgOi4o+TcmHFiAMFWmoMjP7JXbyM0rOm5byZauHfsPM+GzzXRoUosJt/egce1KfIn/sBHWf3z0iBkTYc9mGPwX6HrLKeXfGHMsCxCmSuz9sYC7J2ceefKoPFd3asyzN3ahZkwlPoLffuSm8Cw4eHRdzSS4fTa0vLCSOTbGlMcChDllG3NyufPNdLbvz+OFIV3o17ZR4IReNVKEQGJlnkZShWXjYf6voFFHuPFNqOn1g4iOh6iYU8q/MSYwCxCm0uav3sHLC9dTUOSePvp+32HioiOZelcvureoxIimh/bA3HshZ60LAsUkwr0AUNcIvWcjtLsG/uc1NwaSMSboLECEqeL+L1KJgeZUlfGfbGLcvLWkNkwgtZGbTrNLszrc2z+1ch3Ydq93Hdj2b4Nzr/R6LQugLliojyO3HCLQ7Tboc697hNUYc1pYgAhD+UU+7nork0P5Rbx5Z08SYo9+DPIKfaz+/gCBOlDOzMhmekYWgzqfw3M3diEuupyhKHLWubuE0g5+D+/fDxHRMHwuNC89yK8x5kxgASLM+P3KgzO+5JNvc4iMEEa/ncnEET2IiYpg6w+HGDkpnfW7csvc/3/7pXD/5eeeuAOb3w+LnoZPny07TYPzYNh0qNviFEpjjAkmCxBhZty8tbz/1XYevaodSfExPDzrKx6a+SW39mrB6MmZ+PzKC0O6UD8h9rh9k+Jjad+k1olPUHAIZo+Gb95z/RI6Xn98GhFo2sPaEow5w1mACDF+vzI1fSvrd+aSX+Qnv8iHIMRGCd12zmRXViG3976Vuy9ujYiw+2A+2Qte5YvVOSTVHs74EX1o3cC1LbBlMayY7LUHlMe7o9ixCnZ9AwN+D73H2GQ6xpzFLECEkIN5hdw//UsWrNlJYmwUcTGRxERGEKd5PFrwMlfoEm6IAX+MIvoHUBh9eDwSPRGAkfUPEJ3Y0x0scxJ88ADEJrpeyeAajwN94Zdsr4iu4Ya3aHd1kEtrjAk2CxBnAZ9fKfL7j3wPR0UIkRFy5Akkn1/5bvsOfj11Cev3FPL7qzpyywVNEV8h5O6Cf97tftlf/hTk7iRi6V9c7+PIaGTt++6XfsPziJ57L0y8ynU6Wz4e2vSHG/9+NEAYY8KKBYgz3OSl3/G7978h3+tzUEwEoiMiKPL76S8ZvBT9KtMkH2KARd6rWGwtGDYDzh3glpNS4MOHQf0wcBz0Gu3W10qG6be54NDjLhj4DETaR8SYcGV//WeoIp+fpz9cw98Xb+HClPr0bpN0pHbH51MKfX4KfEqPnTPot+UFdiV2IK/H7dSLBYryXEezyFjXy7j1pVC35dGD9xgJjTu5+ZdbXXR0fZvLYNQi2P0ttBt0+gprjDkjWYCoqO+WQP1UiK9fdprsTPfTPrnbMavXrsrk67Vr2NuoD4lxUcRGR1BQ5CcidwfJ2xfg8xXh8yt+hcgIISpC2LT7R8jJ5W8pSQzo0IiIQHX/O1fDlreh7SAaXT8BYirRUa1Zz8Dr66e6lzEm7AU1QIjIQOAl3JSjE1T1mVLbY4G3gO7AD8AQVd3ibfsVMBLwAWNVdX4w81omvw8+fhyWvAKJTeDmKdCk6/Hp0ifAh790AWLQ89B9OABL571DxyUP0E7yePnLa/lD0Q0oEXSSTUyIeZZGsi/gafsCRAPZ3qssPUe5qiCbP9kYU8WCFiBEJBJ4FbgC9xWXLiJzSs0rPRLYq6opIjIUGAcMEZH2uPmpOwBNgAUicq5qhZ63rDp5+93ooRsWwPm3wub/ukbca189+ny/3wfz/w+W/RVSrwR/Icwdi+5ez+e7oum94QW2RLchum13xq6ezs/O83Gw5ZU0WPQ0WrM+udfNJCqpDTGREUREQJHPzbAWIUJcdDnDSkREuaeMjDEmCIJ5B9ET2KCqmwBEZBowGCgZIAYDT3rvZwGviHs0ZzAwTVXzgc0issE73pKqzuTm1cuQf4wMuK22HiBRc/lz3C/4cNNA6vgH8Lg+Q6dZd7L13cfxI9TQPBppDrNiBvP6jhEA/CI6jsFL/kxfYGXixZz3i3eIrZEITTpS8+PHqbl+rusoNnQKCQkNjzlnFFbvZ4w5MwTzuygZyCqxnA2UHnTnSBpVLRKR/UCSt35pqX2TS59AREYBowCaN29+UpmMjo1nV81WAbflEMkndQazsUZnXK18Aq/7n2fg3sk0Lth6JN28+JEsqzWA4lmP5/MQB/Z3IDWxgJ7DniAi0qv+6TsWGrSDrUvgkkdstjNjzBktmAEiUBfa0iPAlZWmIvuiqq8BrwGkpaUdP7pcBTRN6UjTh+aWub1HwLW9j1nqBgw/Lk33wAc8d8DRx02NMeYMFsyxk7OBZiWWmwLfl5VGRKKA2sCeCu5rjDEmiIIZINKBVBFpJSIxuEbnOaXSzOHoj+8bgH+rG2d6DjBURGJFpBWQCiwPYl6NMcaUErQqJq9NYQwwH/eY60RVXS0ivwUyVHUO8AbwttcIvQcXRPDSzcA1aBcB95z2J5iMMSbMSaCJYc5GaWlpmpGRUd3ZMMaYs4qIZKpqWqBtNn+jMcaYgCxAGGOMCcgChDHGmIAsQBhjjAkoZBqpRSQH+K4Su9QHdgcpO2eycCx3OJYZwrPc4VhmOLVyt1DVBoE2hEyAqCwRySir5T6UhWO5w7HMEJ7lDscyQ/DKbVVMxhhjArIAYYwxJqBwDhCvVXcGqkk4ljscywzhWe5wLDMEqdxh2wZhjDHmxML5DsIYY8wJWIAwxhgTUFgGCBEZKCLrRGSDiDxa3fkJBhFpJiKLRGSNiKwWkXu99fVE5GMRWe/9W7e68xoMIhIpIitE5H1vuZWILPPKPd0bgj5kiEgdEZklImu9a947HK61iNzvfb6/FpGpIhIXitdaRCaKyC4R+brEuoDXV5yXve+3r0Sk28meN+wChIhEAq8CVwHtgZtFpH315iooioAHVfU8oBdwj1fOR4GFqpoKLPSWQ9G9wJoSy+OAF7xy7wUCT0R+9noJmKeq7YAuuLKH9LUWkWRgLJCmqh1x0woMJTSv9ZvAwFLryrq+V+Hm0EnFTcn815M9adgFCKAnsEFVN6lqATANGFzNeapyqrpdVb/w3h/EfWEk48o6yUs2Cbi2enIYPCLSFBgETPCWBegHzPKShFS5RaQWcDFufhVUtUBV9xEG1xo3p00Nb0bKmsB2QvBaq+onuDlzSirr+g4G3lJnKVBHRM45mfOGY4BIBrJKLGd760KWiLQEugLLgEaquh1cEAEaVl/OguZF4JeA31tOAvapapG3HGrXvDWQA/zdq1abICLxhPi1VtVtwLPAVlxg2A9kEtrXuqSyrm+VfceFY4CQAOtC9llfEUkA/gHcp6oHqjs/wSYi1wC7VDWz5OoASUPpmkcB3YC/qmpX4EdCrDopEK/OfTDQCmgCxOOqV0oLpWtdEVX2eQ/HAJENNCux3BT4vpryElQiEo0LDu+o6rve6p3Ft5vev7uqK39B0hf4qYhswVUf9sPdUdTxqiEg9K55NpCtqsu85Vm4gBHq1/pyYLOq5qhqIfAu0IfQvtYllXV9q+w7LhwDRDqQ6j3pEINr1JpTzXmqcl69+xvAGlV9vsSmOcBw7/1w4L3TnbdgUtVfqWpTVW2Ju7b/VtVbgEXADV6ykCq3qu4AskSkrbeqP24+95C+1riqpV4iUtP7vBeXO2SvdSllXd85wO3e00y9gP3FVVGVFZY9qUXkatyvykhgoqo+Xc1ZqnIiciHwKbCKo3Xxv8a1Q8wAmuP+wG5U1dKNXyFBRC4FHlLVa0SkNe6Ooh6wArhVVfOrM39VSUTOxzXKxwCbgDtwPwBD+lqLyFPAENxTeyuAn+Hq20PqWovIVOBS3LDeO4EngNkEuL5esHwF99TTIeAOVc04qfOGY4AwxhhTvnCsYjLGGFMBFiCMMcYEZAHCGGNMQBYgjDHGBGQBwhhjTEAWIEzIEpHcIByzpYgMq+Q+H4pInSo4d28ReT3A+nkisq945NoS60NuVFNzelmAMKZyWgKVChCqerU3eN6pGgjMC7D+T8BtAdaH4qim5jSyAGFCnohcKiL/KTFfwjteZyJEZIuIjBOR5d4rxVv/pojcUOIYxXcjzwAXichKEbm/1HnOEZFPvG1fi8hFJc5RX0RGe9tWishmEVnkbR8gIktE5AsRmemNnxVIf2BB6ZWquhA4WCovIT2CrTk9LECYcNEVuA83B0hr3JhNxQ6oak9c79MXyznOo8Cnqnq+qr5QatswYL6qno+bk2FlyY2q+jdvWw/ceDnPi0h94DfA5araDcgAHih9Ui9doarur1BpQ38EW3MaRJWfxJiQsFxVswFEZCWuqugzb9vUEv+W/tKvjHRgojdI4mxVXVlGupdwY0TN9UafbQ8s9m5qYoAlAfYZAHxUibyE+gi25jSwOwgTLkqOxePj2B9HGuB9Ed7fh1ddU24Drzepy8XANuBtEbm9dBoRGQG0AJ4qXgV87N2RnK+q7VU1UFvBVQRufyjLbsJnVFMTJBYgjHGDvRX/W/zrfQvQ3Xs/GIj23h8EEgMdRERa4OaieB03km63Utu7Aw/hBo8rHkBxKdC3RNtHTRE5t9R+AnSmVJXViagbZC1cRjU1QWIBwhiIFZFluHmsixueXwcuEZHlwAW4SXgAvgKKROTL0o3UuNE2V4rICuB6XFVSSWNwI4wu8hqqJ6hqDjACmCoiX+ECRrtS+3UHVmgZI2uKyKfATKC/iGSLyJXepkeAB0RkA65N4o0K/F8Yc4SN5mrCmjexUJqq7q7uvJRFRH6Dm0d9WnXnxYQXCxAmrJ0NAcKY6mIBwhhjTEDWBmGMMSYgCxDGGGMCsgBhjDEmIAsQxhhjArIAYYwxJqD/Bxxmqj/rRYXNAAAAAElFTkSuQmCC\n", | |
| "text/plain": [ | |
| "<Figure size 432x288 with 1 Axes>" | |
| ] | |
| }, | |
| "metadata": { | |
| "needs_background": "light" | |
| }, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "%matplotlib inline\n", | |
| "\n", | |
| "n = list(range(1, 101))\n", | |
| "\n", | |
| "plt.plot(n, time_samevalues, label = \"Same values\")\n", | |
| "plt.plot(n, time_descending, label = \"Descending\")\n", | |
| "\n", | |
| "plt.xlabel('Input size / 10')\n", | |
| "plt.ylabel('Running time (s)')\n", | |
| "plt.title('Running times for quicksort for different inputs')\n", | |
| "plt.legend()\n", | |
| "plt.show()" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "As the plot shows, when we have input arrays with all same values, the running time is higher than if the array is given with decreasing order of elements, which in other algorithms is a worst-case input. <br>\n", | |
| "That's the case because of the operations quicksort makes whenever it compares similar elements. Because it will keep swapping the same elements at every iteration of the partition procedure, which is not the case with a descending-order array, the computation takes measurably longer time for a the sorted list of equal elements than for the \"completely\" unsorted array of descending elements." | |
| ] | |
| } | |
| ], | |
| "metadata": { | |
| "kernelspec": { | |
| "display_name": "Python 3", | |
| "language": "python", | |
| "name": "python3" | |
| }, | |
| "language_info": { | |
| "codemirror_mode": { | |
| "name": "ipython", | |
| "version": 3 | |
| }, | |
| "file_extension": ".py", | |
| "mimetype": "text/x-python", | |
| "name": "python", | |
| "nbconvert_exporter": "python", | |
| "pygments_lexer": "ipython3", | |
| "version": "3.7.3" | |
| } | |
| }, | |
| "nbformat": 4, | |
| "nbformat_minor": 2 | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment