{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "57e5ba00b7b45ec500d2f43583946ec4",
     "grade": false,
     "grade_id": "cell-fca4677f5235e400",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "# Artificial Intelligence UE\n",
    "## Exercises 2 - Heuristic Search\n",
    "\n",
    "In this exercise you will implement two heuristic search algorithms: Greedy Best First Search and A* search. We also look at a few different heuristics to test out the algorithms. \n",
    "\n",
    "The algorithms have been explained in the lecture (VO) and we provide some additional hints for the different heuristics below. Please refer to the lecture slides (VO) for the pseudo algorithms.\n",
    "\n",
    "<div class=\"alert alert-warning\">\n",
    "\n",
    "<p><strong>Practical hints:</strong></p>\n",
    "<ul>\n",
    "\n",
    "<li>Replace the placeholders <code># YOUR CODE HERE</code>, <code>raise NotImplementedError()</code> with your code.</li>\n",
    "<li>Do not rename any of the already existing variables (this might lead to hidden tests failing / not working).</li>\n",
    "<li><code>solve()</code> should return the found solution node or <code>None</code> if no solution is found. You do not need to store the path, the function <code>node.get_action_sequence()</code> can be used to retrieve it later via backtracking.</li>\n",
    "<li>The heuristics return <code>-1</code> for now; change them so that they return the distance that they represent!</li>\n",
    "<li>Use a <code>set()</code> to store already visited nodes (when needed).</li>\n",
    "<li>Use the imported data structures <code>Queue</code>, <code>Stack</code>, and <code>PriorityQueue</code> as the fringe / frontier (choose the right datatype depending on the algorithm)</li>\n",
    "</ul>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "9f781970aadce801f4f3db209b324590",
     "grade": false,
     "grade_id": "cell-a899a3e4e7642bba",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# import stuff\n",
    "from pig_lite.problem.base import Problem, Node\n",
    "from pig_lite.datastructures.queue import Queue\n",
    "from pig_lite.datastructures.stack import Stack\n",
    "from pig_lite.datastructures.priority_queue import PriorityQueue\n",
    "from pig_lite.instance_generation.problem_factory import ProblemFactory\n",
    "\n",
    "import math\n",
    "import random\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "d39d626778c6bc4602c99d614ce15f29",
     "grade": false,
     "grade_id": "cell-e5b8421256781208",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA94AAAIcCAYAAAAAOnYgAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjUsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvWftoOwAAAAlwSFlzAAAPYQAAD2EBqD+naQAAPXlJREFUeJzt3XucVXW9N/Dv5jYDzgwc0OEmDVChIoi3LNEUDmoiot3L1EDN5zmK50nL59HSAvV0SCqPnUSsTnnJC6IeNKM8cbyXongrg7JjopiCkBxEMRRmr+ePaeY4AsNsXNvN2uv9fr3Wq/Zi7d/67bUHf3zn81u/VUiSJAkAAACgLLpUugMAAABQzRTeAAAAUEYKbwAAACgjhTcAAACUkcIbAAAAykjhDQAAAGWk8AYAAIAyUngDAABAGSm8AQAAoIwU3hARhUKhU9s999wT99xzTxQKhbj55pvL3q/HH388Dj300Ojdu3cUCoW49NJL285/zz33lNxeKe+dOnVqDB06tORzAFSbHXWMeDe9+OKLMWPGjHjiiSdSb/vkk0+OI488st2+LY1/lbR06dKYMWNGPPvssxXtx9s9++yzUSgU4qqrrqp0V3ZYl19++Ravz5au3VVXXRWFQmG7vucf/ehHMXjw4Fi/fv32d5aq1q3SHYAdwYMPPtju9UUXXRR333133HXXXe32jxw5Mh577LF3rV8nn3xyrF+/PubOnRt/93d/F0OHDo1evXrFgw8+GCNHjnzX+gGQZzvqGPFuevHFF+OCCy6IoUOHxt57751au48//nhcffXV8dBDD7Xbv6Xxr5KWLl0aF1xwQYwbN67ifXmrgQMHxoMPPhjvfe97K92VHdbll18eO++8c0ydOrXd/rSv3ZQpU+Liiy+OWbNmxQUXXJBKm1QXhTdExIc+9KF2r3fZZZfo0qXLZvvfbb/73e/i1FNPjYkTJ7bbX+l+AeTJjjpGVINvfvObccABB8T+++/fbv/Wxr/ttXHjxigUCtGtW3X907empsbP4XZK+9p169Yt/vf//t9x0UUXxTnnnBO9evVKrW2qg6nmsJ02btwY5513XgwaNCgaGhrisMMOi6eeemqz4/7zP/8zJkyYEA0NDdGrV6846KCD4s477+yw7dapTps2bYo5c+a0TWOM2Pp08UceeSSOOeaY6Nu3b9TW1sY+++wT8+bN69Rnueqqq2K33XaLmpqa2GOPPeKaa67p3EUAYIvKOUa0Wrt2bXz5y1+O4cOHR01NTTQ2NsZRRx0Vf/jDH9qOWbNmTZx++ukxePDg6NGjRwwfPjzOO++8eOONN9q1ddNNN8UHP/jB6N27d/Tq1SuGDx8eJ598ckS0jDsf+MAHIiLipJNOahuTZsyYERERzzzzTHz2s5+NQYMGRU1NTfTv3z8mTJiwzWnpL730UsyfPz9OPPHEtn0djX8RLQX5scceG3/3d38XtbW1sffee8fVV1/drt3WcfInP/lJfPnLX47BgwdHTU1NPP3001vty5w5c2LMmDFRV1cX9fX1sfvuu8dXv/rVtj596lOfioiI8ePHt/XprVOUO/M9zpgxIwqFQjz++OPx8Y9/PBoaGqJ3795xwgknxOrVq9sdO3To0Dj66KNj/vz5sddee0VtbW0MHz48/vVf/7XdcVuaLt16niVLlsRxxx0XvXv3jv79+8fJJ58cr7zySrv3r127Nk455ZTo27dv1NXVxaRJk+KZZ55p9/12ZPny5XHCCSdEY2Nj278hvvOd70SxWNysj9/+9rfjkksuiWHDhkVdXV0ceOCBsWjRom2eY/Xq1XH66afHyJEjo66uLhobG+Pv//7v4/7779/me4cOHRpLliyJe++9t+17a52xUMo0/c7+PT3++ONj3bp1MXfu3G22Sf4ovGE7ffWrX43nnnsu/u3f/i1+8IMfxH/913/F5MmTo7m5ue2Ya6+9No444ohoaGiIq6++OubNmxd9+/aNj3zkIx3+w2rSpEltUxs/+clPxoMPPrjZVMe3uvvuu+Oggw6KtWvXxhVXXBG33XZb7L333vGZz3xmmwPKVVddFSeddFLsscceccstt8T5558fF1100WZTKAHovHKOERERr776ahx88MHx/e9/P0466aS4/fbb44orrogRI0bEihUrIiJiw4YNMX78+LjmmmviS1/6UixYsCBOOOGEmDVrVnz84x9va+vBBx+Mz3zmMzF8+PCYO3duLFiwIL7+9a/Hpk2bIiJi3333jSuvvDIiIs4///y2MekLX/hCREQcddRR8eijj8asWbNi4cKFMWfOnNhnn31i7dq1HX6GX/7yl7Fx48YYP358276Oxr+nnnoqxo4dG0uWLIl//dd/jX//93+PkSNHxtSpU2PWrFmbtf+Vr3wlli9fHldccUXcfvvt0djYuMV+zJ07N04//fQ49NBDY/78+XHrrbfGWWed1Xav7qRJk+Kf//mfIyJi9uzZbX2aNGlSRJT+PX7sYx+L973vfXHzzTfHjBkz4tZbb42PfOQjsXHjxnbHPfHEE3HmmWfGWWedFfPnz4+xY8fGF7/4xfj2t7/d4XVt9YlPfCJGjBgRt9xyS5x77rlx/fXXx1lnndX258ViMSZPnhzXX399nHPOOTF//vz44Ac/uNn99luzevXqGDt2bPzyl7+Miy66KH7605/GYYcdFmeffXacccYZmx0/e/bsWLhwYVx66aVx3XXXxfr16+Ooo47a7JcBb7dmzZqIiJg+fXosWLAgrrzyyhg+fHiMGzdum2vWzJ8/P4YPHx777LNP2/c2f/78Tn2+VqV8vwMGDIjdd989FixYUNI5yIkE2MyUKVOSnXbaaYt/dvfddycRkRx11FHt9s+bNy+JiOTBBx9MkiRJ1q9fn/Tt2zeZPHlyu+Oam5uTMWPGJAcccMA2+xERybRp07Z4/rvvvrtt3+67757ss88+ycaNG9sde/TRRycDBw5Mmpubt/je5ubmZNCgQcm+++6bFIvFtvc9++yzSffu3ZOmpqZt9hEgb3aEMeLCCy9MIiJZuHDhVo+54oorkohI5s2b127/xRdfnERE8stf/jJJkiT59re/nUREsnbt2q22tXjx4iQikiuvvLLd/r/85S9JRCSXXnpph/3dktNOOy3p2bNnu/Gn1ZbGv89+9rNJTU1Nsnz58nb7J06cmPTq1aut/63fwSGHHNKpfpxxxhlJnz59Ojzmpptu2mzsTZLSvsfp06cnEZGcddZZ7Y697rrrkohIrr322rZ9TU1NSaFQSJ544ol2xx5++OFJQ0NDsn79+iRJkmTZsmWbfS+t55k1a1a7955++ulJbW1t2/VesGBBEhHJnDlz2h03c+bMJCKS6dOnd3hNzj333CQikoceeqjd/tNOOy0pFArJU0891a6Po0ePTjZt2tR23MMPP5xERHLDDTd0eJ6327RpU7Jx48ZkwoQJycc+9rFtHr/nnnsmhx566Gb7t3TtrrzyyiQikmXLliVJsn1/T48//vikf//+JX0m8kHiDdvpmGOOafd6r732ioiI5557LiIiHnjggVizZk1MmTIlNm3a1LYVi8U48sgjY/HixamsfPn000/HH/7whzj++OMjItqd66ijjooVK1ZscXpjREt68OKLL8bnPve5dlP5mpqaYuzYse+4bwB5Ve4x4he/+EWMGDEiDjvssK0ec9ddd8VOO+0Un/zkJ9vtb11kqjWta51G/ulPfzrmzZsXL7zwQqc/Z9++feO9731vfOtb34pLLrkkHn/88XbTjDvy4osvxi677NJu/OnIXXfdFRMmTIghQ4a02z916tR4/fXXN5sZ9olPfKJT7R5wwAGxdu3aOO644+K2226Lv/zlL516X8T2fY+t43WrT3/609GtW7e4++672+3fc889Y8yYMe32fe5zn4t169Z1ahG/Lf0MbtiwIVatWhUREffee2/b+d/quOOO22bbES3fx8iRI+OAAw5ot3/q1KmRJMlmM+cmTZoUXbt2bdefiP/5O9GRK664Ivbdd9+ora2Nbt26Rffu3ePOO++M3//+953q6/banu+3sbExVq1a1TZjBFopvGE79evXr93rmpqaiIj461//GhEt965FtEyV6969e7vt4osvjiRJ2qZPvROt5zn77LM3O8/pp58eEbHVf0S8/PLLEdEyNerttrQPgM4p9xixevXq2HXXXTvsw8svvxwDBgzYrLBtbGyMbt26tY0BhxxySNx6662xadOm+PznPx+77rprjBo1Km644YZtfs5CoRB33nlnfOQjH4lZs2bFvvvuG7vsskv8n//zf+LVV1/t8L1//etfo7a2dpvneOvnGThw4Gb7Bw0a1Pbnb7WlY7fkxBNPjB//+Mfx3HPPxSc+8YlobGyMD37wg7Fw4cJtvnd7vse3j6/dunWLfv36bdb/jsbmtx+7Jdv6GXz55ZejW7du0bdv33bH9e/ff5ttt76/lO9jW/3ZmksuuSROO+20+OAHPxi33HJLLFq0KBYvXhxHHnnkNt/7Tm3P91tbWxtJksSGDRvK2jeyp7qWdoQdyM477xwREd/73ve2umpmZwe3zpznK1/5Srt79t5qt9122+L+1kFw5cqVm/3ZlvYBkI53Okbssssu8ec//7nDc/Tr1y8eeuihSJKkXfHdmsa19iEi4thjj41jjz023njjjVi0aFHMnDkzPve5z8XQoUPjwAMP7PA8TU1N8aMf/SgiIv74xz/GvHnzYsaMGfHmm2/GFVdcsdX37bzzziU9fq1fv35t96+/1YsvvtjW3lt1NkmPaFk07qSTTor169fHfffdF9OnT4+jjz46/vjHP0ZTU9NW37c93+PKlStj8ODBba83bdoUL7/88maFaUdj89uP3R79+vWLTZs2xZo1a9oV350d/0v9PrbXtddeG+PGjYs5c+a027+tX+ykYXu+3zVr1kRNTU3U1dWVvX9ki8QbyuSggw6KPn36xNKlS2P//fff4tajR493fJ7ddtst3v/+98dvfvObrZ6nvr5+q+8dOHBg3HDDDZEkSdv+5557Lh544IF33DcAtuydjhETJ06MP/7xjx0uhDlhwoR47bXX4tZbb223v/XJFRMmTNjsPTU1NXHooYfGxRdfHBEtz9lu3R+x7XRyxIgRcf7558fo0aO3WVTvvvvu8fLLL29zca23fp677rqrrbB76+fp1atXKo+G2mmnnWLixIlx3nnnxZtvvhlLliyJiK1//u35Hq+77rp2r+fNmxebNm2KcePGtdu/ZMmS+M1vftNu3/XXXx/19fWx7777vuPPeuihh0ZExI033thuf2dX5J4wYUIsXbp0s+/5mmuuiUKh0G7RvHeiUCi0Xf9Wv/3tbztcdPatampqtjsZ357v95lnnomRI0du1/mobhJvKJO6urr43ve+F1OmTIk1a9bEJz/5yWhsbIzVq1fHb37zm1i9evVmv73dXt///vdj4sSJ8ZGPfCSmTp0agwcPjjVr1sTvf//7eOyxx+Kmm27a4vu6dOkSF110UXzhC1+Ij33sY3HqqafG2rVrY8aMGaaaA5TROx0jzjzzzLjxxhvj2GOPjXPPPTcOOOCA+Otf/xr33ntvHH300TF+/Pj4/Oc/H7Nnz44pU6bEs88+G6NHj45f/epX8c///M9x1FFHtd0f/vWvfz3+/Oc/x4QJE2LXXXeNtWvXxne/+93o3r17W3H23ve+N3r27BnXXXdd7LHHHlFXVxeDBg2Kv/zlL3HGGWfEpz71qXj/+98fPXr0iLvuuit++9vfxrnnntvhNRg3blwkSRIPPfRQHHHEEdu8ZtOnT4+f/exnMX78+Pj6178effv2jeuuuy4WLFgQs2bNit69e5fwDfyPU089NXr27BkHHXRQDBw4MFauXBkzZ86M3r17t93/PmrUqIiI+MEPfhD19fVRW1sbw4YNi379+pX8Pf77v/97dOvWLQ4//PBYsmRJfO1rX4sxY8Zsdq/1oEGD4phjjokZM2bEwIED49prr42FCxfGxRdfnMozoo888sg46KCD4stf/nKsW7cu9ttvv3jwwQfbfjHTpUvH+dxZZ50V11xzTUyaNCkuvPDCaGpqigULFsTll18ep512WowYMeId9zEi4uijj46LLroopk+fHoceemg89dRTceGFF8awYcM6dR/16NGjY+7cuXHjjTfG8OHDo7a2NkaPHt2pc5f697RYLMbDDz8cp5xyynZ/XqpYxZZ1gx1YZ1asvemmm9rt39LqmEmSJPfee28yadKkpG/fvkn37t2TwYMHJ5MmTdrs/VsSnVzVPEmS5De/+U3y6U9/OmlsbEy6d++eDBgwIPn7v//75Iorrtjme//t3/4tef/735/06NEjGTFiRPLjH/84mTJlilXNAbZgRxkj/vu//zv54he/mLznPe9JunfvnjQ2NiaTJk1K/vCHP7Qd8/LLLyf/8A//kAwcODDp1q1b0tTUlHzlK19JNmzY0HbMz372s2TixInJ4MGDkx49eiSNjY3JUUcdldx///3tznfDDTcku+++e9K9e/e2Va9feumlZOrUqcnuu++e7LTTTkldXV2y1157Jf/yL//SbgXrLWlubk6GDh2anH766Zv92ZbGvyRJkieffDKZPHly0rt376RHjx7JmDFjNrumW/sOtubqq69Oxo8fn/Tv3z/p0aNHMmjQoOTTn/508tvf/rbdcZdeemkybNiwpGvXrpt9l535HltXG3/00UeTyZMnJ3V1dUl9fX1y3HHHJS+99FK7czU1NSWTJk1Kbr755mTPPfdMevTokQwdOjS55JJL2h3X0armq1evbnfs21fsTpIkWbNmTXLSSSclffr0SXr16pUcfvjhyaJFi5KISL773e9u89o999xzyec+97mkX79+Sffu3ZPddtst+da3vtX2NJW39vFb3/rWZu+PTqye/sYbbyRnn312Mnjw4KS2tjbZd999k1tvvbXT/0559tlnkyOOOCKpr69PIqLtPZ1Z1bxVZ/+e3nnnnW3fMbxdIUneMr8UAADeJd/5znfiG9/4RrzwwgvRs2fPSnenrGbMmBEXXHBBrF69epv3Pw8dOjRGjRoVP/vZz96l3v2P66+/Po4//vj49a9/7QknJTrxxBPjmWeeiV//+teV7go7IFPNAQCoiGnTpsVll10Ws2fPjrPPPrvS3cmdG264IV544YUYPXp0dOnSJRYtWhTf+ta34pBDDlF0l+hPf/pT3HjjjR2uu0C+KbwBAKiI2tra+MlPftK2iBvvrvr6+pg7d2780z/9U6xfvz4GDhwYU6dOjX/6p3+qdNcyZ/ny5XHZZZfFwQcfXOmusIMy1RwAAADKyOPEAKAC7rvvvpg8eXIMGjQoCoXCZo98AgB2PDNnzoxCoRBnnnlmSe9TeANABaxfvz7GjBkTl112WaW7AgB0wuLFi+MHP/hB7LXXXiW/1z3eAFABEydOjIkTJ1a6GwBAJ7z22mtx/PHHxw9/+MPtWgeh5MK7WCzGiy++GPX19VEoFEo+IQBUUpIkbY/z6dIl3YlfSZJsNjbW1NRETU1NqufpDOM1AFlXrjF7e8bradOmxaRJk+Kwww4rb+E9e/bsmD17drz55pvxpz/9qeQTAUC1q6uri9dee63dvunTp8eMGTPetT4YrwGoJgMau8bKVc2ptlnqeD137tx47LHHYvHixdt9zpJXNX/llVeiT58+8fzzz0dDQ8N2nxgAKuGFF16IkSNHlq39t4+PnUm8C4VCzJ8/Pz760Y+m1o/W8fq5x4ZGQ50lXdJ22vMHVroLVWvOkAcr3QVgB/HCyk0x6pDlsezRpmioT2csW/dqMYbt91ynx+vnn38+9t9///jlL38ZY8aMiYiIcePGxd577x2XXnppp89b8lTz1ki+oaFB4Q1A5qxbt67t/6c5Bbv199g7yvjYNl7XdUntHyv8jx51PSrdharl5xVote61lv8eNNSnP5Z1drx+9NFHY9WqVbHffvu17Wtubo777rsvLrvssnjjjTeia9eu22zH4moA5FKhUEj93ucSJ5EBAJ3QnBSjOaUhtjkplnT8hAkT4sknn2y376STTordd989zjnnnE4V3REKbwCoiNdeey2efvrpttfLli2LJ554Ivr27Rvvec97KtgzAKBVfX19jBo1qt2+nXbaKfr167fZ/o4ovAHIpUon3o888kiMHz++7fWXvvSliIiYMmVKXHXVVan2CwCyrBhJFCOdyDutdkql8AYgl8pReJdi3LhxpqYDQCcUoxilTRDvuK136p577in5PVavAAAAgDKSeAOQS5VOvAGAzmlOkmhOaZZYWu2USuINAAAAZSTxBiCXJN4AkA0WVwOAjFJ4A0A2FCOJ5owX3qaaAwAAQBlJvAHIJYk3AGRDNUw1l3gDAABAGUm8AcgliTcAZIPHiQEAAAAdkngDkEsSbwDIhuLftrTaqgSFNwC5pPAGgGxoTvFxYmm1UypTzQEAAKCMJN4A5JLEGwCyoTlp2dJqqxIk3gAAAFBGEm8AckniDQDZYHE1AMgohTcAZEMxCtEc6YzZxZTaKZWp5gAAAFBGEm8AckniDQDZUExatrTaqgSJNwAAAJSRxBuAXJJ4A0A2NKd4j3da7ZRK4Q1ALim8ASAbqqHwNtUcAAAAykjiDUAuSbwBIBuKSSGKSUqPE0upnVJJvAEAAKCMJN4A5FaaiXeSVOj5JABQ5dzjDQAAAHRI4g1ALqV9j7f7xQGgPJqjSzSnlBk3p9JK6RTeAOSSwhsAsiFJcXG1xOJqAAAAUH0k3gDkksQbALKhGhZXU3hTsuZiEg8vWxOrXt0QjfW1ccCwvtG1i39wAgAAbInCm5Lc8bsVccHtS2PFKxva9g3sXRvTJ4+MI0cNrGDPAEoj8QaAbGhOukRzktLiahV6+qd7vOm0O363Ik679rF2RXdExMpXNsRp1z4Wd/xuRYV6BlC61sI7zQ0ASF8xClGMLiltFldjB9ZcTOKC25fGln5B1LrvgtuXRnOxQr9CAgAA2EGZak6nPLxszWZJ91slEbHilQ3x8LI1ceB7+717HQPYTqaaA0A2VMPiahJvOmXVq1svurfnOAAAgLyQeNMpjfW1qR4HUGkSbwDIhnQXV6vMrbEKbzrlgGF9Y2Dv2lj5yoYt3uddiIgBvVseLQaQBQpvAMiGlsXV0hlnLa7GDq1rl0JMnzwyImKzH9XW19Mnj/Q8bwAAgLdReNNpR44aGHNO2DcG9G4/nXxA79qYc8K+nuMNZIrHiQFANhSjSzSntBUrVAKbak5Jjhw1MA4fOSAeXrYmVr26IRrrW6aXS7oBAAC2TOFNybp2KXhkGJB57vEGgGywuBoAZJTCGwCyoZjiFPHiFpeKLj/3eAMAAEAZSbwByCWJNwBkQ3NSiOYknXE2rXZKJfEGAACAMpJ4A5BLEm8AyIbWR4Gl05Z7vAEAAKDqSLwByCWJNwBkQzHpEsWUHidW9DgxAHj3KLwBIBtMNQcAAAA6JPEGIJck3gCQDcVI7zFgxVRaKZ3EGwAAAMpI4g1ALkm8ASAbitEliillxmm1UyqFNwC5pVgGgB1fc9IlmlNa1TytdkplqjkAAACUkcQbgFwy1RwAsqEYhShGWourVWa8lngDAABAGUm8AcgliTcAZEM13OOt8AYglxTeAJANzdElmlOarJ1WO6Uy1RwAAADKSOINQC5JvAEgG4pJIYpJSourpdROqSTeAAAAUEYSbwBySeINANlQTPEe76J7vAEAAKD6SLwByCWJNwBkQzHpEsWUHgOWVjulUngDkEsKbwDIhuYoRHOkM86m1U6pTDUHAACAMpJ4A5BLEm8AyIZqmGou8QYAAIAykngDkEsSbwDIhuZI797s5lRaKZ3CG4BcUngDQDaYag4AAAB0SOINQC5JvAEgG5qTLtGcUlKdVjulkngDAABAGUm8AcgliTcAZEMShSimtLhaklI7pVJ4A5BLCm8AyAZTzQEAAIAOdTrxnj17dsyePTuamyv15LN8kJiUT5Ikle5C1fJzSxZVa+JtvH53XPme+yvdhap10vIPV7oLVcvPbfn4uS2P9S+tj4hno5gUopikM86m1U6pOp14T5s2LZYuXRqLFy8uZ38AgHfAeA0AOx73eAOQS9WaeANAtWmOLtGc0l3SabVTKoU3ALmk8AaAbMjVVHMAAACgdBJvAHJJ4g0A2VCMLlFMKTNOq51SSbwBAACgjCTeAOSWlBoAdnzNSSGaU7o3O612SiXxBgAAgDKSeAOQS+7xBoBsqIZVzRXeAOSSwhsAsiFJukQxSWeydpJSO6Uy1RwAAADKSOINQC5JvAEgG5qjEM2R0uJqKbVTKok3AAAAlJHEG4BckngDQDYUk/QWRSsmqTRTMoU3ALmk8AaAbCimuLhaWu2UylRzAAAAKCOJNwC5JPEGgGwoRiGKKS2KllY7pZJ4AwAAwBbMmTMn9tprr2hoaIiGhoY48MAD4xe/+EXJ7Ui8AcgliTcAZENzUojmlBZXK7WdXXfdNb75zW/G+973voiIuPrqq+PYY4+Nxx9/PPbcc89Ot6PwBiCXFN4AkA2VXFxt8uTJ7V5/4xvfiDlz5sSiRYsU3gAAALA169ata/e6pqYmampqOnxPc3Nz3HTTTbF+/fo48MADSzqfe7wByKXWxDvNDQBIXzEKUUxS2v62uNqQIUOid+/ebdvMmTO3ev4nn3wy6urqoqamJv7hH/4h5s+fHyNHjizpM0i8AQAAyJXnn38+Ghoa2l53lHbvtttu8cQTT8TatWvjlltuiSlTpsS9995bUvGt8AYgl9zjDQDZkKT4OLHkb+20rlLeGT169GhbXG3//fePxYsXx3e/+934/ve/3+nzmmoOAAAAnZQkSbzxxhslvUfiDUAuSbwBIBta789Oq61SfPWrX42JEyfGkCFD4tVXX425c+fGPffcE3fccUdJ7Si8AcglhTcAZEMlHyf20ksvxYknnhgrVqyI3r17x1577RV33HFHHH744SW1o/AGAACALfjRj36USjsKbwBySeINANlQyanmabG4GgAAAJSRxBuAXJJ4A0A2FFN8nFha7ZRK4Q1ALim8ASAbTDUHAAAAOiTxBiCXJN4AkA0SbwAAAKBDEm8AckniDQDZUA2Jt8IbgNxSLAPAjq8aCm9TzQEAAKCMJN4A5JKp5gCQDUmk9/ztJJVWSifxBgAAgDKSeAOQSxJvAMgG93gDAAAAHZJ4A5BLEm8AyIZqSLwV3gDkksIbALKhGgpvU80BAACgjCTeAOSSxBsAskHiDQAAAHRI4g1ALkm8ASAbkqQQSUpJdVrtlErhDUAuKbwBIBuKUYhipDTVPKV2SmWqOQAAAJSRxBuAXJJ4A0A2WFwNAAAA6JDEG4BckngDQDZYXA0AMkrhDQDZYKo5AAAA0CGJNwC5JPEGgGyohqnmEm8AAAAoI4k3ALkk8QaAbEhSvMfb4moA8C5SeANANiQRkSTptVUJppoDAABAGUm8AcgliTcAZEMxClGIlB4nllI7pZJ4AwAAQBlJvAHIJYk3AGSDx4kBAAAAHZJ4A5BLEm8AyIZiUohCSkl1Wo8lK5XCG4BcUngDQDYkSYqPE6vQ88RMNQcAAIAykngDkEsSbwDIBourAQAAAB2SeAOQW1JqANjxVUPirfAGIJdMNQeAbKiGVc1NNQcAAIAykngDkEsSbwDIBo8TAwAAADok8QYglyTeAJANLYl3WourpdJMyRTeAOSSwhsAsqEaVjU31RwAAADKSOINQC5JvAEgG5K/bWm1VQkSbwAAACgjiTcAuSTxBoBscI83AAAA0CGJNwC5JPEGgIyogpu8Fd4A5JLCGwAyIsWp5mGqOQAAAFQfiTcAuSTxBoBsSJKWLa22KkHiDQAAAGXU6cR79uzZMXv27Ghubi5nf4AMSir1q0PYDn/+859jyJAhVZt4v328Pu35A6NHXY8K96r63PfgnpXuQtU65MAlle5C1Tpp+Ycr3YWq9fTFIyvdhar0xutrIyJnjxObNm1aLF26NBYvXlzO/gDAu6K18E5z2xEYrwGoOkkh3a0CTDUHAACAMrK4GgC5VK1TzQGg2lhcDQAAAOiQxBuAXJJ4A0BGJH/b0mqrAhTeAOSSwhsAsiFXq5oDAAAApZN4A5BLEm8AyJAKTRFPi8QbAAAAykjiDUAuSbwBIBvc4w0AAAB0SOINQC5JvAEgIzxODACyS7EMAFlQ+NuWVlvvPlPNAQAAoIwk3gDkkqnmAJARVTDVXOINAAAAZSTxBiCXJN4AkBFVkHgrvAHIJYU3AGREUmjZ0mqrAkw1BwAAgDKSeAOQSxJvAMiGJGnZ0mqrEiTeAAAAUEYSbwBySeINABlhcTUAyCaFNwBkhMXVAAAAgI5IvAHIJYk3AGRDIWnZ0mqrEiTeAAAAUEYSbwBySeINABlhcTUAyCaFNwBkhMXVAAAAgI5IvAHIJYk3AGREFUw1l3gDAABAGUm8AcgliTcAZITEGwAAAOiIxBuAXJJ4A0BGVEHirfAGIJcU3gCQER4nBgAAAHRE4g1ALkm8ASAbCknLllZblSDxBgAAgDKSeAOQSxJvAMiIKlhcTeINQC61Ft5pbgBAdZk5c2Z84AMfiPr6+mhsbIyPfvSj8dRTT5XcjsIbAAAAtuDee++NadOmxaJFi2LhwoWxadOmOOKII2L9+vUltWOqOQC5ZKo5AGRDIVJcXK3E4++44452r6+88spobGyMRx99NA455JBOt6PwBgAAIFfWrVvX7nVNTU3U1NRs832vvPJKRET07du3pPOZag5Abrm/GwAyICmku0XEkCFDonfv3m3bzJkzt92NJIkvfelLcfDBB8eoUaNK+ggSbwByyVRzAMiIMqxq/vzzz0dDQ0Pb7s6k3WeccUb89re/jV/96lcln1bhDQAAQK40NDS0K7y35R//8R/jpz/9adx3332x6667lnw+hTcAuSTxBoCMqOBzvJMkiX/8x3+M+fPnxz333BPDhg3brtMqvAEAAGALpk2bFtdff33cdtttUV9fHytXroyIiN69e0fPnj073Y7CG4BckngDQDYUkhQfJ1ZiO3PmzImIiHHjxrXbf+WVV8bUqVM73Y7CGwAAALYgSdKp+BXeAOSSxBsAMqKC93inReENQC4pvAEgI6qg8O5SmdMCAABAPki8AcgliTcAZEMlF1dLi8QbAAAAykjiDUAuSbwBICOSQsuWVlsVoPAGIJcU3gCQERZXAwAAADoi8QYglyTeAJANFlcDAAAAOiTxBiCXJN4AkBFVcI+3whuAXFJ4A0BGpDjV3OJqAAAAUIUk3gDkksQbADKiCqaaS7wBAACgjCTeAOSSxBsAMkLiDQAAAHRE4g1ALkm8ASAbCimuap7a6uglUngDkEsKbwDg3WKqOQAAAJSRxBuAXJJ4A0BGWFwNAAAA6IjEG4BckngDQDZYXA0AMkyxDAAZUaGCOS2mmgMAAEAZSbwByCVTzQEgIyyuBgAAAHRE4g1ALkm8ASAbLK4GABml8AaAjDDVHAAAAOiIxBuAXJJ4A0A2VMNUc4k3AAAAlJHEG4BckngDQEZUwT3eCm8AcknhDQAZUQWFt6nmAAAAUEYSbwBySeINANlQDYurdbrwnj17dsyePTuam5vL2R8ggxQc5ZMkFRodyKy3j9fPXLp7dOteW+FeVaFDKt2B6nXle+6vdBeq1knLP1zpLkBudXqq+bRp02Lp0qWxePHicvYHAN4VrYl3mtuOwHgNQNVJUt4qwD3eAAAAUEbu8QYgl9zjDQAZUQWrmiu8AcglhTcAZEM1LK5mqjkAAACUkcQbgFySeANARlTBVHOJNwAAAJSRxBuAXJJ4A0A2VMM93gpvAHJJ4Q0AGWGqOQAAANARiTcAuSTxBoCMkHgDAAAAHZF4A5BLEm8AyIbC37a02qoEhTcAuaTwBoCMMNUcAAAA6IjEG4BckngDQDZUw3O8Jd4AAABQRhJvAHJLSg0AGeAebwAAAKAjEm8Acsk93gCQIRVKqtOi8AYglxTeAJANFlcDAAAAOiTxBiCXJN4AkBEWVwMAAAA6IvEGIJck3gCQDdVwj7fCG4BcUngDQEaYag4AAAB0ROINQC5JvAEgG6phqrnEGwAAAMpI4g1ALkm8ASAjquAeb4U3ALmk8AaAjKiCwttUcwAAACgjiTcAuSTxBoBssLgaAAAA0CGJNwC5JPEGgIxwjzcAAADQEYk3ALkk8QaAbCgkSRSSdKLqtNoplcIbgFxSeANARphqDgAAAHRE4g1ALkm8ASAbPE4MAAAA6JDEG4BckngDQEZUwT3eCm8AcknhDQDZYKo5AAAA0CGJNwC5JPEGgIyogqnmEm8AAAAoI4k3ALkk8QaAbKiGe7wV3gDkksIbADLCVHMAAACgIxJvAHJLSg0A2VCpKeJpkXgDAABAGUm8Acgl93gDQEYkScuWVlsVoPAGIJcU3gCQDdWwqrmp5gAAAFBGEm8AckniDQAZ4XFiAAAAQEck3gDkksQbALKhUGzZ0mqrEiTeAAAAUEYSbwBySeINABlRBfd4K7wByCWFNwBkg8eJAQAAAB1SeAOQS62Jd5obAFAGSZLuVqL77rsvJk+eHIMGDYpCoRC33npryW0ovAEAAGAr1q9fH2PGjInLLrtsu9twjzcAueQebwDIhnLc471u3bp2+2tqaqKmpmaL75k4cWJMnDjxHZ1X4g1ALplqDgAZkaS8RcSQIUOid+/ebdvMmTPL+hEk3gAAAOTK888/Hw0NDW2vt5Z2p0XhDUAumWoOANlQjqnmDQ0N7QrvcjPVHAAAAMpI4g1ALkm8ASAjtvMxYFttqwIU3gDkksIbALKhHFPNS/Haa6/F008/3fZ62bJl8cQTT0Tfvn3jPe95T6faUHgDAADAVjzyyCMxfvz4ttdf+tKXIiJiypQpcdVVV3WqDYU3ALkk8QaAjHjLY8BSaatE48aNi+QdTlG3uBoAAACUkcQbgFySeANANlT6Hu80SLwBAACgjCTeAOSSxBsAMqKYtGxptVUBCm8AcknhDQAZUeHF1dJgqjkAAACUkcQbgFySeANANhQixcXV0mmmZBJvAAAAKCOJNwC5JaUGgAxIkpYtrbYqQOENQC6Zag4A2eA53gAAAECHJN4A5JLEGwAywuPEAAAAgI5IvAHIJYk3AGRDIUmikNKiaGm1U6pOF96zZ8+O2bNnR3Nzczn7k3tJhX4Q4J3wc0sWVWvh/fbxutftj0S3QvcK96oKHfKhSvegan1k0N6V7kIVe7XSHahaL/7LjjEGVJtNawsRd0RE8W9bGtJqp0Sdnmo+bdq0WLp0aSxevLic/QEA3gHjNQDseEw1ByCXqjXxBoBqUw1TzS2uBgAAAGUk8QYglyTeAJARHicGAAAAdETiDUAuSbwBICOSpGVLq60KUHgDkEsKbwDIhkLSsqXVViWYag4AAABlJPEGIJck3gCQEVUw1VziDQAAAGUk8QYglyTeAJANhWLLllZblaDwBiCXFN4AkBGmmgMAAAAdkXgDkEsSbwDIiORvW1ptVYDEGwAAAMpI4g1ALkm8ASAbCkkShZTuzU6rnVIpvAHIJYU3AGSExdUAAACAjki8AcgliTcAZEQSEWk9f9viagAAAFB9JN4A5JLEGwCyweJqAJBRCm8AyIgkUlxcLZ1mSmWqOQAAAJSRxBuA3JJSA0AGeJwYAAAA0BGJNwC55B5vAMiIYkSkNcym9ViyEkm8AQAAoIwk3gDkksQbALLB48QAIKMU3gCQERZXAwAAADoi8QYglyTeAJAREm8AAACgIxJvAHJJ4g0AGVEFibfCG4BcUngDQEZ4jjcAAADQEYk3ALkk8QaAbKiG53hLvAEAAKCMJN4A5JLEGwAywuJqAOResTniuQciXnspoq5/RNPYiC5dK92rbVJ4A0BGFJOIQkoFc1HhDUDWLP1pxB3nRKx78X/2NQyKOPLiiJHHVK5fAAA7EPd4A7B9lv40Yt7n2xfdERHrVrTsX/rTyvSrk1oT7zQ3AKAMWqeap7VVgMIbgNIVm1uS7tjS4PW3fXec23IcAEDOKbwBKN1zD2yedLeTRKx7oeW4HZTEGwCyIs20W+INQFa89lK6xwEAVDGLqwFQurr+6R5XAVY1B4CM8DgxAHKpaWzL6uXrVsSWp2wVWv68aey73bNOU3gDQEYUU5wiXqHHiZlqDkDpunRteWRYRES8veD82+sjv5mJ53kDAJSbwhuA7TPymIhPXxPRMLD9/oZBLft38Od4W1wNADIiKaa7VYCp5gBsv5HHROw+qWX18tdearmnu2mspBsA4C0U3gC8M126Rgz7cKV7UTL3eANARlhcDQCySeENABlhcTUAAACgIxJvAHJJ4g0AGVEFU80l3gAAAFBGEm8AcktKDQAZkESKiXc6zZRK4Q1ALplqDgAZYao5AAAA0BGJNwC5JPEGgIwoFiOimGJb7z6JNwAAAJSRxBuAXJJ4A0BGuMcbAAAA6IjEG4BckngDQEZUQeKt8AYglxTeAJARxSRSewB30VRzAAAAqDoSbwBySeINANmQJMVIknQeA5ZWO6WSeAMAAEAZSbwByCWJNwBkRJKkd2+2xdUA4N2j8AaAjEhSXFzNc7wBAACg+ki8AcgliTcAZESxGFFIaVE0i6sBAABA9ZF4A5BLEm8AyIgquMdb4Q1ALim8ASAbkmIxkpSmmnuONwAAAFQhiTcAuSTxBoCMqIKp5hJvAAAAKCOJNwC5JPEGgIwoJhGFbCfeCm8AcknhDQAZkSQRkdZzvE01BwAAgKoj8QYglyTeAJANSTGJJKWp5onEGwAAAKqPxBuAXJJ4A0BGJMVI7x7vlNopkcQbACro8ssvj2HDhkVtbW3st99+cf/991e6SwDA27zT8VrhDUAutSbeaW6luvHGG+PMM8+M8847Lx5//PH48Ic/HBMnTozly5eX4RMDQDYlxSTVrVRpjNcKbwByaUcovC+55JI45ZRT4gtf+ELssccecemll8aQIUNizpw5ZfjEAJBRSTHdrURpjNcl3+PdugrcunXrSn0rAFTcq6++GhHpj2Ot7b293Zqamqipqdns+DfffDMeffTROPfcc9vtP+KII+KBBx54x/1pHa83xcaIyizgWtWKGzZUugtVa1OysdJdgJL5b0J5FDe8ERHpjmWbouW/Me/2eN3pwnv27Nkxe/bsePPNNyMiYsiQIZ0+CQDsaMoxjtXV1W3W7vTp02PGjBmbHfuXv/wlmpubo3///u329+/fP1auXLndfXj7eP2r+Pl2t0UHzr2t0j2oWm60IJP8N6Gs0h7LKjFed7rwnjZtWkybNi2KxWKMGDEiHn30USu4lsEHPvCBWLx4caW7UZVc2/JwXcvHtS2PJElin332icceeyy6dEn3jqskSTYbG7f02/O3evvxW2qjFMbrd4e/n+Xj2paPa1s+rm15lGvMrsR4XfJU8y5dukSPHj2id+/epb6VTujatWs0NDRUuhtVybUtD9e1fFzb8qmtrY0+ffpUtA8777xzdO3adbPflq9atWqz36pvD+N1efn7WT6ubfm4tuXj2pZPpcfstMbr7fq1wbRp07bnbXSCa1s+rm15uK7l49qWz45wbXv06BH77bdfLFy4sN3+hQsXxtixY1M5x47wOauVa1s+rm35uLbl49qWT6WvbVrjdSFpXX0FAHhX3XjjjXHiiSfGFVdcEQceeGD84Ac/iB/+8IexZMmSaGpqqnT3AIBIZ7wueao5AJCOz3zmM/Hyyy/HhRdeGCtWrIhRo0bFz3/+c0U3AOxA0hivJd4AAABQRuku5woAAAC0o/AGAACAMlJ4AwAAQBkpvAEAAKCMFN4AAABQRgpvAAAAKCOFNwAAAJSRwhsAAADKSOENAAAAZaTwBgAAgDJSeAMAAEAZKbwBAACgjLpVugNQKc3NzbFx48ZKdyNzunfvHl27dq10NwAAIDMU3uROkiSxcuXKWLt2baW7kll9+vSJAQMGRKFQqHRXAABgh6fwJndai+7Gxsbo1auX4rEESZLE66+/HqtWrYqIiIEDB1a4RwAAsONTeJMrzc3NbUV3v379Kt2dTOrZs2dERKxatSoaGxtNOwcAgG2wuBq50npPd69evSrck2xrvX7ukQcAgG1TeJNLppe/M64fAAB0nsIbAAAAykjhDQAAAGWk8IaMmzp1anz0ox9Nrb1x48bFmWeemVp7AACQd1Y1h+3QXEzi4WVrYtWrG6KxvjYOGNY3unbJ9n3PGzdujO7du1e6GwAAUHUk3lCiO363Ig6++K447oeL4otzn4jjfrgoDr74rrjjdyvKet6bb745Ro8eHT179ox+/frFYYcdFv/3//7fuPrqq+O2226LQqEQhUIh7rnnnoiIOOecc2LEiBHRq1evGD58eHzta19rtwr5jBkzYu+9944f//jHMXz48KipqYkpU6bEvffeG9/97nfb2nv22WfL+rkAAKDaSbyhBHf8bkWcdu1jkbxt/8pXNsRp1z4Wc07YN44cNTD1865YsSKOO+64mDVrVnzsYx+LV199Ne6///74/Oc/H8uXL49169bFlVdeGRERffv2jYiI+vr6uOqqq2LQoEHx5JNPxqmnnhr19fXx//7f/2tr9+mnn4558+bFLbfcEl27do2mpqb4r//6rxg1alRceOGFERGxyy67pP55AAAgTxTe0EnNxSQuuH3pZkV3REQSEYWIuOD2pXH4yAGpTztfsWJFbNq0KT7+8Y9HU1NTRESMHj06IiJ69uwZb7zxRgwYMKDde84///y2/z906ND48pe/HDfeeGO7wvvNN9+Mn/zkJ+2K6x49ekSvXr02aw8AANg+pppDJz28bE2seGXDVv88iYgVr2yIh5etSf3cY8aMiQkTJsTo0aPjU5/6VPzwhz+M//7v/+7wPTfffHMcfPDBMWDAgKirq4uvfe1rsXz58nbHNDU1SbQBAKDMFN7QSate3XrRvT3HlaJr166xcOHC+MUvfhEjR46M733ve7HbbrvFsmXLtnj8okWL4rOf/WxMnDgxfvazn8Xjjz8e5513Xrz55pvtjttpp51S7ysAANCeqebQSY31takeV6pCoRAHHXRQHHTQQfH1r389mpqaYv78+dGjR49obm5ud+yvf/3raGpqivPOO69t33PPPdep82ypPQAAYPspvKGTDhjWNwb2ro2Vr2zY4n3ehYgY0Lvl0WJpe+ihh+LOO++MI444IhobG+Ohhx6K1atXxx577BEbNmyI//iP/4innnoq+vXrF7179473ve99sXz58pg7d2584AMfiAULFsT8+fM7da6hQ4fGQw89FM8++2zU1dVF3759o0sXk2MAAGB7+dc0dFLXLoWYPnlkRLQU2W/V+nr65JFleZ53Q0ND3HfffXHUUUfFiBEj4vzzz4/vfOc7MXHixDj11FNjt912i/333z922WWX+PWvfx3HHntsnHXWWXHGGWfE3nvvHQ888EB87Wtf69S5zj777OjatWuMHDkydtlll83uCwcAAEpTSJJkS+EdVKUNGzbEsmXLYtiwYVFbu31Twu/43Yq44Pal7RZaG9i7NqZPHlmWR4ntiNK4jgAAkBemmkOJjhw1MA4fOSAeXrYmVr26IRrrW6aXlyPpBgAAsk/hDduha5dCHPjefpXuBgAAkAHu8QYAAIAyUngDAABAGSm8AQAAoIwU3gAAAFBGCm8AAAAoI4U3AAAAlJHCGwAAAMpI4Q05NmPGjNh7770r3Q0AAKhqCm8AAAAoo26V7gBkUrE54rkHIl57KaKuf0TT2IguXSvdKwAAYAck8YZSLf1pxKWjIq4+OuKWU1r+99JRLfvLKEmSmDVrVgwfPjx69uwZY8aMiZtvvjkiIu65554oFApx5513xv777x+9evWKsWPHxlNPPdWujW9+85vRv3//qK+vj1NOOSU2bNhQ1j4DAAAKbyjN0p9GzPt8xLoX2+9ft6JlfxmL7/PPPz+uvPLKmDNnTixZsiTOOuusOOGEE+Lee+9tO+a8886L73znO/HII49Et27d4uSTT277s3nz5sX06dPjG9/4RjzyyCMxcODAuPzyy8vWXwAAoEUhSZKk0p2Ad8uGDRti2bJlMWzYsKitrS3tzcXmlmT77UV3m0JEw6CIM59Mfdr5+vXrY+edd4677rorDjzwwLb9X/jCF+L111+P//W//leMHz8+/vM//zMmTJgQERE///nPY9KkSfHXv/41amtrY+zYsTFmzJiYM2dO2/s/9KEPxYYNG+KJJ54oqT/v6DoCAEDOSLyhs557oIOiOyIiiVj3QstxKVu6dGls2LAhDj/88Kirq2vbrrnmmvjTn/7Udtxee+3V9v8HDhwYERGrVq2KiIjf//737Yr2iNjsNQAAkD6Lq0FnvfZSuseVoFgsRkTEggULYvDgwe3+rKampq347t69e9v+QqHQ7r0AAEBlSLyhs+r6p3tcCUaOHBk1NTWxfPnyeN/73tduGzJkSKfa2GOPPWLRokXt9r39NQAAkD6JN3RW09iWe7jXrYiILS2N8Ld7vJvGpn7q+vr6OPvss+Oss86KYrEYBx98cKxbty4eeOCBqKuri6ampm228cUvfjGmTJkS+++/fxx88MFx3XXXxZIlS2L48OGp9xcAAPgfCm/orC5dI468uGX18ihE++K7ZVp3HPnNsj3P+6KLLorGxsaYOXNmPPPMM9GnT5/Yd99946tf/WqnppN/5jOfiT/96U9xzjnnxIYNG+ITn/hEnHbaafEf//EfZekvAADQwqrm5Eoqq3Ev/WnEHee0X2itYXBL0T3ymHQ6uoOzqjkAAHSexBtKNfKYiN0ntaxe/tpLLfd0N40tW9INAABkm8IbtkeXrhHDPlzpXgAAABlgVXMAAAAoI4U3AAAAlJHCm1yypuA74/oBAEDnKbzJle7du0dExOuvv17hnmRb6/VrvZ4AAMDWWVyNXOnatWv06dMnVq1aFRERvXr1ikKhUOFeZUeSJPH666/HqlWrok+fPtG1q5XcAQBgWzzHm9xJkiRWrlwZa9eurXRXMqtPnz4xYMAAv7QAAIBOUHiTW83NzbFx48ZKdyNzunfvLukGAIASKLwBAACgjCyuBgAAAGWk8AYAAIAyUngDAABAGSm8AQAAoIwU3gAAAFBGCm8AAAAoI4U3AAAAlNH/B3bBQseUNUS7AAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 1000x700 with 4 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# as a reminder, this way we can visualize a particular problem (here: a maze)\n",
    "factory = ProblemFactory()\n",
    "maze = factory.create_problem_from_json(json_path='boards/tiny0.json')\n",
    "maze.visualize()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-warning\">\n",
    "Now it's your turn to implement some heuristics and search algorithms - all spots that need your attention are marked with <code># YOUR CODE HERE</code>!\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "eb30ea66fa5021f4fd86c85ca69c9a62",
     "grade": false,
     "grade_id": "cell-9f2c8647014ac9bb",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Implementing Heuristics\n",
    "\n",
    "Here, you first have to implement several heuristics:\n",
    "- [Manhattan (City block) distance](https://en.wikipedia.org/wiki/Taxicab_geometry)\n",
    "- [Euclidean distance](https://en.wikipedia.org/wiki/Euclidean_distance)\n",
    "- [Chebyshev distance](https://en.wikipedia.org/wiki/Chebyshev_distance)\n",
    "\n",
    "For comparison, we also provide you with a random distance heuristic - feel free to use them for debugging your implementations if it helps! "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "859bbb736254964fe70b6c73998c7b9a",
     "grade": false,
     "grade_id": "cell-37c3f36c850cc52c",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# this is a random heuristic - it returns a random number as the distance between two nodes\n",
    "# we use it for testing - you can also use it for debbuging if you want\n",
    "def random_heuristic(current: Node, goal: Node):\n",
    "    return random.random()\n",
    "\n",
    "def cityblock_heuristic(current: Node, goal: Node):\n",
    "    (currentX, currentY) = current.state\n",
    "    (goalX, goalY) = goal.state\n",
    "    return abs(currentX - goalX) + abs(currentY - goalY)\n",
    "\n",
    "def euclidean_heuristic(current: Node, goal: Node):\n",
    "    (currentX, currentY) = current.state\n",
    "    (goalX, goalY) = goal.state\n",
    "    return math.sqrt((currentX - goalX)**2 + (currentY - goalY)**2)\n",
    "\n",
    "def chebyshev_heuristic(current: Node, goal: Node):\n",
    "    (currentX, currentY) = current.state\n",
    "    (goalX, goalY) = goal.state\n",
    "    return max(abs(currentX - goalX), abs(currentY - goalY))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Check City Block Heuristic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "b4bfd7b32d44d3bfe6f4511793e4fa2f",
     "grade": true,
     "grade_id": "cell-9bf0ab82cd12f045",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA94AAAIcCAYAAAAAOnYgAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjUsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvWftoOwAAAAlwSFlzAAAPYQAAD2EBqD+naQAAPXlJREFUeJzt3XucVXW9N/Dv5jYDzgwc0OEmDVChIoi3LNEUDmoiot3L1EDN5zmK50nL59HSAvV0SCqPnUSsTnnJC6IeNKM8cbyXongrg7JjopiCkBxEMRRmr+ePaeY4AsNsXNvN2uv9fr3Wq/Zi7d/67bUHf3zn81u/VUiSJAkAAACgLLpUugMAAABQzRTeAAAAUEYKbwAAACgjhTcAAACUkcIbAAAAykjhDQAAAGWk8AYAAIAyUngDAABAGSm8AQAAoIwU3hARhUKhU9s999wT99xzTxQKhbj55pvL3q/HH388Dj300Ojdu3cUCoW49NJL285/zz33lNxeKe+dOnVqDB06tORzAFSbHXWMeDe9+OKLMWPGjHjiiSdSb/vkk0+OI488st2+LY1/lbR06dKYMWNGPPvssxXtx9s9++yzUSgU4qqrrqp0V3ZYl19++Ravz5au3VVXXRWFQmG7vucf/ehHMXjw4Fi/fv32d5aq1q3SHYAdwYMPPtju9UUXXRR333133HXXXe32jxw5Mh577LF3rV8nn3xyrF+/PubOnRt/93d/F0OHDo1evXrFgw8+GCNHjnzX+gGQZzvqGPFuevHFF+OCCy6IoUOHxt57751au48//nhcffXV8dBDD7Xbv6Xxr5KWLl0aF1xwQYwbN67ifXmrgQMHxoMPPhjvfe97K92VHdbll18eO++8c0ydOrXd/rSv3ZQpU+Liiy+OWbNmxQUXXJBKm1QXhTdExIc+9KF2r3fZZZfo0qXLZvvfbb/73e/i1FNPjYkTJ7bbX+l+AeTJjjpGVINvfvObccABB8T+++/fbv/Wxr/ttXHjxigUCtGtW3X907empsbP4XZK+9p169Yt/vf//t9x0UUXxTnnnBO9evVKrW2qg6nmsJ02btwY5513XgwaNCgaGhrisMMOi6eeemqz4/7zP/8zJkyYEA0NDdGrV6846KCD4s477+yw7dapTps2bYo5c+a0TWOM2Pp08UceeSSOOeaY6Nu3b9TW1sY+++wT8+bN69Rnueqqq2K33XaLmpqa2GOPPeKaa67p3EUAYIvKOUa0Wrt2bXz5y1+O4cOHR01NTTQ2NsZRRx0Vf/jDH9qOWbNmTZx++ukxePDg6NGjRwwfPjzOO++8eOONN9q1ddNNN8UHP/jB6N27d/Tq1SuGDx8eJ598ckS0jDsf+MAHIiLipJNOahuTZsyYERERzzzzTHz2s5+NQYMGRU1NTfTv3z8mTJiwzWnpL730UsyfPz9OPPHEtn0djX8RLQX5scceG3/3d38XtbW1sffee8fVV1/drt3WcfInP/lJfPnLX47BgwdHTU1NPP3001vty5w5c2LMmDFRV1cX9fX1sfvuu8dXv/rVtj596lOfioiI8ePHt/XprVOUO/M9zpgxIwqFQjz++OPx8Y9/PBoaGqJ3795xwgknxOrVq9sdO3To0Dj66KNj/vz5sddee0VtbW0MHz48/vVf/7XdcVuaLt16niVLlsRxxx0XvXv3jv79+8fJJ58cr7zySrv3r127Nk455ZTo27dv1NXVxaRJk+KZZ55p9/12ZPny5XHCCSdEY2Nj278hvvOd70SxWNysj9/+9rfjkksuiWHDhkVdXV0ceOCBsWjRom2eY/Xq1XH66afHyJEjo66uLhobG+Pv//7v4/7779/me4cOHRpLliyJe++9t+17a52xUMo0/c7+PT3++ONj3bp1MXfu3G22Sf4ovGE7ffWrX43nnnsu/u3f/i1+8IMfxH/913/F5MmTo7m5ue2Ya6+9No444ohoaGiIq6++OubNmxd9+/aNj3zkIx3+w2rSpEltUxs/+clPxoMPPrjZVMe3uvvuu+Oggw6KtWvXxhVXXBG33XZb7L333vGZz3xmmwPKVVddFSeddFLsscceccstt8T5558fF1100WZTKAHovHKOERERr776ahx88MHx/e9/P0466aS4/fbb44orrogRI0bEihUrIiJiw4YNMX78+LjmmmviS1/6UixYsCBOOOGEmDVrVnz84x9va+vBBx+Mz3zmMzF8+PCYO3duLFiwIL7+9a/Hpk2bIiJi3333jSuvvDIiIs4///y2MekLX/hCREQcddRR8eijj8asWbNi4cKFMWfOnNhnn31i7dq1HX6GX/7yl7Fx48YYP358276Oxr+nnnoqxo4dG0uWLIl//dd/jX//93+PkSNHxtSpU2PWrFmbtf+Vr3wlli9fHldccUXcfvvt0djYuMV+zJ07N04//fQ49NBDY/78+XHrrbfGWWed1Xav7qRJk+Kf//mfIyJi9uzZbX2aNGlSRJT+PX7sYx+L973vfXHzzTfHjBkz4tZbb42PfOQjsXHjxnbHPfHEE3HmmWfGWWedFfPnz4+xY8fGF7/4xfj2t7/d4XVt9YlPfCJGjBgRt9xyS5x77rlx/fXXx1lnndX258ViMSZPnhzXX399nHPOOTF//vz44Ac/uNn99luzevXqGDt2bPzyl7+Miy66KH7605/GYYcdFmeffXacccYZmx0/e/bsWLhwYVx66aVx3XXXxfr16+Ooo47a7JcBb7dmzZqIiJg+fXosWLAgrrzyyhg+fHiMGzdum2vWzJ8/P4YPHx777LNP2/c2f/78Tn2+VqV8vwMGDIjdd989FixYUNI5yIkE2MyUKVOSnXbaaYt/dvfddycRkRx11FHt9s+bNy+JiOTBBx9MkiRJ1q9fn/Tt2zeZPHlyu+Oam5uTMWPGJAcccMA2+xERybRp07Z4/rvvvrtt3+67757ss88+ycaNG9sde/TRRycDBw5Mmpubt/je5ubmZNCgQcm+++6bFIvFtvc9++yzSffu3ZOmpqZt9hEgb3aEMeLCCy9MIiJZuHDhVo+54oorkohI5s2b127/xRdfnERE8stf/jJJkiT59re/nUREsnbt2q22tXjx4iQikiuvvLLd/r/85S9JRCSXXnpph/3dktNOOy3p2bNnu/Gn1ZbGv89+9rNJTU1Nsnz58nb7J06cmPTq1aut/63fwSGHHNKpfpxxxhlJnz59Ojzmpptu2mzsTZLSvsfp06cnEZGcddZZ7Y697rrrkohIrr322rZ9TU1NSaFQSJ544ol2xx5++OFJQ0NDsn79+iRJkmTZsmWbfS+t55k1a1a7955++ulJbW1t2/VesGBBEhHJnDlz2h03c+bMJCKS6dOnd3hNzj333CQikoceeqjd/tNOOy0pFArJU0891a6Po0ePTjZt2tR23MMPP5xERHLDDTd0eJ6327RpU7Jx48ZkwoQJycc+9rFtHr/nnnsmhx566Gb7t3TtrrzyyiQikmXLliVJsn1/T48//vikf//+JX0m8kHiDdvpmGOOafd6r732ioiI5557LiIiHnjggVizZk1MmTIlNm3a1LYVi8U48sgjY/HixamsfPn000/HH/7whzj++OMjItqd66ijjooVK1ZscXpjREt68OKLL8bnPve5dlP5mpqaYuzYse+4bwB5Ve4x4he/+EWMGDEiDjvssK0ec9ddd8VOO+0Un/zkJ9vtb11kqjWta51G/ulPfzrmzZsXL7zwQqc/Z9++feO9731vfOtb34pLLrkkHn/88XbTjDvy4osvxi677NJu/OnIXXfdFRMmTIghQ4a02z916tR4/fXXN5sZ9olPfKJT7R5wwAGxdu3aOO644+K2226Lv/zlL516X8T2fY+t43WrT3/609GtW7e4++672+3fc889Y8yYMe32fe5zn4t169Z1ahG/Lf0MbtiwIVatWhUREffee2/b+d/quOOO22bbES3fx8iRI+OAAw5ot3/q1KmRJMlmM+cmTZoUXbt2bdefiP/5O9GRK664Ivbdd9+ora2Nbt26Rffu3ePOO++M3//+953q6/banu+3sbExVq1a1TZjBFopvGE79evXr93rmpqaiIj461//GhEt965FtEyV6969e7vt4osvjiRJ2qZPvROt5zn77LM3O8/pp58eEbHVf0S8/PLLEdEyNerttrQPgM4p9xixevXq2HXXXTvsw8svvxwDBgzYrLBtbGyMbt26tY0BhxxySNx6662xadOm+PznPx+77rprjBo1Km644YZtfs5CoRB33nlnfOQjH4lZs2bFvvvuG7vsskv8n//zf+LVV1/t8L1//etfo7a2dpvneOvnGThw4Gb7Bw0a1Pbnb7WlY7fkxBNPjB//+Mfx3HPPxSc+8YlobGyMD37wg7Fw4cJtvnd7vse3j6/dunWLfv36bdb/jsbmtx+7Jdv6GXz55ZejW7du0bdv33bH9e/ff5ttt76/lO9jW/3ZmksuuSROO+20+OAHPxi33HJLLFq0KBYvXhxHHnnkNt/7Tm3P91tbWxtJksSGDRvK2jeyp7qWdoQdyM477xwREd/73ve2umpmZwe3zpznK1/5Srt79t5qt9122+L+1kFw5cqVm/3ZlvYBkI53Okbssssu8ec//7nDc/Tr1y8eeuihSJKkXfHdmsa19iEi4thjj41jjz023njjjVi0aFHMnDkzPve5z8XQoUPjwAMP7PA8TU1N8aMf/SgiIv74xz/GvHnzYsaMGfHmm2/GFVdcsdX37bzzziU9fq1fv35t96+/1YsvvtjW3lt1NkmPaFk07qSTTor169fHfffdF9OnT4+jjz46/vjHP0ZTU9NW37c93+PKlStj8ODBba83bdoUL7/88maFaUdj89uP3R79+vWLTZs2xZo1a9oV350d/0v9PrbXtddeG+PGjYs5c+a027+tX+ykYXu+3zVr1kRNTU3U1dWVvX9ki8QbyuSggw6KPn36xNKlS2P//fff4tajR493fJ7ddtst3v/+98dvfvObrZ6nvr5+q+8dOHBg3HDDDZEkSdv+5557Lh544IF33DcAtuydjhETJ06MP/7xjx0uhDlhwoR47bXX4tZbb223v/XJFRMmTNjsPTU1NXHooYfGxRdfHBEtz9lu3R+x7XRyxIgRcf7558fo0aO3WVTvvvvu8fLLL29zca23fp677rqrrbB76+fp1atXKo+G2mmnnWLixIlx3nnnxZtvvhlLliyJiK1//u35Hq+77rp2r+fNmxebNm2KcePGtdu/ZMmS+M1vftNu3/XXXx/19fWx7777vuPPeuihh0ZExI033thuf2dX5J4wYUIsXbp0s+/5mmuuiUKh0G7RvHeiUCi0Xf9Wv/3tbztcdPatampqtjsZ357v95lnnomRI0du1/mobhJvKJO6urr43ve+F1OmTIk1a9bEJz/5yWhsbIzVq1fHb37zm1i9evVmv73dXt///vdj4sSJ8ZGPfCSmTp0agwcPjjVr1sTvf//7eOyxx+Kmm27a4vu6dOkSF110UXzhC1+Ij33sY3HqqafG2rVrY8aMGaaaA5TROx0jzjzzzLjxxhvj2GOPjXPPPTcOOOCA+Otf/xr33ntvHH300TF+/Pj4/Oc/H7Nnz44pU6bEs88+G6NHj45f/epX8c///M9x1FFHtd0f/vWvfz3+/Oc/x4QJE2LXXXeNtWvXxne/+93o3r17W3H23ve+N3r27BnXXXdd7LHHHlFXVxeDBg2Kv/zlL3HGGWfEpz71qXj/+98fPXr0iLvuuit++9vfxrnnntvhNRg3blwkSRIPPfRQHHHEEdu8ZtOnT4+f/exnMX78+Pj6178effv2jeuuuy4WLFgQs2bNit69e5fwDfyPU089NXr27BkHHXRQDBw4MFauXBkzZ86M3r17t93/PmrUqIiI+MEPfhD19fVRW1sbw4YNi379+pX8Pf77v/97dOvWLQ4//PBYsmRJfO1rX4sxY8Zsdq/1oEGD4phjjokZM2bEwIED49prr42FCxfGxRdfnMozoo888sg46KCD4stf/nKsW7cu9ttvv3jwwQfbfjHTpUvH+dxZZ50V11xzTUyaNCkuvPDCaGpqigULFsTll18ep512WowYMeId9zEi4uijj46LLroopk+fHoceemg89dRTceGFF8awYcM6dR/16NGjY+7cuXHjjTfG8OHDo7a2NkaPHt2pc5f697RYLMbDDz8cp5xyynZ/XqpYxZZ1gx1YZ1asvemmm9rt39LqmEmSJPfee28yadKkpG/fvkn37t2TwYMHJ5MmTdrs/VsSnVzVPEmS5De/+U3y6U9/OmlsbEy6d++eDBgwIPn7v//75Iorrtjme//t3/4tef/735/06NEjGTFiRPLjH/84mTJlilXNAbZgRxkj/vu//zv54he/mLznPe9JunfvnjQ2NiaTJk1K/vCHP7Qd8/LLLyf/8A//kAwcODDp1q1b0tTUlHzlK19JNmzY0HbMz372s2TixInJ4MGDkx49eiSNjY3JUUcdldx///3tznfDDTcku+++e9K9e/e2Va9feumlZOrUqcnuu++e7LTTTkldXV2y1157Jf/yL//SbgXrLWlubk6GDh2anH766Zv92ZbGvyRJkieffDKZPHly0rt376RHjx7JmDFjNrumW/sOtubqq69Oxo8fn/Tv3z/p0aNHMmjQoOTTn/508tvf/rbdcZdeemkybNiwpGvXrpt9l535HltXG3/00UeTyZMnJ3V1dUl9fX1y3HHHJS+99FK7czU1NSWTJk1Kbr755mTPPfdMevTokQwdOjS55JJL2h3X0armq1evbnfs21fsTpIkWbNmTXLSSSclffr0SXr16pUcfvjhyaJFi5KISL773e9u89o999xzyec+97mkX79+Sffu3ZPddtst+da3vtX2NJW39vFb3/rWZu+PTqye/sYbbyRnn312Mnjw4KS2tjbZd999k1tvvbXT/0559tlnkyOOOCKpr69PIqLtPZ1Z1bxVZ/+e3nnnnW3fMbxdIUneMr8UAADeJd/5znfiG9/4RrzwwgvRs2fPSnenrGbMmBEXXHBBrF69epv3Pw8dOjRGjRoVP/vZz96l3v2P66+/Po4//vj49a9/7QknJTrxxBPjmWeeiV//+teV7go7IFPNAQCoiGnTpsVll10Ws2fPjrPPPrvS3cmdG264IV544YUYPXp0dOnSJRYtWhTf+ta34pBDDlF0l+hPf/pT3HjjjR2uu0C+KbwBAKiI2tra+MlPftK2iBvvrvr6+pg7d2780z/9U6xfvz4GDhwYU6dOjX/6p3+qdNcyZ/ny5XHZZZfFwQcfXOmusIMy1RwAAADKyOPEAKAC7rvvvpg8eXIMGjQoCoXCZo98AgB2PDNnzoxCoRBnnnlmSe9TeANABaxfvz7GjBkTl112WaW7AgB0wuLFi+MHP/hB7LXXXiW/1z3eAFABEydOjIkTJ1a6GwBAJ7z22mtx/PHHxw9/+MPtWgeh5MK7WCzGiy++GPX19VEoFEo+IQBUUpIkbY/z6dIl3YlfSZJsNjbW1NRETU1NqufpDOM1AFlXrjF7e8bradOmxaRJk+Kwww4rb+E9e/bsmD17drz55pvxpz/9qeQTAUC1q6uri9dee63dvunTp8eMGTPetT4YrwGoJgMau8bKVc2ptlnqeD137tx47LHHYvHixdt9zpJXNX/llVeiT58+8fzzz0dDQ8N2nxgAKuGFF16IkSNHlq39t4+PnUm8C4VCzJ8/Pz760Y+m1o/W8fq5x4ZGQ50lXdJ22vMHVroLVWvOkAcr3QVgB/HCyk0x6pDlsezRpmioT2csW/dqMYbt91ynx+vnn38+9t9///jlL38ZY8aMiYiIcePGxd577x2XXnppp89b8lTz1ki+oaFB4Q1A5qxbt67t/6c5Bbv199g7yvjYNl7XdUntHyv8jx51PSrdharl5xVote61lv8eNNSnP5Z1drx+9NFHY9WqVbHffvu17Wtubo777rsvLrvssnjjjTeia9eu22zH4moA5FKhUEj93ucSJ5EBAJ3QnBSjOaUhtjkplnT8hAkT4sknn2y376STTordd989zjnnnE4V3REKbwCoiNdeey2efvrpttfLli2LJ554Ivr27Rvvec97KtgzAKBVfX19jBo1qt2+nXbaKfr167fZ/o4ovAHIpUon3o888kiMHz++7fWXvvSliIiYMmVKXHXVVan2CwCyrBhJFCOdyDutdkql8AYgl8pReJdi3LhxpqYDQCcUoxilTRDvuK136p577in5PVavAAAAgDKSeAOQS5VOvAGAzmlOkmhOaZZYWu2USuINAAAAZSTxBiCXJN4AkA0WVwOAjFJ4A0A2FCOJ5owX3qaaAwAAQBlJvAHIJYk3AGRDNUw1l3gDAABAGUm8AcgliTcAZIPHiQEAAAAdkngDkEsSbwDIhuLftrTaqgSFNwC5pPAGgGxoTvFxYmm1UypTzQEAAKCMJN4A5JLEGwCyoTlp2dJqqxIk3gAAAFBGEm8AckniDQDZYHE1AMgohTcAZEMxCtEc6YzZxZTaKZWp5gAAAFBGEm8AckniDQDZUExatrTaqgSJNwAAAJSRxBuAXJJ4A0A2NKd4j3da7ZRK4Q1ALim8ASAbqqHwNtUcAAAAykjiDUAuSbwBIBuKSSGKSUqPE0upnVJJvAEAAKCMJN4A5FaaiXeSVOj5JABQ5dzjDQAAAHRI4g1ALqV9j7f7xQGgPJqjSzSnlBk3p9JK6RTeAOSSwhsAsiFJcXG1xOJqAAAAUH0k3gDkksQbALKhGhZXU3hTsuZiEg8vWxOrXt0QjfW1ccCwvtG1i39wAgAAbInCm5Lc8bsVccHtS2PFKxva9g3sXRvTJ4+MI0cNrGDPAEoj8QaAbGhOukRzktLiahV6+qd7vOm0O363Ik679rF2RXdExMpXNsRp1z4Wd/xuRYV6BlC61sI7zQ0ASF8xClGMLiltFldjB9ZcTOKC25fGln5B1LrvgtuXRnOxQr9CAgAA2EGZak6nPLxszWZJ91slEbHilQ3x8LI1ceB7+717HQPYTqaaA0A2VMPiahJvOmXVq1svurfnOAAAgLyQeNMpjfW1qR4HUGkSbwDIhnQXV6vMrbEKbzrlgGF9Y2Dv2lj5yoYt3uddiIgBvVseLQaQBQpvAMiGlsXV0hlnLa7GDq1rl0JMnzwyImKzH9XW19Mnj/Q8bwAAgLdReNNpR44aGHNO2DcG9G4/nXxA79qYc8K+nuMNZIrHiQFANhSjSzSntBUrVAKbak5Jjhw1MA4fOSAeXrYmVr26IRrrW6aXS7oBAAC2TOFNybp2KXhkGJB57vEGgGywuBoAZJTCGwCyoZjiFPHiFpeKLj/3eAMAAEAZSbwByCWJNwBkQ3NSiOYknXE2rXZKJfEGAACAMpJ4A5BLEm8AyIbWR4Gl05Z7vAEAAKDqSLwByCWJNwBkQzHpEsWUHidW9DgxAHj3KLwBIBtMNQcAAAA6JPEGIJck3gCQDcVI7zFgxVRaKZ3EGwAAAMpI4g1ALkm8ASAbitEliillxmm1UyqFNwC5pVgGgB1fc9IlmlNa1TytdkplqjkAAACUkcQbgFwy1RwAsqEYhShGWourVWa8lngDAABAGUm8AcgliTcAZEM13OOt8AYglxTeAJANzdElmlOarJ1WO6Uy1RwAAADKSOINQC5JvAEgG4pJIYpJSourpdROqSTeAAAAUEYSbwBySeINANlQTPEe76J7vAEAAKD6SLwByCWJNwBkQzHpEsWUHgOWVjulUngDkEsKbwDIhuYoRHOkM86m1U6pTDUHAACAMpJ4A5BLEm8AyIZqmGou8QYAAIAykngDkEsSbwDIhuZI797s5lRaKZ3CG4BcUngDQDaYag4AAAB0SOINQC5JvAEgG5qTLtGcUlKdVjulkngDAABAGUm8AcgliTcAZEMShSimtLhaklI7pVJ4A5BLCm8AyAZTzQEAAIAOdTrxnj17dsyePTuamyv15LN8kJiUT5Ikle5C1fJzSxZVa+JtvH53XPme+yvdhap10vIPV7oLVcvPbfn4uS2P9S+tj4hno5gUopikM86m1U6pOp14T5s2LZYuXRqLFy8uZ38AgHfAeA0AOx73eAOQS9WaeANAtWmOLtGc0l3SabVTKoU3ALmk8AaAbMjVVHMAAACgdBJvAHJJ4g0A2VCMLlFMKTNOq51SSbwBAACgjCTeAOSWlBoAdnzNSSGaU7o3O612SiXxBgAAgDKSeAOQS+7xBoBsqIZVzRXeAOSSwhsAsiFJukQxSWeydpJSO6Uy1RwAAADKSOINQC5JvAEgG5qjEM2R0uJqKbVTKok3AAAAlJHEG4BckngDQDYUk/QWRSsmqTRTMoU3ALmk8AaAbCimuLhaWu2UylRzAAAAKCOJNwC5JPEGgGwoRiGKKS2KllY7pZJ4AwAAwBbMmTMn9tprr2hoaIiGhoY48MAD4xe/+EXJ7Ui8AcgliTcAZENzUojmlBZXK7WdXXfdNb75zW/G+973voiIuPrqq+PYY4+Nxx9/PPbcc89Ot6PwBiCXFN4AkA2VXFxt8uTJ7V5/4xvfiDlz5sSiRYsU3gAAALA169ata/e6pqYmampqOnxPc3Nz3HTTTbF+/fo48MADSzqfe7wByKXWxDvNDQBIXzEKUUxS2v62uNqQIUOid+/ebdvMmTO3ev4nn3wy6urqoqamJv7hH/4h5s+fHyNHjizpM0i8AQAAyJXnn38+Ghoa2l53lHbvtttu8cQTT8TatWvjlltuiSlTpsS9995bUvGt8AYgl9zjDQDZkKT4OLHkb+20rlLeGT169GhbXG3//fePxYsXx3e/+934/ve/3+nzmmoOAAAAnZQkSbzxxhslvUfiDUAuSbwBIBta789Oq61SfPWrX42JEyfGkCFD4tVXX425c+fGPffcE3fccUdJ7Si8AcglhTcAZEMlHyf20ksvxYknnhgrVqyI3r17x1577RV33HFHHH744SW1o/AGAACALfjRj36USjsKbwBySeINANlQyanmabG4GgAAAJSRxBuAXJJ4A0A2FFN8nFha7ZRK4Q1ALim8ASAbTDUHAAAAOiTxBiCXJN4AkA0SbwAAAKBDEm8AckniDQDZUA2Jt8IbgNxSLAPAjq8aCm9TzQEAAKCMJN4A5JKp5gCQDUmk9/ztJJVWSifxBgAAgDKSeAOQSxJvAMgG93gDAAAAHZJ4A5BLEm8AyIZqSLwV3gDkksIbALKhGgpvU80BAACgjCTeAOSSxBsAskHiDQAAAHRI4g1ALkm8ASAbkqQQSUpJdVrtlErhDUAuKbwBIBuKUYhipDTVPKV2SmWqOQAAAJSRxBuAXJJ4A0A2WFwNAAAA6JDEG4BckngDQDZYXA0AMkrhDQDZYKo5AAAA0CGJNwC5JPEGgGyohqnmEm8AAAAoI4k3ALkk8QaAbEhSvMfb4moA8C5SeANANiQRkSTptVUJppoDAABAGUm8AcgliTcAZEMxClGIlB4nllI7pZJ4AwAAQBlJvAHIJYk3AGSDx4kBAAAAHZJ4A5BLEm8AyIZiUohCSkl1Wo8lK5XCG4BcUngDQDYkSYqPE6vQ88RMNQcAAIAykngDkEsSbwDIBourAQAAAB2SeAOQW1JqANjxVUPirfAGIJdMNQeAbKiGVc1NNQcAAIAykngDkEsSbwDIBo8TAwAAADok8QYglyTeAJANLYl3WourpdJMyRTeAOSSwhsAsqEaVjU31RwAAADKSOINQC5JvAEgG5K/bWm1VQkSbwAAACgjiTcAuSTxBoBscI83AAAA0CGJNwC5JPEGgIyogpu8Fd4A5JLCGwAyIsWp5mGqOQAAAFQfiTcAuSTxBoBsSJKWLa22KkHiDQAAAGXU6cR79uzZMXv27Ghubi5nf4AMSir1q0PYDn/+859jyJAhVZt4v328Pu35A6NHXY8K96r63PfgnpXuQtU65MAlle5C1Tpp+Ycr3YWq9fTFIyvdhar0xutrIyJnjxObNm1aLF26NBYvXlzO/gDAu6K18E5z2xEYrwGoOkkh3a0CTDUHAACAMrK4GgC5VK1TzQGg2lhcDQAAAOiQxBuAXJJ4A0BGJH/b0mqrAhTeAOSSwhsAsiFXq5oDAAAApZN4A5BLEm8AyJAKTRFPi8QbAAAAykjiDUAuSbwBIBvc4w0AAAB0SOINQC5JvAEgIzxODACyS7EMAFlQ+NuWVlvvPlPNAQAAoIwk3gDkkqnmAJARVTDVXOINAAAAZSTxBiCXJN4AkBFVkHgrvAHIJYU3AGREUmjZ0mqrAkw1BwAAgDKSeAOQSxJvAMiGJGnZ0mqrEiTeAAAAUEYSbwBySeINABlhcTUAyCaFNwBkhMXVAAAAgI5IvAHIJYk3AGRDIWnZ0mqrEiTeAAAAUEYSbwBySeINABlhcTUAyCaFNwBkhMXVAAAAgI5IvAHIJYk3AGREFUw1l3gDAABAGUm8AcgliTcAZITEGwAAAOiIxBuAXJJ4A0BGVEHirfAGIJcU3gCQER4nBgAAAHRE4g1ALkm8ASAbCknLllZblSDxBgAAgDKSeAOQSxJvAMiIKlhcTeINQC61Ft5pbgBAdZk5c2Z84AMfiPr6+mhsbIyPfvSj8dRTT5XcjsIbAAAAtuDee++NadOmxaJFi2LhwoWxadOmOOKII2L9+vUltWOqOQC5ZKo5AGRDIVJcXK3E4++44452r6+88spobGyMRx99NA455JBOt6PwBgAAIFfWrVvX7nVNTU3U1NRs832vvPJKRET07du3pPOZag5Abrm/GwAyICmku0XEkCFDonfv3m3bzJkzt92NJIkvfelLcfDBB8eoUaNK+ggSbwByyVRzAMiIMqxq/vzzz0dDQ0Pb7s6k3WeccUb89re/jV/96lcln1bhDQAAQK40NDS0K7y35R//8R/jpz/9adx3332x6667lnw+hTcAuSTxBoCMqOBzvJMkiX/8x3+M+fPnxz333BPDhg3brtMqvAEAAGALpk2bFtdff33cdtttUV9fHytXroyIiN69e0fPnj073Y7CG4BckngDQDYUkhQfJ1ZiO3PmzImIiHHjxrXbf+WVV8bUqVM73Y7CGwAAALYgSdKp+BXeAOSSxBsAMqKC93inReENQC4pvAEgI6qg8O5SmdMCAABAPki8AcgliTcAZEMlF1dLi8QbAAAAykjiDUAuSbwBICOSQsuWVlsVoPAGIJcU3gCQERZXAwAAADoi8QYglyTeAJANFlcDAAAAOiTxBiCXJN4AkBFVcI+3whuAXFJ4A0BGpDjV3OJqAAAAUIUk3gDkksQbADKiCqaaS7wBAACgjCTeAOSSxBsAMkLiDQAAAHRE4g1ALkm8ASAbCimuap7a6uglUngDkEsKbwDg3WKqOQAAAJSRxBuAXJJ4A0BGWFwNAAAA6IjEG4BckngDQDZYXA0AMkyxDAAZUaGCOS2mmgMAAEAZSbwByCVTzQEgIyyuBgAAAHRE4g1ALkm8ASAbLK4GABml8AaAjDDVHAAAAOiIxBuAXJJ4A0A2VMNUc4k3AAAAlJHEG4BckngDQEZUwT3eCm8AcknhDQAZUQWFt6nmAAAAUEYSbwBySeINANlQDYurdbrwnj17dsyePTuam5vL2R8ggxQc5ZMkFRodyKy3j9fPXLp7dOteW+FeVaFDKt2B6nXle+6vdBeq1knLP1zpLkBudXqq+bRp02Lp0qWxePHicvYHAN4VrYl3mtuOwHgNQNVJUt4qwD3eAAAAUEbu8QYgl9zjDQAZUQWrmiu8AcglhTcAZEM1LK5mqjkAAACUkcQbgFySeANARlTBVHOJNwAAAJSRxBuAXJJ4A0A2VMM93gpvAHJJ4Q0AGWGqOQAAANARiTcAuSTxBoCMkHgDAAAAHZF4A5BLEm8AyIbC37a02qoEhTcAuaTwBoCMMNUcAAAA6IjEG4BckngDQDZUw3O8Jd4AAABQRhJvAHJLSg0AGeAebwAAAKAjEm8Acsk93gCQIRVKqtOi8AYglxTeAJANFlcDAAAAOiTxBiCXJN4AkBEWVwMAAAA6IvEGIJck3gCQDdVwj7fCG4BcUngDQEaYag4AAAB0ROINQC5JvAEgG6phqrnEGwAAAMpI4g1ALkm8ASAjquAeb4U3ALmk8AaAjKiCwttUcwAAACgjiTcAuSTxBoBssLgaAAAA0CGJNwC5JPEGgIxwjzcAAADQEYk3ALkk8QaAbCgkSRSSdKLqtNoplcIbgFxSeANARphqDgAAAHRE4g1ALkm8ASAbPE4MAAAA6JDEG4BckngDQEZUwT3eCm8AcknhDQDZYKo5AAAA0CGJNwC5JPEGgIyogqnmEm8AAAAoI4k3ALkk8QaAbKiGe7wV3gDkksIbADLCVHMAAACgIxJvAHJLSg0A2VCpKeJpkXgDAABAGUm8Acgl93gDQEYkScuWVlsVoPAGIJcU3gCQDdWwqrmp5gAAAFBGEm8AckniDQAZ4XFiAAAAQEck3gDkksQbALKhUGzZ0mqrEiTeAAAAUEYSbwBySeINABlRBfd4K7wByCWFNwBkg8eJAQAAAB1SeAOQS62Jd5obAFAGSZLuVqL77rsvJk+eHIMGDYpCoRC33npryW0ovAEAAGAr1q9fH2PGjInLLrtsu9twjzcAueQebwDIhnLc471u3bp2+2tqaqKmpmaL75k4cWJMnDjxHZ1X4g1ALplqDgAZkaS8RcSQIUOid+/ebdvMmTPL+hEk3gAAAOTK888/Hw0NDW2vt5Z2p0XhDUAumWoOANlQjqnmDQ0N7QrvcjPVHAAAAMpI4g1ALkm8ASAjtvMxYFttqwIU3gDkksIbALKhHFPNS/Haa6/F008/3fZ62bJl8cQTT0Tfvn3jPe95T6faUHgDAADAVjzyyCMxfvz4ttdf+tKXIiJiypQpcdVVV3WqDYU3ALkk8QaAjHjLY8BSaatE48aNi+QdTlG3uBoAAACUkcQbgFySeANANlT6Hu80SLwBAACgjCTeAOSSxBsAMqKYtGxptVUBCm8AcknhDQAZUeHF1dJgqjkAAACUkcQbgFySeANANhQixcXV0mmmZBJvAAAAKCOJNwC5JaUGgAxIkpYtrbYqQOENQC6Zag4A2eA53gAAAECHJN4A5JLEGwAywuPEAAAAgI5IvAHIJYk3AGRDIUmikNKiaGm1U6pOF96zZ8+O2bNnR3Nzczn7k3tJhX4Q4J3wc0sWVWvh/fbxutftj0S3QvcK96oKHfKhSvegan1k0N6V7kIVe7XSHahaL/7LjjEGVJtNawsRd0RE8W9bGtJqp0Sdnmo+bdq0WLp0aSxevLic/QEA3gHjNQDseEw1ByCXqjXxBoBqUw1TzS2uBgAAAGUk8QYglyTeAJARHicGAAAAdETiDUAuSbwBICOSpGVLq60KUHgDkEsKbwDIhkLSsqXVViWYag4AAABlJPEGIJck3gCQEVUw1VziDQAAAGUk8QYglyTeAJANhWLLllZblaDwBiCXFN4AkBGmmgMAAAAdkXgDkEsSbwDIiORvW1ptVYDEGwAAAMpI4g1ALkm8ASAbCkkShZTuzU6rnVIpvAHIJYU3AGSExdUAAACAjki8AcgliTcAZEQSEWk9f9viagAAAFB9JN4A5JLEGwCyweJqAJBRCm8AyIgkUlxcLZ1mSmWqOQAAAJSRxBuA3JJSA0AGeJwYAAAA0BGJNwC55B5vAMiIYkSkNcym9ViyEkm8AQAAoIwk3gDkksQbALLB48QAIKMU3gCQERZXAwAAADoi8QYglyTeAJAREm8AAACgIxJvAHJJ4g0AGVEFibfCG4BcUngDQEZ4jjcAAADQEYk3ALkk8QaAbKiG53hLvAEAAKCMJN4A5JLEGwAywuJqAOResTniuQciXnspoq5/RNPYiC5dK92rbVJ4A0BGFJOIQkoFc1HhDUDWLP1pxB3nRKx78X/2NQyKOPLiiJHHVK5fAAA7EPd4A7B9lv40Yt7n2xfdERHrVrTsX/rTyvSrk1oT7zQ3AKAMWqeap7VVgMIbgNIVm1uS7tjS4PW3fXec23IcAEDOKbwBKN1zD2yedLeTRKx7oeW4HZTEGwCyIs20W+INQFa89lK6xwEAVDGLqwFQurr+6R5XAVY1B4CM8DgxAHKpaWzL6uXrVsSWp2wVWv68aey73bNOU3gDQEYUU5wiXqHHiZlqDkDpunRteWRYRES8veD82+sjv5mJ53kDAJSbwhuA7TPymIhPXxPRMLD9/oZBLft38Od4W1wNADIiKaa7VYCp5gBsv5HHROw+qWX18tdearmnu2mspBsA4C0U3gC8M126Rgz7cKV7UTL3eANARlhcDQCySeENABlhcTUAAACgIxJvAHJJ4g0AGVEFU80l3gAAAFBGEm8AcktKDQAZkESKiXc6zZRK4Q1ALplqDgAZYao5AAAA0BGJNwC5JPEGgIwoFiOimGJb7z6JNwAAAJSRxBuAXJJ4A0BGuMcbAAAA6IjEG4BckngDQEZUQeKt8AYglxTeAJARxSRSewB30VRzAAAAqDoSbwBySeINANmQJMVIknQeA5ZWO6WSeAMAAEAZSbwByCWJNwBkRJKkd2+2xdUA4N2j8AaAjEhSXFzNc7wBAACg+ki8AcgliTcAZESxGFFIaVE0i6sBAABA9ZF4A5BLEm8AyIgquMdb4Q1ALim8ASAbkmIxkpSmmnuONwAAAFQhiTcAuSTxBoCMqIKp5hJvAAAAKCOJNwC5JPEGgIwoJhGFbCfeCm8AcknhDQAZkSQRkdZzvE01BwAAgKoj8QYglyTeAJANSTGJJKWp5onEGwAAAKqPxBuAXJJ4A0BGJMVI7x7vlNopkcQbACro8ssvj2HDhkVtbW3st99+cf/991e6SwDA27zT8VrhDUAutSbeaW6luvHGG+PMM8+M8847Lx5//PH48Ic/HBMnTozly5eX4RMDQDYlxSTVrVRpjNcKbwByaUcovC+55JI45ZRT4gtf+ELssccecemll8aQIUNizpw5ZfjEAJBRSTHdrURpjNcl3+PdugrcunXrSn0rAFTcq6++GhHpj2Ot7b293Zqamqipqdns+DfffDMeffTROPfcc9vtP+KII+KBBx54x/1pHa83xcaIyizgWtWKGzZUugtVa1OysdJdgJL5b0J5FDe8ERHpjmWbouW/Me/2eN3pwnv27Nkxe/bsePPNNyMiYsiQIZ0+CQDsaMoxjtXV1W3W7vTp02PGjBmbHfuXv/wlmpubo3///u329+/fP1auXLndfXj7eP2r+Pl2t0UHzr2t0j2oWm60IJP8N6Gs0h7LKjFed7rwnjZtWkybNi2KxWKMGDEiHn30USu4lsEHPvCBWLx4caW7UZVc2/JwXcvHtS2PJElin332icceeyy6dEn3jqskSTYbG7f02/O3evvxW2qjFMbrd4e/n+Xj2paPa1s+rm15lGvMrsR4XfJU8y5dukSPHj2id+/epb6VTujatWs0NDRUuhtVybUtD9e1fFzb8qmtrY0+ffpUtA8777xzdO3adbPflq9atWqz36pvD+N1efn7WT6ubfm4tuXj2pZPpcfstMbr7fq1wbRp07bnbXSCa1s+rm15uK7l49qWz45wbXv06BH77bdfLFy4sN3+hQsXxtixY1M5x47wOauVa1s+rm35uLbl49qWT6WvbVrjdSFpXX0FAHhX3XjjjXHiiSfGFVdcEQceeGD84Ac/iB/+8IexZMmSaGpqqnT3AIBIZ7wueao5AJCOz3zmM/Hyyy/HhRdeGCtWrIhRo0bFz3/+c0U3AOxA0hivJd4AAABQRuku5woAAAC0o/AGAACAMlJ4AwAAQBkpvAEAAKCMFN4AAABQRgpvAAAAKCOFNwAAAJSRwhsAAADKSOENAAAAZaTwBgAAgDJSeAMAAEAZKbwBAACgjLpVugNQKc3NzbFx48ZKdyNzunfvHl27dq10NwAAIDMU3uROkiSxcuXKWLt2baW7kll9+vSJAQMGRKFQqHRXAABgh6fwJndai+7Gxsbo1auX4rEESZLE66+/HqtWrYqIiIEDB1a4RwAAsONTeJMrzc3NbUV3v379Kt2dTOrZs2dERKxatSoaGxtNOwcAgG2wuBq50npPd69evSrck2xrvX7ukQcAgG1TeJNLppe/M64fAAB0nsIbAAAAykjhDQAAAGWk8IaMmzp1anz0ox9Nrb1x48bFmWeemVp7AACQd1Y1h+3QXEzi4WVrYtWrG6KxvjYOGNY3unbJ9n3PGzdujO7du1e6GwAAUHUk3lCiO363Ig6++K447oeL4otzn4jjfrgoDr74rrjjdyvKet6bb745Ro8eHT179ox+/frFYYcdFv/3//7fuPrqq+O2226LQqEQhUIh7rnnnoiIOOecc2LEiBHRq1evGD58eHzta19rtwr5jBkzYu+9944f//jHMXz48KipqYkpU6bEvffeG9/97nfb2nv22WfL+rkAAKDaSbyhBHf8bkWcdu1jkbxt/8pXNsRp1z4Wc07YN44cNTD1865YsSKOO+64mDVrVnzsYx+LV199Ne6///74/Oc/H8uXL49169bFlVdeGRERffv2jYiI+vr6uOqqq2LQoEHx5JNPxqmnnhr19fXx//7f/2tr9+mnn4558+bFLbfcEl27do2mpqb4r//6rxg1alRceOGFERGxyy67pP55AAAgTxTe0EnNxSQuuH3pZkV3REQSEYWIuOD2pXH4yAGpTztfsWJFbNq0KT7+8Y9HU1NTRESMHj06IiJ69uwZb7zxRgwYMKDde84///y2/z906ND48pe/HDfeeGO7wvvNN9+Mn/zkJ+2K6x49ekSvXr02aw8AANg+pppDJz28bE2seGXDVv88iYgVr2yIh5etSf3cY8aMiQkTJsTo0aPjU5/6VPzwhz+M//7v/+7wPTfffHMcfPDBMWDAgKirq4uvfe1rsXz58nbHNDU1SbQBAKDMFN7QSate3XrRvT3HlaJr166xcOHC+MUvfhEjR46M733ve7HbbrvFsmXLtnj8okWL4rOf/WxMnDgxfvazn8Xjjz8e5513Xrz55pvtjttpp51S7ysAANCeqebQSY31takeV6pCoRAHHXRQHHTQQfH1r389mpqaYv78+dGjR49obm5ud+yvf/3raGpqivPOO69t33PPPdep82ypPQAAYPspvKGTDhjWNwb2ro2Vr2zY4n3ehYgY0Lvl0WJpe+ihh+LOO++MI444IhobG+Ohhx6K1atXxx577BEbNmyI//iP/4innnoq+vXrF7179473ve99sXz58pg7d2584AMfiAULFsT8+fM7da6hQ4fGQw89FM8++2zU1dVF3759o0sXk2MAAGB7+dc0dFLXLoWYPnlkRLQU2W/V+nr65JFleZ53Q0ND3HfffXHUUUfFiBEj4vzzz4/vfOc7MXHixDj11FNjt912i/333z922WWX+PWvfx3HHntsnHXWWXHGGWfE3nvvHQ888EB87Wtf69S5zj777OjatWuMHDkydtlll83uCwcAAEpTSJJkS+EdVKUNGzbEsmXLYtiwYVFbu31Twu/43Yq44Pal7RZaG9i7NqZPHlmWR4ntiNK4jgAAkBemmkOJjhw1MA4fOSAeXrYmVr26IRrrW6aXlyPpBgAAsk/hDduha5dCHPjefpXuBgAAkAHu8QYAAIAyUngDAABAGSm8AQAAoIwU3gAAAFBGCm8AAAAoI4U3AAAAlJHCGwAAAMpI4Q05NmPGjNh7770r3Q0AAKhqCm8AAAAoo26V7gBkUrE54rkHIl57KaKuf0TT2IguXSvdKwAAYAck8YZSLf1pxKWjIq4+OuKWU1r+99JRLfvLKEmSmDVrVgwfPjx69uwZY8aMiZtvvjkiIu65554oFApx5513xv777x+9evWKsWPHxlNPPdWujW9+85vRv3//qK+vj1NOOSU2bNhQ1j4DAAAKbyjN0p9GzPt8xLoX2+9ft6JlfxmL7/PPPz+uvPLKmDNnTixZsiTOOuusOOGEE+Lee+9tO+a8886L73znO/HII49Et27d4uSTT277s3nz5sX06dPjG9/4RjzyyCMxcODAuPzyy8vWXwAAoEUhSZKk0p2Ad8uGDRti2bJlMWzYsKitrS3tzcXmlmT77UV3m0JEw6CIM59Mfdr5+vXrY+edd4677rorDjzwwLb9X/jCF+L111+P//W//leMHz8+/vM//zMmTJgQERE///nPY9KkSfHXv/41amtrY+zYsTFmzJiYM2dO2/s/9KEPxYYNG+KJJ54oqT/v6DoCAEDOSLyhs557oIOiOyIiiVj3QstxKVu6dGls2LAhDj/88Kirq2vbrrnmmvjTn/7Udtxee+3V9v8HDhwYERGrVq2KiIjf//737Yr2iNjsNQAAkD6Lq0FnvfZSuseVoFgsRkTEggULYvDgwe3+rKampq347t69e9v+QqHQ7r0AAEBlSLyhs+r6p3tcCUaOHBk1NTWxfPnyeN/73tduGzJkSKfa2GOPPWLRokXt9r39NQAAkD6JN3RW09iWe7jXrYiILS2N8Ld7vJvGpn7q+vr6OPvss+Oss86KYrEYBx98cKxbty4eeOCBqKuri6ampm228cUvfjGmTJkS+++/fxx88MFx3XXXxZIlS2L48OGp9xcAAPgfCm/orC5dI468uGX18ihE++K7ZVp3HPnNsj3P+6KLLorGxsaYOXNmPPPMM9GnT5/Yd99946tf/WqnppN/5jOfiT/96U9xzjnnxIYNG+ITn/hEnHbaafEf//EfZekvAADQwqrm5Eoqq3Ev/WnEHee0X2itYXBL0T3ymHQ6uoOzqjkAAHSexBtKNfKYiN0ntaxe/tpLLfd0N40tW9INAABkm8IbtkeXrhHDPlzpXgAAABlgVXMAAAAoI4U3AAAAlJHCm1yypuA74/oBAEDnKbzJle7du0dExOuvv17hnmRb6/VrvZ4AAMDWWVyNXOnatWv06dMnVq1aFRERvXr1ikKhUOFeZUeSJPH666/HqlWrok+fPtG1q5XcAQBgWzzHm9xJkiRWrlwZa9eurXRXMqtPnz4xYMAAv7QAAIBOUHiTW83NzbFx48ZKdyNzunfvLukGAIASKLwBAACgjCyuBgAAAGWk8AYAAIAyUngDAABAGSm8AQAAoIwU3gAAAFBGCm8AAAAoI4U3AAAAlNH/B3bBQseUNUS7AAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 1000x700 with 4 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# this is a testing cell, do not edit or delete\n",
    "maze = ProblemFactory().create_problem_from_json(json_path='boards/tiny0.json')\n",
    "maze.visualize()\n",
    "\n",
    "assert(cityblock_heuristic(maze.get_start_node(), maze.get_end_node()) != -1), \"it seems like you might not have implemented this heuristic yet, the distance is -1\"\n",
    "assert(cityblock_heuristic(maze.get_start_node(), maze.get_end_node()) == 7.0), \"the city block heuristic returned the wrong distance between start and end node\"\n",
    "assert(cityblock_heuristic(Node(None, [2, 3], None, 0, 0), maze.get_end_node()) == 3.0), \"the city block heuristic returned the wrong distance between arbitrary node and end\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Check Euclidean Heuristic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "5cbac803847c6552e5948aa13664d4a7",
     "grade": true,
     "grade_id": "cell-30cd5ba142359b7e",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# this is a testing cell, do not edit or delete\n",
    "maze = ProblemFactory().create_problem_from_json(json_path='boards/tiny0.json')\n",
    "\n",
    "assert(euclidean_heuristic(maze.get_start_node(), maze.get_end_node()) != -1), \"it seems like you might not have implemented this heuristic yet, the distance is -1\"\n",
    "assert(math.isclose(euclidean_heuristic(maze.get_start_node(), maze.get_end_node()), 5.0)), \"the euclidean heuristic returned the wrong distance between start and end node\"\n",
    "assert(math.isclose(euclidean_heuristic(Node(None, [2, 3], None, 0, 0), maze.get_end_node()), 2.23606797749979)), \"the euclidean heuristic returned the wrong distance between arbitrary node and end\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Check Chebyshev Heuristic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ca7d173ebc842e01cf0ee94873621c2b",
     "grade": true,
     "grade_id": "cell-7d395cfb4952c216",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# this is a testing cell, do not edit or delete\n",
    "maze = ProblemFactory().create_problem_from_json(json_path='boards/tiny0.json')\n",
    "\n",
    "assert(chebyshev_heuristic(maze.get_start_node(), maze.get_end_node()) != -1), \"it seems like you might not have implemented this heuristic yet, the distance is -1\"\n",
    "assert(chebyshev_heuristic(maze.get_start_node(), maze.get_end_node()) == 4.0), \"the chebyshev heuristic returned the wrong distance between start and end node\"\n",
    "assert(chebyshev_heuristic(Node(None, [2, 3], None, 0, 0), maze.get_end_node()) == 2.0), \"the chebyshev heuristic returned the wrong distance between arbitrary node and end\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing GBFS\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "deletable": false,
    "editable": true,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "51332bf82c052acd3d8f20d078acde5c",
     "grade": false,
     "grade_id": "cell-d09ad07d2e0d6517",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "state (4, 4) was reached following the sequence ['R', 'D', 'D', 'R', 'R', 'D', 'D'] (cost: 17, depth: 7)\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA94AAAIxCAYAAAC7CGDIAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjUsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvWftoOwAAAAlwSFlzAAAPYQAAD2EBqD+naQAATDJJREFUeJzt3Xl4FFXe9vG7sydkM4FA2AKoLJFdxAEchUGURVTcd8DleUZwZkR5XjcU1HEYccPRCC4I7oALbswwMCioCIgsLqAosipLEIRAMJB0n/ePmB6ahCYdqqhU1/dzXXWZrlSfOt0dPPnlPnXKZ4wxAgAAAAAAtohxugMAAAAAAEQzCm8AAAAAAGxE4Q0AAAAAgI0ovAEAAAAAsBGFNwAAAAAANqLwBgAAAADARhTeAAAAAADYiMIbAAAAAAAbUXgDAAAAAGAjCm9Aks/nq9Y2b948zZs3Tz6fT2+88Ybt/Vq+fLnOOOMMZWRkyOfzafz48cHzz5s3L+L2InnukCFD1KxZs4jPAQDRpraOEcfS5s2bNWbMGK1YscLytq+99lr17ds3ZF9V45+TVq1apTFjxmj9+vWO9uNQ69evl8/n05QpU5zuSq311FNPVfn+VPXeTZkyRT6fr0af86RJk9SoUSMVFxfXvLOIanFOdwCoDRYuXBjy+P7779eHH36oDz74IGR/fn6+li1bdsz6de2116q4uFhTp07Vcccdp2bNmiklJUULFy5Ufn7+MesHAHhZbR0jjqXNmzfr3nvvVbNmzdSxY0fL2l2+fLleeOEFLV68OGR/VeOfk1atWqV7771XPXv2dLwvB8vNzdXChQt1/PHHO92VWuupp55S3bp1NWTIkJD9Vr93gwcP1oMPPqhx48bp3nvvtaRNRBcKb0DS7373u5DH9erVU0xMTKX9x9rXX3+tG264Qf369QvZ73S/AMBLausYEQ3+/ve/q2vXrurSpUvI/sONfzVVWloqn8+nuLjo+tU3MTGRn8Masvq9i4uL0//+7//q/vvv12233aaUlBTL2kZ0YKo5UEOlpaW666671LBhQ6Wnp+vMM8/U6tWrKx33n//8R71791Z6erpSUlLUo0cPzZ07N2zbFVOdysrKNGHChOA0Runw08U///xznXvuucrKylJSUpI6deqk6dOnV+u1TJkyRa1atVJiYqLatGmjF198sXpvAgCgSnaOERV27dqlW2+9VS1atFBiYqJycnLUv39/ffvtt8Fjdu7cqWHDhqlRo0ZKSEhQixYtdNddd2n//v0hbb3++us69dRTlZGRoZSUFLVo0ULXXnutpPJx55RTTpEkDR06NDgmjRkzRpK0du1aXXbZZWrYsKESExNVv3599e7d+4jT0rdt26YZM2bo6quvDu4LN/5J5QX5eeedp+OOO05JSUnq2LGjXnjhhZB2K8bJl156SbfeeqsaNWqkxMRErVmz5rB9mTBhgjp06KDU1FSlpaWpdevWuvPOO4N9uvjiiyVJvXr1Cvbp4CnK1fkcx4wZI5/Pp+XLl+uCCy5Qenq6MjIydNVVV2n79u0hxzZr1kznnHOOZsyYofbt2yspKUktWrTQP/7xj5DjqpouXXGelStX6vLLL1dGRobq16+va6+9Vrt37w55/q5du3TdddcpKytLqampGjBggNauXRvy+YazceNGXXXVVcrJyQn+DvHII48oEAhU6uPDDz+sRx99VM2bN1dqaqq6deumRYsWHfEc27dv17Bhw5Sfn6/U1FTl5OToD3/4gz7++OMjPrdZs2ZauXKl5s+fH/zcKmYsRDJNv7r/Tq+88koVFRVp6tSpR2wT3kPhDdTQnXfeqQ0bNui5557TM888o++//14DBw6U3+8PHvPyyy/rrLPOUnp6ul544QVNnz5dWVlZOvvss8P+YjVgwIDg1MaLLrpICxcurDTV8WAffvihevTooV27dmnixIl655131LFjR1166aVHHFCmTJmioUOHqk2bNnrzzTc1atQo3X///ZWmUAIAqs/OMUKS9uzZo9NOO01PP/20hg4dqvfee08TJ05Uy5YttWXLFklSSUmJevXqpRdffFG33HKLZs6cqauuukrjxo3TBRdcEGxr4cKFuvTSS9WiRQtNnTpVM2fO1D333KOysjJJUufOnTV58mRJ0qhRo4Jj0vXXXy9J6t+/v5YuXapx48Zpzpw5mjBhgjp16qRdu3aFfQ2zZ89WaWmpevXqFdwXbvxbvXq1unfvrpUrV+of//iH3nrrLeXn52vIkCEaN25cpfbvuOMObdy4URMnTtR7772nnJycKvsxdepUDRs2TGeccYZmzJiht99+WyNGjAheqztgwAD97W9/kyQVFBQE+zRgwABJkX+OgwYN0gknnKA33nhDY8aM0dtvv62zzz5bpaWlIcetWLFCN998s0aMGKEZM2aoe/fu+stf/qKHH3447Pta4cILL1TLli315ptv6vbbb9err76qESNGBL8fCAQ0cOBAvfrqq7rttts0Y8YMnXrqqZWutz+c7du3q3v37po9e7buv/9+vfvuuzrzzDM1cuRI3XTTTZWOLygo0Jw5czR+/Hi98sorKi4uVv/+/Sv9MeBQO3fulCSNHj1aM2fO1OTJk9WiRQv17NnziGvWzJgxQy1atFCnTp2Cn9uMGTOq9foqRPL5NmjQQK1bt9bMmTMjOgc8wgCoZPDgwaZOnTpVfu/DDz80kkz//v1D9k+fPt1IMgsXLjTGGFNcXGyysrLMwIEDQ47z+/2mQ4cOpmvXrkfshyQzfPjwKs//4YcfBve1bt3adOrUyZSWloYce84555jc3Fzj9/urfK7f7zcNGzY0nTt3NoFAIPi89evXm/j4eJOXl3fEPgKA19SGMeK+++4zksycOXMOe8zEiRONJDN9+vSQ/Q8++KCRZGbPnm2MMebhhx82ksyuXbsO29aSJUuMJDN58uSQ/T///LORZMaPHx+2v1W58cYbTXJycsj4U6Gq8e+yyy4ziYmJZuPGjSH7+/XrZ1JSUoL9r/gMTj/99Gr146abbjKZmZlhj3n99dcrjb3GRPY5jh492kgyI0aMCDn2lVdeMZLMyy+/HNyXl5dnfD6fWbFiRcixffr0Menp6aa4uNgYY8y6desqfS4V5xk3blzIc4cNG2aSkpKC7/fMmTONJDNhwoSQ48aOHWskmdGjR4d9T26//XYjySxevDhk/4033mh8Pp9ZvXp1SB/btWtnysrKgsd99tlnRpJ57bXXwp7nUGVlZaa0tNT07t3bDBo06IjHn3TSSeaMM86otL+q927y5MlGklm3bp0xpmb/Tq+88kpTv379iF4TvIHEG6ihc889N+Rx+/btJUkbNmyQJH366afauXOnBg8erLKysuAWCATUt29fLVmyxJKVL9esWaNvv/1WV155pSSFnKt///7asmVLldMbpfL0YPPmzbriiitCpvLl5eWpe/fuR903APAqu8eIf/3rX2rZsqXOPPPMwx7zwQcfqE6dOrroootC9lcsMlWR1lVMI7/kkks0ffp0/fTTT9V+nVlZWTr++OP10EMP6dFHH9Xy5ctDphmHs3nzZtWrVy9k/Anngw8+UO/evdWkSZOQ/UOGDNG+ffsqzQy78MILq9Vu165dtWvXLl1++eV655139PPPP1freVLNPseK8brCJZdcori4OH344Ych+0866SR16NAhZN8VV1yhoqKiai3iV9XPYElJiQoLCyVJ8+fPD57/YJdffvkR25bKP4/8/Hx17do1ZP+QIUNkjKk0c27AgAGKjY0N6Y/0338T4UycOFGdO3dWUlKS4uLiFB8fr7lz5+qbb76pVl9rqiafb05OjgoLC4MzRoAKFN5ADWVnZ4c8TkxMlCT9+uuvksqvXZPKp8rFx8eHbA8++KCMMcHpU0ej4jwjR46sdJ5hw4ZJ0mF/idixY4ek8qlRh6pqHwCgeuweI7Zv367GjRuH7cOOHTvUoEGDSoVtTk6O4uLigmPA6aefrrfffltlZWW65ppr1LhxY7Vt21avvfbaEV+nz+fT3LlzdfbZZ2vcuHHq3Lmz6tWrpz//+c/as2dP2Of++uuvSkpKOuI5Dn49ubm5lfY3bNgw+P2DVXVsVa6++mo9//zz2rBhgy688ELl5OTo1FNP1Zw5c4743Jp8joeOr3FxccrOzq7U/3Bj86HHVuVIP4M7duxQXFycsrKyQo6rX7/+EduueH4kn8eR+nM4jz76qG688UadeuqpevPNN7Vo0SItWbJEffv2PeJzj1ZNPt+kpCQZY1RSUmJr3+A+0bW0I1CL1K1bV5L0xBNPHHbVzOoObtU5zx133BFyzd7BWrVqVeX+ikFw69atlb5X1T4AgDWOdoyoV6+efvzxx7DnyM7O1uLFi2WMCSm+K9K4ij5I0nnnnafzzjtP+/fv16JFizR27FhdccUVatasmbp16xb2PHl5eZo0aZIk6bvvvtP06dM1ZswYHThwQBMnTjzs8+rWrRvR7deys7OD168fbPPmzcH2DlbdJF0qXzRu6NChKi4u1kcffaTRo0frnHPO0Xfffae8vLzDPq8mn+PWrVvVqFGj4OOysjLt2LGjUmEabmw+9NiayM7OVllZmXbu3BlSfFd3/I/086ipl19+WT179tSECRNC9h/pDztWqMnnu3PnTiUmJio1NdX2/sFdSLwBm/To0UOZmZlatWqVunTpUuWWkJBw1Odp1aqVTjzxRH3xxReHPU9aWtphn5ubm6vXXntNxpjg/g0bNujTTz896r4BAKp2tGNEv3799N1334VdCLN3797au3ev3n777ZD9FXeu6N27d6XnJCYm6owzztCDDz4oqfw+2xX7pSOnky1bttSoUaPUrl27IxbVrVu31o4dO464uNbBr+eDDz4IFnYHv56UlBRLbg1Vp04d9evXT3fddZcOHDiglStXSjr866/J5/jKK6+EPJ4+fbrKysrUs2fPkP0rV67UF198EbLv1VdfVVpamjp37nzUr/WMM86QJE2bNi1kf3VX5O7du7dWrVpV6XN+8cUX5fP5QhbNOxo+ny/4/lf48ssvwy46e7DExMQaJ+M1+XzXrl2r/Pz8Gp0P0Y3EG7BJamqqnnjiCQ0ePFg7d+7URRddpJycHG3fvl1ffPGFtm/fXumvtzX19NNPq1+/fjr77LM1ZMgQNWrUSDt37tQ333yjZcuW6fXXX6/yeTExMbr//vt1/fXXa9CgQbrhhhu0a9cujRkzhqnmAGCjox0jbr75Zk2bNk3nnXeebr/9dnXt2lW//vqr5s+fr3POOUe9evXSNddco4KCAg0ePFjr169Xu3bt9Mknn+hvf/ub+vfvH7w+/J577tGPP/6o3r17q3Hjxtq1a5cef/xxxcfHB4uz448/XsnJyXrllVfUpk0bpaamqmHDhvr5559100036eKLL9aJJ56ohIQEffDBB/ryyy91++23h30PevbsKWOMFi9erLPOOuuI79no0aP1/vvvq1evXrrnnnuUlZWlV155RTNnztS4ceOUkZERwSfwXzfccIOSk5PVo0cP5ebmauvWrRo7dqwyMjKC17+3bdtWkvTMM88oLS1NSUlJat68ubKzsyP+HN966y3FxcWpT58+Wrlype6++2516NCh0rXWDRs21LnnnqsxY8YoNzdXL7/8subMmaMHH3zQkntE9+3bVz169NCtt96qoqIinXzyyVq4cGHwDzMxMeHzuREjRujFF1/UgAEDdN999ykvL08zZ87UU089pRtvvFEtW7Y86j5K0jnnnKP7779fo0eP1hlnnKHVq1frvvvuU/Pmzat1HXW7du00depUTZs2TS1atFBSUpLatWtXrXNH+u80EAjos88+03XXXVfj14so5tiybkAtVp0Va19//fWQ/VWtjmmMMfPnzzcDBgwwWVlZJj4+3jRq1MgMGDCg0vOromquam6MMV988YW55JJLTE5OjomPjzcNGjQwf/jDH8zEiROP+NznnnvOnHjiiSYhIcG0bNnSPP/882bw4MGsag4AVagtY8Qvv/xi/vKXv5imTZua+Ph4k5OTYwYMGGC+/fbb4DE7duwwf/zjH01ubq6Ji4szeXl55o477jAlJSXBY95//33Tr18/06hRI5OQkGBycnJM//79zccffxxyvtdee820bt3axMfHB1e93rZtmxkyZIhp3bq1qVOnjklNTTXt27c3jz32WMgK1lXx+/2mWbNmZtiwYZW+V9X4Z4wxX331lRk4cKDJyMgwCQkJpkOHDpXe08N9BofzwgsvmF69epn69eubhIQE07BhQ3PJJZeYL7/8MuS48ePHm+bNm5vY2NhKn2V1PseK1caXLl1qBg4caFJTU01aWpq5/PLLzbZt20LOlZeXZwYMGGDeeOMNc9JJJ5mEhATTrFkz8+ijj4YcF25V8+3bt4cce+iK3cYYs3PnTjN06FCTmZlpUlJSTJ8+fcyiRYuMJPP4448f8b3bsGGDueKKK0x2draJj483rVq1Mg899FDwbioH9/Ghhx6q9HxVY/X0/fv3m5EjR5pGjRqZpKQk07lzZ/P2229X+/eU9evXm7POOsukpaUZScHnVGdV8wrV/Xc6d+7c4GcMHMpnzEHzSwEAAIBj5JFHHtEDDzygn376ScnJyU53x1ZjxozRvffeq+3btx/x+udmzZqpbdu2ev/9949R7/7r1Vdf1ZVXXqkFCxZwh5MIXX311Vq7dq0WLFjgdFdQCzHVHAAAAI4YPny4nnzySRUUFGjkyJFOd8dzXnvtNf30009q166dYmJitGjRIj300EM6/fTTKboj9MMPP2jatGlh112At1F4AwAAwBFJSUl66aWXgou44dhKS0vT1KlT9de//lXFxcXKzc3VkCFD9Ne//tXprrnOxo0b9eSTT+q0005zuiuopZhqDgAAAACAjbidGAAADvjoo480cOBANWzYUD6fr9ItnwAAQO0zduxY+Xw+3XzzzRE9j8IbAAAHFBcXq0OHDnryySed7goAAKiGJUuW6JlnnlH79u0jfi7XeAMA4IB+/fqpX79+TncDAABUw969e3XllVfq2WefrdE6CBEX3oFAQJs3b1ZaWpp8Pl/EJwQAwEnGmODtfGJirJ34ZYypNDYmJiYqMTHR0vNUB+M1AMDt7BqzazJeDx8+XAMGDNCZZ55pb+FdUFCggoICHThwQD/88EPEJwIAINqlpqZq7969IftGjx6tMWPGHLM+MF4DAKJJg5xYbS30W9pmpOP11KlTtWzZMi1ZsqTG54x4VfPdu3crMzNTmzZtUnp6eo1PDACAE3766Sfl5+fb1v6h42N1Em+fz6cZM2bo/PPPt6wfFeP1hmXNlJ7Kki5Wu3FTN6e7ELUmNFnodBcA1BI/bS1T29M3at3SPKWnWTOWFe0JqPnJG6o9Xm/atEldunTR7Nmz1aFDB0lSz5491bFjR40fP77a5414qnlFJJ+enk7hDQBwnaKiouDXVk7Brvg7dm0ZH4PjdWqMZb+s4L8SUhOc7kLU4ucVQIWiveX/P0hPs34sq+54vXTpUhUWFurkk08O7vP7/froo4/05JNPav/+/YqNjT1iOyyuBgDwJJ/PZ/m1zxFOIgMAANXgNwH5LRpi/SYQ0fG9e/fWV199FbJv6NChat26tW677bZqFd0ShTcAAI7Yu3ev1qxZE3y8bt06rVixQllZWWratKmDPQMAABXS0tLUtm3bkH116tRRdnZ2pf3hUHgDADzJ6cT7888/V69evYKPb7nlFknS4MGDNWXKFEv7BQCAmwVkFJA1kbdV7USKwhsA4El2FN6R6NmzJ1PTAQCohoACimyCePi2jta8efMifg6rVwAAAAAAYCMSbwCAJzmdeAMAgOrxGyO/RbPErGonUiTeAAAAAADYiMQbAOBJJN4AALgDi6sBAOBSFN4AALhDQEZ+lxfeTDUHAAAAAMBGJN4AAE8i8QYAwB2iYao5iTcAAAAAADYi8QYAeBKJNwAA7sDtxAAAAAAAQFgk3gAATyLxBgDAHQK/bVa15QQKbwCAJ1F4AwDgDn4LbydmVTuRYqo5AAAAAAA2IvEGAHgSiTcAAO7gN+WbVW05gcQbAAAAAAAbkXgDADyJxBsAAHdgcTUAAFyKwhsAAHcIyCe/rBmzAxa1EymmmgMAAAAAYCMSbwCAJ5F4AwDgDgFTvlnVlhNIvAEAAAAAsBGJNwDAk0i8AQBwB7+F13hb1U6kKLwBAJ5E4Q0AgDtEQ+HNVHMAAAAAAGxE4g0A8CQSbwAA3CFgfAoYi24nZlE7kSLxBgAAAADARiTeAADPsjLxNsah+5MAABDluMYbAAAAAACEReINAPAkq6/x5npxAADs4VeM/BZlxn5LWokchTcAwJMovAEAcAdj4eJqhsXVAAAAAACIPiTeAABPIvEGAMAdomFxNQpvRMwfMPps3U4V7ilRTlqSujbPUmwMv3ACAAAAQFUovBGRWV9v0b3vrdKW3SXBfbkZSRo9MF992+Y62DMAiAyJNwAA7uA3MfIbixZXc+jun1zjjWqb9fUW3fjyspCiW5K27i7RjS8v06yvtzjUMwCIXEXhbeUGAACsF5BPAcVYtDHVHLWYP2B073urVNUfiCr2jZrxteolxjDtvAZ8PikvJ12ZqUlOdwUAEEWSTJqa+jso1RynA75fne5OtXxRmO90F8JKTfhJzdJnKzbmgNNdAeAiFN6ols/W7ayUdB/q5+ID+s/KLTohO+UY9Sq6rPlplxpm11GbptkU4MAxwFRzeEGHsr6qHzje6W5EZO1up3twZKt3XqqWx72u5hmzKMCBY4DF1eAZhXvCF90VikqcuiV9dPh596+a98Um+Xw+5eWkq+MJOU53CQDgYvEm0ekuRKVSfx2t/PlafbPjaslndGbejUqO2+F0twDUYhTeqJactOolsM1z6ig3u47NvYk+MfIpr366Nm4v0o/b90oy8gcCTncLiGok3vCCFXH/0vH+rko1Wa6Zat45uXYXsKkJPym3zkJ99OMjCpj48mvuHFqsCfAKaxdXc+YfLIU3qqVr8yzlZiRp6+6SKscWn6QGGUka2rMV13gfhU3b9zjdBcAzKLzhBXtjduiLmH853Y2IDGv4sdNdOKI9Bxo63QXAU8oXV7NmnHVqcTVWNUe1xMb4NHpg+WInh/6oVjwePTCfohsAAAAADkHhjWrr2zZXE67qrAYZodPOG2QkacJVnbmPNwBX4XZiAAC4Q0Ax8lu0BRwqgZlqjoj0bZurPvkN9Nm6nSrcU6KctCR1bZ5F0g0AAAAAh0HhjYjFxvjU7fhsp7sBAEeFa7wBAHCHaFhcjanmAAAAAADYiMQbAOBJJN4AALhDwMJrswMO3f+PwhsA4EkU3gAAuIPf+OQ31oyzVrUTKaaaAwAAAABgIxJvAIAnkXgDAOAOFbcCs6YtFlcDAAAAACDqkHgDADyJxBsAAHcImBgFLLqdWMCh24lReAMAPInCGwAAd2CqOQAAAAAACIvEGwDgSSTeAAC4Q0DW3QYsYEkrkSPxBgAAAADARiTeAABPIvEGAMAdAopRwKLM2Kp2IkXhDQDwLIplAABqP7+Jkd+iVc2taidSTDUHAAAAAMBGJN4AAE9iqjkAAO4QkE8BWbW4mjPjNYk3AAAAAAA2IvEGAHgSiTcAAO4QDdd4U3gDADyJwhsAAHfwK0Z+iyZrW9VOpJhqDgAAAACAjUi8AQCeROINAIA7BIxPAWPR4moWtRMpEm8AAAAAAGxE4g0A8CQSbwAA3CFg4TXeAa7xBgAAAAAg+pB4AwA8icQbAAB3CJgYBSy6DZhV7USKwhsA4EkU3gAAuINfPvllzThrVTuRYqo5AAAAAAA2IvEGAHgSiTcAAO4QDVPNSbwBAAAAALARiTcAwJNIvAEAcAe/rLs2229JK5Gj8AYAeBKFNwAA7sBUcwAAAAAAEBaJNwDAk0i8AQBwB7+Jkd+ipNqqdiJF4g0AAAAAgI1IvAEAnkTiDQCAOxj5FLBocTVjUTuRovAGAHgShTcAAO7AVHMAAAAAABBWtRPvgoICFRQUyO936s5n3kBiYh9jjNNdiFr83MKNojXxZrw+NiY3/djpLkStoRt/73QXjqhO4Dj1PujxLZtPVYlvj2P9qS5+bu3jhp9bNyreVixpvQLGp4CxZpy1qp1IVTvxHj58uFatWqUlS5bY2R8AAHAUGK8BAKh9uMYbAOBJ0Zp4AwAQbfyKkd+iq6StaidSXOMNAAAAAICNSLwBAJ5E4g0AgDtEwzXeFN4AAE+i8AYAwB0CilHAosnaVrUTKaaaAwAAAABgIxJvAIBnkVIDAFD7+Y1PfoumiFvVTqRIvAEAAAAAsBGJNwDAk7jGGwAAd2BxNQAAXIrCGwAAdzAmRgFjzWRtY1E7kWKqOQAAAAAANiLxBgB4Eok3AADu4JdPflm0uJpF7USKxBsAAAAAABuReAMAPInEGwAAdwgY6xZFCxhLmokYhTcAwJMovAEAcIeAhYurWdVOpJhqDgAAAACAjUi8AQCeROINAIA7BORTwKJF0axqJ1Ik3gAAAAAAVGHChAlq37690tPTlZ6erm7duulf//pXxO2QeAMAPInEGwAAd/Abn/wWLa4WaTuNGzfW3//+d51wwgmSpBdeeEHnnXeeli9frpNOOqna7VB4AwAAAABQhYEDB4Y8fuCBBzRhwgQtWrSIwhsAgCMh8QYAwB3sWNW8qKgoZH9iYqISExPDPtfv9+v1119XcXGxunXrFtF5ucYbAOBJFYW3lRsAALBeQD4FjEXbb4urNWnSRBkZGcFt7Nixhz3/V199pdTUVCUmJuqPf/yjZsyYofz8/IheA4k3AAAAAMBTNm3apPT09ODjcGl3q1attGLFCu3atUtvvvmmBg8erPnz50dUfFN4AwA8ianmAAC4g7HwdmLmt3YqVimvjoSEhODial26dNGSJUv0+OOP6+mnn672eZlqDgAAAABANRljtH///oieQ+INAPAkEm8AANyh4vpsq9qKxJ133ql+/fqpSZMm2rNnj6ZOnap58+Zp1qxZEbVD4Q0A8CQKbwAA3MGOVc2ra9u2bbr66qu1ZcsWZWRkqH379po1a5b69OkTUTsU3gAAAAAAVGHSpEmWtEPhDQDwJBJvAADcwcmp5lZhcTUAAAAAAGxE4g0A8CQSbwAA3CFg4e3ErGonUhTeAABPovAGAMAdmGoOAAAAAADCIvEGAHgSiTcAAO5A4g0AAAAAAMIi8QYAeBKJNwAA7hANiTeFNwDAsyiWAQCo/aKh8GaqOQAAAAAANiLxBgB4ElPNAQBwByPr7r9tLGklciTeQC0Sc9Av7jEx/BIPAEBtFPAFQh4b+R3qCQC3IPEGapG8+unaUFgkSWpWP8Ph3gDRjcQbQE396tut7b4NqmfytDVmjfb79jndJSCqcY03AEvVy0xRvYxkNciqo+PSkpzuDgAAOIzv4j6RJK2O/cThngBwAxJvoBYp8wd0YuPjFBcTozJ/QHGx/G0MsAuJN4AaMz7t9hVqVcw8Fft+Kb9olP8FALaJhsSbwhuoRZZ9v02btu+RJDWrn66TWzZwuEdA9KLwBlBTdUymepf+ryQp/0BPzU4oUIn2ONwrIHpFQ+FNnAYAAAAAgI1IvAEAnkTiDQCAO5B4AwAAAACAsEi8AQCeROINAIA7GOOTsSiptqqdSFF4AwA8icIbAAB3CMingEW3DrCqnUgx1RwAAAAAABuReAMAPInEGwAAd2BxNQAAAAAAEBaJNwDAk0i8AQBwBxZXAwDApSi8AQBwB6aaAwAAAACAsEi8AQCeROINAIA7RMNUcxJvAAAAAABsROINAPAkEm8AANzBWHiNN4k3AAAAAABRiMQbAOBJJN4AALiDkWSMdW05gcIbAOBJFN4AALhDQD75ZNHtxCxqJ1JMNQcAAAAAwEYk3gAATyLxBgDAHbidGAAAAAAACIvEGwDgSSTeAAC4Q8D45LMoqbbqtmSRovAGAHgShTcAAO5gjIWrmju0rDlTzQEAAAAAsBGJNwDAk0i8AQBwBxZXAwAAAAAAYZF4AwA8i5QaAIDaLxoSbwpvAIAnMdUcAAB3iIZVzZlqDgAAAACAjUi8AQCeROINAIA7cDsxAAAAAAAQFok3AMCTSLwBAHCH8sTbqsXVLGkmYiTeAAAAAADYiMQbAOBJJN4AALgDtxMDAMClKLwBAHAH89tmVVtOYKo5AAAAAAA2IvEGAHgSiTcAAO4QDVPNSbwBAAAAALARiTcAwJNIvAEAcIkouMibwhsA4EkU3gAAuISFU83FVHMAAAAAAKIPiTcAwJNIvAEAcAdjyjer2nICiTcAAAAAADaqduJdUFCggoIC+f1+O/sDwIWMU386BGrgxx9/VJMmTaI28T50vL5xUzclpCY43Kvo89HCk5zuQtQ6vdtKp7sQtYZu/L3TXYhaax7Md7oLUWn/vl2SPHY7seHDh2vVqlVasmSJnf0BAOCYqCi8rdxqA8ZrAEDUMT5rNwcw1RwAAAAAABuxuBoAwJOidao5AADRhsXVAAAAAABAWCTeAABPIvEGAMAlzG+bVW05gMIbAOBJFN4AALiDp1Y1BwAAAAAAkSPxBgB4Eok3AAAu4tAUcauQeAMAAAAAYCMSbwCAJ5F4AwDgDlzjDQAAAAAAwiLxBgB4Eok3AAAuwe3EAABwL4plAADcwPfbZlVbxx5TzQEAAAAAsBGJNwDAk5hqDgCAS0TBVHMSbwAAAAAAbETiDQDwJBJvAABcIgoSbwpvAIAnUXgDAOASxle+WdWWA5hqDgAAAACAjUi8AQCeROINAIA7GFO+WdWWE0i8AQAAAACwEYk3AMCTSLwBAHAJFlcDAMCdKLwBAHAJFlcDAAAAAADhkHgDADyJxBsAAHfwmfLNqracQOINAAAAAICNSLwBAJ5E4g0AgEtEweJqJN4AAAAAANiIxBsA4Ekk3gAAuEQUrGpO4Q0A8CQKbwAAXIKp5gAAAAAAIBwSbwCAJ5F4AwDgEiTeAAAAAAAgHBJvAIAnkXgDAOASUZB4U3gDADyJwhsAAJeIglXNmWoOAAAAAICNSLwBAJ5E4g0AgDv4TPlmVVtOIPEGAAAAAMBGJN4AAE8i8QYAwCWiYHE1Em+gFomN/e8/ybhY/nkCdqoovK3cAHiD31cW/NooIL9KHewNADuNHTtWp5xyitLS0pSTk6Pzzz9fq1evjrgdfrMHapHjczOCXzfPzXSuIwAA4LBKfHu0Jab8F++fYlap1FficI8A2GX+/PkaPny4Fi1apDlz5qisrExnnXWWiouLI2qHqeZALZKZmqTcrDr6uehXffbtFqe7ExXiYn1qkZupxvXSVLK/TJ+u2ux0l6JGQlyMTmh0nHKz6rgy7WWqOYCjsTp2geoHTlRGoIHOODDU6e5EhV2+rfo+7lPt8+1W67LTVT9wvNNdqrbfXZHkdBfC2rjpZ32+dI327dvvdFdqxCcLF1eL8PhZs2aFPJ48ebJycnK0dOlSnX766dVuh8IbqGVaN83Shys2aXeZO//HWBvtKNqqbzbu0AmNjtPuYt5XK23f/avSUuJ1YqPjlJWWrOSEOCXExzrdLQCwXVFMobb5vleuaeXYNaPRJsPUV5MDbbUp5mvFKUEZpr7TXaq+HKc7EF5OToY6tM/Td99v0YoVa1Va6tfOX/Y63S1HFRUVhTxOTExUYmLiEZ+3e/duSVJWVlZE52OqOVDLZNap3X8xdaP42Bg1qZemrFTeW6slxseqZL9fy74v1H+WbdCWne4axLm+G8DR2BOzw+kuRJ2dvp/0Y+xKGfmd7krU2fnLXp2U30RXXnGGBp1/qtPdiYzxWbtJatKkiTIyMoLb2LFjj9wNY3TLLbfotNNOU9u2bSN6CSTeQC3j80ntmtd1uhtRIzYmRk1y0pQQF6sDpX7eWwslxMWqcb00zf58vUr9Aae7AwDHXGHMWpWK67utsitmq3bEbJQkxZo47fYVOtyj6vv5w9qdzm/a9LNycjJ0Vp+OTnel1ti0aZPS09ODj6uTdt9000368ssv9cknn0R8PgpvoJbx+Xxq2TiyqSuonoT4WN5bBHGNN4CjtTPmR+2M+dHpbkSlwti1KtRap7tRbWuW5TvdhSPKyck48kG1lQ23E0tPTw8pvI/kT3/6k95991199NFHaty4ccSnpfAGAHgShTcAAC7h4H28jTH605/+pBkzZmjevHlq3rx5jU5L4Q0AAAAAQBWGDx+uV199Ve+8847S0tK0detWSVJGRoaSk5Or3Q6FNwDAk0i8AQBwB5+x8HZiEbYzYcIESVLPnj1D9k+ePFlDhgypdjsU3gAAAAAAVMEYayp+Cm8AgCeReAMA4BIOXuNtFQpvAIAnUXgDAOASUVB4xzhzWgAAAAAAvIHEGwDgSSTeAAC4g5OLq1mFxBsAAAAAABuReAMAPInEGwAAlzC+8s2qthxA4Q0A8CQKbwAAXILF1QAAAAAAQDgk3gAATyLxBgDAHVhcDQAAAAAAhEXiDQDwJBJvAABcIgqu8abwBgB4EoU3AAAuYeFUcxZXAwAAAAAgCpF4AwA8icQbAACXiIKp5iTeAAAAAADYiMQbAOBJJN4AALgEiTcAAAAAAAiHxBsA4Ekk3gAAuIPPwlXNLVsdPUIU3gAAT6LwBgAAxwpTzQEAAAAAsBGJNwDAk0i8AQBwCRZXAwAAAAAA4ZB4AwA8icQbAAB3YHE1AABcjGIZAACXcKhgtgpTzQEAAAAAsBGJNwDAk5hqDgCAS7C4GgAAAAAACIfEGwDgSSTeAAC4A4urAQDgUhTeAAC4BFPNAQAAAABAOCTeAABPIvEGAMAdomGqOYk3AAAAAAA2IvEGAHgSiTcAAC7BNd4AAAAAACAcEm8AgCeReAMA4BJRkHhTeAMAPInCGwAAd4iGxdWqXXgXFBSooKBAfr/fzv4AcCEKDvsY49DoANc6dLxeO7614uKTHO5VFDrd6Q5Er8lNP3a6C1Fr6MbfO90FwLOqfY338OHDtWrVKi1ZssTO/gAAcExUJN5WbrUB4zUAIOoYizcHsLgaAAAAAAA24hpvAIAncY03AAAuweJqAAC4E4U3AADuEA2LqzHVHAAAAAAAG5F4AwA8icQbAACXiIKp5iTeAAAAAADYiMQbAOBJJN4AALhDNFzjTeENAPAkCm8AAFyCqeYAAAAAACAcEm8AgCeReAMA4BIk3gAAAAAAIBwSbwCAJ5F4AwDgDr7fNqvacgKJNwAAAAAANiLxBgB4Eok3AAAuEQXXeFN4AwA8icIbAAB3iIb7eDPVHAAAAAAAG5F4AwA8i5QaAAAXiIKp5iTeAAAAAADYiMQbAOBJXOMNAICLOJRUW4XCGwDgSRTeAAC4A4urAQAAAACAsEi8AQCeROINAIBLsLgaAAAAAAAIh8QbAOBJJN4AALhDNFzjTeENAPAkCm8AAFyCqeYAAAAAACAcEm8AgCeReAMA4A7RMNWcxBsAAAAAABuReAMAPInEGwAAl4iCa7wpvAEAnkThDQCAS0RB4c1UcwAAAAAAbETiDQDwJBJvAADcgcXVAAAAAABAWCTeAABPIvEGAMAluMYbAAAAAACEQ+INAPAkEm8AANzBZ4x8xpqo2qp2IkXhDQDwJApvAABcgqnmAAAAAAAgHBJvAMBRSYiP1a8Hysq/jot1uDfVR+INAPCSX0sOHPR1qYM9iRy3EwMAeF7LxsdJktKSE9Qgq47DvQEAAFVZu3abdu7cK0launSNw73xHgpvAMBRaVwvTanJ8WrTNMtVqW9F4m3lBgBAbWWM0eLPvtOOHXv03febne5OZIzFmwMovAEAR2X7rn3Kq5+u2Fif9u13z9Q1Cm8AgJekpSVr/4FSrVy1UY0b13W6OxGpmGpu1eYErvEGAByVpd9tC17j3aVlfeXVz3C4RwAA4FB5TevprD4dJUm7dxdr0uS5znbIYyi8AQCexOJqAAC4BLcTAwAAAAAA4ZB4AwA8icQbAAB3iIbbiVF4AwA8icIbAACXYKo5AAAAAAAIh8QbAOBZpNQAALiDU1PErULiDQAAAACAjUi8AQCexDXeAAC4hDHlm1VtOYDEGwAAAAAAG5F4AwA8icQbAAB34HZiAAC4FIU3AAAuwe3EAAAAAABAOCTeAABPIvEGAMAdfIHyzaq2nEDiDQAAAACAjUi8AQCeROINAIBLRME13hTeAABPovAGAMAdomFVc6aaAwAAAABgIwpvAIAnVSTeVm4AAMAGxli7Reijjz7SwIED1bBhQ/l8Pr399tsRt0HhDQAAAADAYRQXF6tDhw568skna9wG13gDADyJa7wBAHAHO67xLioqCtmfmJioxMTEKp/Tr18/9evX76jOS+INAPAkppoDAOASxuJNUpMmTZSRkRHcxo4da+tLIPEGAAAAAHjKpk2blJ6eHnx8uLTbKhTeAABPYqo5AADuYMdU8/T09JDC225MNQcAAAAAwEYk3gAATyLxBgDAJWp4G7DDtuUACm8AAAAAAA5j7969WrNmTfDxunXrtGLFCmVlZalp06bVaoPCGwDgSSTeAAC4gx3XeEfi888/V69evYKPb7nlFknS4MGDNWXKlGq1QeENAPAkCm8AAFzioNuAWdJWhHr27ClzlFPUWVwNAAAAAAAbkXgDADyJxBsAAHdweqq5FUi8AQAAAACwEYk3AMCTSLwBAHCJgCnfrGrLARTeAABPovAGAMAlHF5czQpMNQcAAAAAwEYk3gAATyLxBgDAHXyycHE1a5qJGIk3AAAAAAA2IvEGAHgWKTUAAC5gTPlmVVsOoPAGAHgSU80BAHAH7uMNAAAAAADCIvEGAHgSiTcAAC7B7cQAAAAAAEA4JN4AAE8i8QYAwB18xshn0aJoVrUTqWoX3gUFBSooKJDf77ezP55nHPpBAI4GP7dwo2gtvA8dr1Pe+1xxvniHexWFTv+d0z2IWmc37Oh0F6LYHqc7ELU2P1Y7xoBwGmf/92t/kk+bT6/9fS7b5ZNmSQr8tlnBqnYiVO2p5sOHD9eqVau0ZMkSO/sDAACOAuM1AAC1D1PNAQCeFK2JNwAA0SYappqzuBoAAAAAADYi8QYAeBKJNwAALsHtxAAAAAAAQDgk3gAATyLxBgDAJYwp36xqywEU3gAAT6LwBgDAHXymfLOqLScw1RwAAAAAABuReAMAPInEGwAAl4iCqeYk3gAAAAAA2IjEGwDgSSTeAAC4gy9QvlnVlhMovAEAnkThDQCASzDVHAAAAAAAhEPiDQDwJBJvAABcwvy2WdWWA0i8AQAAAACwEYk3AMCTSLwBAHAHnzHyWXRttlXtRIrCGwDgSRTeAAC4BIurAQAAAACAcEi8AQCeROINAIBLGElW3X+bxdUAAAAAAIg+JN4AAE8i8QYAwB2iYXE1Em8AAAAAAGxE4g0A8CQSbwAAXMLIwlXNrWkmUhTeAADPolgGAMAFuJ0YAAAAAAAIh8QbAOBJTDUHAMAlApKsGmatui1ZhEi8AQAAAACwEYk3AMCTSLwBAHCHaLidGIU3AMCTKLwBAHAJFlcDAAAAAADhkHgDADyJxBsAAJcg8QYAAAAAAOGQeAMAPInEGwAAl4iCxJvCGwDgSRTeAAC4BPfxBgAAAAAA4ZB4AwA8icQbAAB3iIb7eJN4AwAAAABgIxJvAIAnkXgDAOASLK4GAPA841fdX5Yqaf/PSqxzolSvjxQT63SvAAAAag0KbwBAza16V3+YN1JJJdvKH6+UNK+h1PdBKf9cR7t2JCTeAAAv2XWg5KCvf3WwJzUQMJLPoqQ6wDXeAAA3WfWuNP0aJVYU3RWKtkjTryn/fi1WUXhbuQEAUFt9t2e7fty3S5I0d9v3znYmUhVTza3aHEDhDQCIXMAvzbpNkqnitpq/DWizbi8/DgAA1Aqzt3ynDcW/aHXRdqe74jlMNQcARG7Dp1LR5jAHGKnop/Ljmv/+mHUrEkw1BwB4zard27Rjf7HT3agBK5NqEm8AgFvs3XbkYyI5DgAAHBPbSvY63QVPIvEGAEQutb61xzmAxBsAAJfgdmIAAE/K6y6lNyxfSK3KKVu+8u/ndT/WPas2Cm8AAFwiYGTZFHFWNQcAuEZMbPktwySp0vJqvz3u+3fu5w0AACAKbwBATeWfK13yopSeG7o/vWH5fpfcx5vbiQEAUMuZgLWbA5hqDgCoufxzpdYDylcv37ut/JruvO4k3QAAAAeh8AYAHJ2Y2Fp7y7BwuMYbAACXYHE1AADcicIbAACXYHE1AAAAAAAQDok3AMCTSLwBAHCJKJhqTuINAAAAAICNSLwBAJ5FSg0AgAsYWZh4W9NMpCi8AQCexFRzAABcgqnmAAAAAAAgHBJvAIAnkXgDAOASgYCkgIVtHXsk3gAAAAAA2IjEGwDgSSTeAAC4BNd4AwAAAACAcEi8AQCeROINAIBLREHiTeENAPAkCm8AAFwiYGTZDbgDTDUHAAAAACDqkHgDADyJxBsAAHcwJiBjrLkNmFXtRIrEGwAAAAAAG5F4AwA8icQbAACXMMa6a7NZXA0AgGOHwhsAAJcwFi6uxn28AQAAAACIPiTeAABPIvEGAMAlAgHJZ9GiaCyuBgAAAABA9CHxBgB4Eok3AAAuEQXXeFN4AwA8icIbAAB3MIGAjEVTzbmPNwAAAAAAUYjEGwDgSSTeAAC4RBRMNSfxBgAAAADARiTeAABPIvEGAMAlAkbykXgDAAAAAIDDIPEGAHgSiTcAAC5hjCSLViPndmIAABw7FN4AALiDCRgZi6aaG6aaAwAAAAAQfUi8AQCeROINAIBLmICsm2puUTsRIvEGAMBBTz31lJo3b66kpCSdfPLJ+vjjj53uEgAAOMTRjtcU3gAAT6pIvK3cIjVt2jTdfPPNuuuuu7R8+XL9/ve/V79+/bRx40YbXjEAAO5kAsbSLVJWjNcU3gAAT6oNhfejjz6q6667Ttdff73atGmj8ePHq0mTJpowYYINrxgAAJcyAWu3CFkxXkd8jXfFKnBFRUWRPhUAAMft2bNHkvXjWEV7h7abmJioxMTESscfOHBAS5cu1e233x6y/6yzztKnn3561P2pGK/LVCo5s4BrVAuUlDjdhahVZkqd7gIQMf6fYI9AyX5J1o5lZSr/f8yxHq+rXXgXFBSooKBABw4ckCQ1adKk2icBAKC2sWMcS01NrdTu6NGjNWbMmErH/vzzz/L7/apfv37I/vr162vr1q017sOh4/Un+meN20IYt7/jdA+iFhdawJX4f4KtrB7LnBivq114Dx8+XMOHD1cgEFDLli21dOlSVnC1wSmnnKIlS5Y43Y2oxHtrD95X+/De2sMYo06dOmnZsmWKibH2iitjTKWxsaq/nh/s0OOraiMSjNfHBv8+7cN7ax/eW/vw3trDrjHbifE64qnmMTExSkhIUEZGRqRPRTXExsYqPT3d6W5EJd5be/C+2of31j5JSUnKzMx0tA9169ZVbGxspb+WFxYWVvqrek0wXtuLf5/24b21D++tfXhv7eP0mG3VeF2jPxsMHz68Jk9DNfDe2of31h68r/bhvbVPbXhvExISdPLJJ2vOnDkh++fMmaPu3btbco7a8DqjFe+tfXhv7cN7ax/eW/s4/d5aNV77TMXqKwAA4JiaNm2arr76ak2cOFHdunXTM888o2effVYrV65UXl6e090DAACyZryOeKo5AACwxqWXXqodO3bovvvu05YtW9S2bVv985//pOgGAKAWsWK8JvEGAAAAAMBG1i7nCgAAAAAAQlB4AwAAAABgIwpvAAAAAABsROENAAAAAICNKLwBAAAAALARhTcAAAAAADai8AYAAAAAwEYU3gAAAAAA2IjCGwAAAAAAG1F4AwAAAABgIwpvAAAAAABsROENAAAAAICN4pzuAKKD3+9XaWmp090AqhQfH6/Y2FinuwEAjmO8Rm3HmI1oReGNo2KM0datW7Vr1y6nuwKElZmZqQYNGsjn8zndFQA45hiv4SaM2YhGFN44KhWDeE5OjlJSUvgfJGodY4z27dunwsJCSVJubq7DPQKAY4/xGm7AmI1oRuGNGvP7/cFBPDs72+nuAIeVnJwsSSosLFROTg5T2AB4CuM13IQxG9GKxdVQYxXXiKWkpDjcE+DIKn5OubYRgNcwXsNtGLMRjSi8cdSYrgY34OcUgNfx/0G4BT+riEYU3gAAAAAA2IjCG6hCs2bNNH78+LDHbN26VX369FGdOnWUmZl5TPp1NKZMmRK2n+vXr5fP59OKFSuOWZ8AADhajNkA3IDF1WC5Nz/+7pie78Lftzym56vw2GOPacuWLVqxYoUyMjIc6cOx1rNnT82fP7/S/v79+2vmzJmWneeBBx7QzJkztWLFCiUkJFS6/c2UKVM0dOjQKp+7bds25eTkWNYXAIhmjNnRizEbqF0ovIEa+uGHH3TyySfrxBNPtKS90tJSxcfHW9KWXd566y0dOHAg+HjHjh3q0KGDLr74YkvPc+DAAV188cXq1q2bJk2aVOn7l156qfr27Ruyb8iQISopKWEABwBUwpjNmA04janm8Jw9e/boyiuvVJ06dZSbm6vHHntMPXv21M0331zpuCuuuEKpqalq2LChnnjiieD3mjVrpjfffFMvvviifD6fhgwZIkkaM2aMmjZtqsTERDVs2FB//vOfD9uPMWPGqGPHjnr++efVokULJSYmyhijWbNm6bTTTlNmZqays7N1zjnn6Icffgg+r2J62VtvvaVevXopJSVFHTp00MKFC0PanzJlipo2baqUlBQNGjRIO3bsOOr3LisrSw0aNAhuc+bMUUpKyhEH8QULFuiMM85QSkqKjjvuOJ199tn65ZdfDnv8vffeqxEjRqhdu3ZVfj85OTmkH7Gxsfrggw903XXXHdXrAwDULozZNceYDdQuFN7wnFtuuUULFizQu+++qzlz5ujjjz/WsmXLKh330EMPqX379lq2bJnuuOMOjRgxQnPmzJEkLVmyRH379tUll1yiLVu26PHHH9cbb7yhxx57TE8//bS+//57vf3224cdhCqsWbNG06dP15tvvhm8Tqu4uFi33HKLlixZorlz5yomJkaDBg1SIBAIee5dd92lkSNHasWKFWrZsqUuv/xylZWVSZIWL16sa6+9VsOGDdOKFSvUq1cv/fWvf434vWrWrJnGjBlz2O9PmjRJl112merUqXPYY1asWKHevXvrpJNO0sKFC/XJJ59o4MCB8vv9ksp/2Tja1UtffPFFpaSk6KKLLjqqdgAAtQtjdvUxZgO1G1PN4Sl79uzRCy+8oFdffVW9e/eWJE2ePFkNGzasdGyPHj10++23S5JatmypBQsW6LHHHlOfPn1Ur149JSYmBv+KK0kbN25UgwYNdOaZZyo+Pl5NmzZV165dw/bnwIEDeumll1SvXr3gvgsvvDDkmEmTJiknJ0erVq1S27Ztg/tHjhypAQMGSCr/a/NJJ52kNWvWqHXr1nr88cd19tlnh/T/008/1axZsyJ6v44//njVrVu3yu999tln+vrrr6ucVnawcePGqUuXLnrqqaeC+0466aTg1xkZGWrVqlVE/TrU888/ryuuuELJyclH1Q4AoPZgzGbMBqIJiTc8Ze3atSotLQ0ZXA83iHTr1q3S42+++eawbV988cX69ddf1aJFC91www2aMWNG8K/Zh5OXlxcygEvl16FdccUVatGihdLT09W8eXNJ5b8kHKx9+/bBr3NzcyVJhYWFkqRvvvmmyv5Hau7cubrpppuq/N6kSZPUtm3bI/6iUvHX88MZNGiQvv3224j7VmHhwoVatWoVU9YAIMowZkeGMRuo3Si84SnGGEmqNE2qYv+RhJte1aRJE61evVoFBQVKTk7WsGHDdPrpp6u0tPSwz6lqutfAgQO1Y8cOPfvss1q8eLEWL14sSSELpEgKWdSlol8VU9uq+3pqat++fZo6daquv/76Ix5r91+0n3vuOXXs2FEnn3yyrecBABxbjNnWYMwGagcKb3jK8ccfr/j4eH322WfBfUVFRfr+++8rHbto0aJKj1u3bh22/eTkZJ177rn6xz/+oXnz5mnhwoX66quvqt2/HTt26JtvvtGoUaPUu3dvtWnTJuyCJoeTn59fZf+tMn36dO3fv19XXXXVEY9t37695s6da9m5D7Z3715Nnz6dv5wDQBRizLYGYzZQO3CNNzwlLS1NgwcP1v/93/8pKytLOTk5Gj16tGJiYir9ZXzBggUaN26czj//fM2ZM0evv/562PteTpkyRX6/X6eeeqpSUlL00ksvKTk5WXl5edXu33HHHafs7Gw988wzys3N1caNG4PXfEXiz3/+s7p37x7s/+zZsyO+VkySevfurUGDBlWaujZp0iSdf/75ys7OPmIbd9xxh9q1a6dhw4bpj3/8oxISEvThhx/q4osvVt26dTVjxgzdcccdIVPXNm7cqJ07d2rjxo3y+/3BRWxOOOEEpaamBo+bNm2aysrKdOWVV0b82gAAtRtjdmQYs4HajcQbnvPoo4+qW7duOuecc3TmmWeqR48eatOmjZKSkkKOu/XWW7V06VJ16tRJ999/vx555BGdffbZh203MzNTzz77rHr06BH8i/F7771XrYGuQkxMjKZOnaqlS5eqbdu2GjFihB566KGIX+Pvfvc7Pffcc3riiSfUsWNHzZ49W6NGjYq4nR9++EE///xzyL7vvvtOn3zySbX/Yt2yZUvNnj1bX3zxhbp27apu3brpnXfeUVxc+d/9du/erdWrV4c855577lGnTp00evRo7d27V506dVKnTp30+eefhxw3adIkXXDBBTruuOMifm0AgNqPMbv6GLOB2s1n7L6wBFGrpKRE69atU/PmzSsNgG5SXFysRo0a6ZFHHmH6UxSLlp9XAIhUNP3/jzHbG6LpZxaowFRzeM7y5cv17bffqmvXrtq9e7fuu+8+SdJ5553ncM8AAMDBGLMBRAsKb3jSww8/rNWrVyshIUEnn3yyPv7448Pe+xIAADiHMRtANKDwhud06tRJS5cudbobAADgCBizAUQLFlcDAAAAAMBGFN4AAAAewHq6cAt+VhGNKLwBAACiWHx8vCRp3759DvcEqJ6Kn9WKn10gGnCNNwAAQBSLjY1VZmamCgsLJUkpKSny+XwO9wqozBijffv2qbCwUJmZmYqNjXW6S4BlKLwBAACiXIMGDSQpWHwDtVlmZmbwZxaIFhTeAAAAUc7n8yk3N1c5OTkqLS11ujvAYcXHx5N0IypReAMAAHhEbGwsRQ0AOIDF1YCDDBkyROeff75l7fXs2VM333yzZe0BAAAAcB8SbzjOHzD6bN1OFe4pUU5akro2z1JsjLsXfSktLWUlTgAAAACSSLzhsFlfb9FpD36gy59dpL9MXaHLn12k0x78QLO+3mLred944w21a9dOycnJys7O1plnnqn/+7//0wsvvKB33nlHPp9PPp9P8+bNkyTddtttatmypVJSUtSiRQvdfffdIdfIjRkzRh07dtTzzz+vFi1aKDExUYMHD9b8+fP1+OOPB9tbv369ra8LAAAAQO1D4g3HzPp6i258eZnMIfu37i7RjS8v04SrOqtv21zLz7tlyxZdfvnlGjdunAYNGqQ9e/bo448/1jXXXKONGzeqqKhIkydPliRlZWVJktLS0jRlyhQ1bNhQX331lW644QalpaXp//2//xdsd82aNZo+fbrefPNNxcbGKi8vT99//73atm2r++67T5JUr149y18PAAAAgNqNwhuO8AeM7n1vVaWiW5KMJJ+ke99bpT75DSyfdr5lyxaVlZXpggsuUF5eniSpXbt2kqTk5GTt37+/0i0sRo0aFfy6WbNmuvXWWzVt2rSQwvvAgQN66aWXQorrhIQEpaSkcEsMAAAAwMOYag5HfLZup7bsLjns942kLbtL9Nm6nZafu0OHDurdu7fatWuniy++WM8++6x++eWXsM954403dNppp6lBgwZKTU3V3XffrY0bN4Yck5eXR6INAAAAoBIKbziicM/hi+6aHBeJ2NhYzZkzR//617+Un5+vJ554Qq1atdK6deuqPH7RokW67LLL1K9fP73//vtavny57rrrLh04cCDkuDp16ljeVwAAAADux1RzOCInLcnS4yLl8/nUo0cP9ejRQ/fcc4/y8vI0Y8YMJSQkyO/3hxy7YMEC5eXl6a677gru27BhQ7XOU1V7AAAAALyFwhuO6No8S7kZSdq6u6TK67x9khpklN9azGqLFy/W3LlzddZZZyknJ0eLFy/W9u3b1aZNG5WUlOjf//63Vq9erezsbGVkZOiEE07Qxo0bNXXqVJ1yyimaOXOmZsyYUa1zNWvWTIsXL9b69euVmpqqrKwsxcQw0QQAAADwEioAOCI2xqfRA/MllRfZB6t4PHpgvi33805PT9dHH32k/v37q2XLlho1apQeeeQR9evXTzfccINatWqlLl26qF69elqwYIHOO+88jRgxQjfddJM6duyoTz/9VHfffXe1zjVy5EjFxsYqPz9f9erVq3RdOAAAAIDo5zPGVBU4AkdUUlKidevWqXnz5kpKqtmU8Flfb9G9760KWWgtNyNJowfm23IrMXiXFT+vAAAAQE0w1RyO6ts2V33yG+izdTtVuKdEOWnl08vtSLoBAAAAwAkU3nBcbIxP3Y7PdrobAAAAAGALrvEGAAAAAMBGFN4AAAAAANiIwhsAAAAAABtReAMAAAAAYCMKbwAAAAAAbEThDQAAAACAjSi8AQAAAACwEYU3YJExY8aoY8eOTncDAAAAQC1D4Q0AAAAAgI3inO4AoIBf2vCptHeblFpfyusuxcQ63SsAAAAAsASJN5y16l1pfFvphXOkN68r/+/4tuX7bWSM0bhx49SiRQslJyerQ4cOeuONNyRJ8+bNk8/n09y5c9WlSxelpKSoe/fuWr16dUgbf//731W/fn2lpaXpuuuuU0lJia19BgAAAOBOFN5wzqp3penXSEWbQ/cXbSnfb2PxPWrUKE2ePFkTJkzQypUrNWLECF111VWaP39+8Ji77rpLjzzyiD7//HPFxcXp2muvDX5v+vTpGj16tB544AF9/vnnys3N1VNPPWVbfwEAAAC4l88YY5zuBNyppKRE69atU/PmzZWUlBTZkwP+8mT70KI7yCelN5Ru/sryaefFxcWqW7euPvjgA3Xr1i24//rrr9e+ffv0P//zP+rVq5f+85//qHfv3pKkf/7znxowYIB+/fVXJSUlqXv37urQoYMmTJgQfP7vfvc7lZSUaMWKFZb2F9Y4qp9XAAAA4CiQeMMZGz4NU3RLkpGKfio/zmKrVq1SSUmJ+vTpo9TU1OD24osv6ocffgge1759++DXubm5kqTCwkJJ0jfffBNStEuq9BgAAAAAJBZXg1P2brP2uAgEAgFJ0syZM9WoUaOQ7yUmJgaL7/j4+OB+n88X8lwAAAAAqC4Sbzgjtb61x0UgPz9fiYmJ2rhxo0444YSQrUmTJtVqo02bNlq0aFHIvkMfAwAAAIBE4g2n5HUvv4a7aIukqpYZ+O0a77zulp86LS1NI0eO1IgRIxQIBHTaaaepqKhIn376qVJTU5WXl3fENv7yl79o8ODB6tKli0477TS98sorWrlypVq0aGF5fwEAAAC4G4U3nBETK/V9sHz1cvkUWnyXT+tW37/bdj/v+++/Xzk5ORo7dqzWrl2rzMxMde7cWXfeeWe1ppNfeuml+uGHH3TbbbeppKREF154oW688Ub9+9//tqW/AAAAANyLVc1RY5asEr3qXWnWbaELraU3Ki+688+1pqOAWNUcAAAAziHxhrPyz5VaDyhfvXzvtvJruvO625Z0AwAAAMCxRuEN58XESs1/73QvAAAAAMAWrGoOAAAAAICNKLwBAAAAALARhTeOGuvzwQ34OQUAAIBTKLxRY/Hx8ZKkffv2OdwT4Mgqfk4rfm4BAACAY4XF1VBjsbGxyszMVGFhoSQpJSVFPp/P4V4BoYwx2rdvnwoLC5WZmanYWFbMBwAAwLHFfbxxVIwx2rp1q3bt2uV0V4CwMjMz1aBBA/44BAAAgGOOwhuW8Pv9Ki0tdbobQJXi4+NJugEAAOAYCm8AAAAAAGzE4moAAAAAANiIwhsAAAAAABtReAMAAAAAYCMKbwAAAAAAbEThDQAAAACAjSi8AQAAAACwEYU3AAAAAAA2+v+p7CRzkadL+AAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 1000x700 with 4 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "class GBFS(object):\n",
    "    def __init__(self, heuristic):\n",
    "        \n",
    "        self.heuristic = heuristic\n",
    "        self.visited = None\n",
    "        self.fringe = None\n",
    "    \n",
    "    def solve(self, problem: Problem):\n",
    "        \n",
    "        # YOUR CODE HERE: make sure to initialise self.visited and self.fringe here!\n",
    "        self.fringe = PriorityQueue()\n",
    "        self.visited = set()\n",
    "        end_node = problem.get_end_node()\n",
    "        self.fringe.put(self.heuristic(problem.get_start_node(), end_node), problem.get_start_node())\n",
    "\n",
    "        while self.fringe.has_elements():\n",
    "            current = self.fringe.get()\n",
    "            \n",
    "            if problem.is_end(current):\n",
    "                return current\n",
    "\n",
    "            if current in self.visited:\n",
    "                continue\n",
    "\n",
    "            self.visited.add(current)\n",
    "            for successor in problem.successors(current):\n",
    "                self.fringe.put(self.heuristic(successor, end_node), successor)\n",
    "            \n",
    "            \n",
    "        return None\n",
    "\n",
    "\n",
    "# reset maze before search\n",
    "maze.reset()\n",
    "gbfs_rand = GBFS(random_heuristic)\n",
    "gbfs_rand_sol = gbfs_rand.solve(maze)\n",
    "if gbfs_rand_sol is not None: \n",
    "    gbfs_rand_sol.pretty_print()\n",
    "    maze.visualize(sequences=[('gbfs rand', \"\".join(maze.get_action_sequence(gbfs_rand_sol)))])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "### Basic checks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "da3db1e5026088e700feea53e49c52c3",
     "grade": true,
     "grade_id": "cell-33642543af658c78",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# this is a testing cell, do not edit or delete\n",
    "assert(gbfs_rand_sol is not None), \"GBFS did not return a solution\"\n",
    "assert(gbfs_rand_sol.state == (4, 4)), \"GBFS did not return the expected solution\"\n",
    "\n",
    "assert(gbfs_rand.visited is not None), \"it seems you did not correctly initialize the visited set\"\n",
    "assert(gbfs_rand.fringe is not None), \"it seems you did not correctly initialize the fringe\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "maze.reset()\n",
    "gbfs_cb_sol = GBFS(cityblock_heuristic).solve(maze)\n",
    "assert(gbfs_cb_sol.depth == 7), \"the solution found by city block-GBFS does not have the expected length\"\n",
    "assert(gbfs_cb_sol.cost == 17), \"the solution found by city block-GBFS does not have the expected cost\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "### Check different mazes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "c4a4cbe8458bcabe3abe68ddcfbe8d30",
     "grade": true,
     "grade_id": "cell-ae3066efbf1abd87",
     "locked": true,
     "points": 0.5,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "tiny1 = factory.create_problem_from_json(json_path='boards/tiny1.json')\n",
    "assert(GBFS(cityblock_heuristic).solve(tiny1).get_action_sequence_hash() == '0123d362bf2df8f84e7c41197827be005159724c07774ef32d9f15373a440091'), \"City block-GBFS did not return the expected solution path\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "bf20896a24cdbfb8c9017d689fb1f686",
     "grade": true,
     "grade_id": "cell-db152198f4515796",
     "locked": true,
     "points": 0.5,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "tiny1 = factory.create_problem_from_json(json_path='boards/tiny1.json')\n",
    "assert(GBFS(euclidean_heuristic).solve(tiny1).get_action_sequence_hash() == 'c283a9803562a0053fc1ea0c30d421e0b4a7a9f599c699d74477cbeeffec23bc'), \"Euclidean-GBFS did not return the expected solution path\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a62d879a6138939e7cb466f60f56cfe0",
     "grade": true,
     "grade_id": "cell-8fdbf6cce29d0e2a",
     "locked": true,
     "points": 0.5,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "tiny2 = factory.create_problem_from_json(json_path='boards/tiny2.json')\n",
    "assert(GBFS(cityblock_heuristic).solve(tiny2).get_action_sequence_hash() == 'f5cdd7625f98bc258a52c4c332d534d9c2d9bfebc34ef4c26c11b85e15803363'), \"City block-GBFS did not return the expected solution path\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "c617df180e1c7f73e54718c88661e24d",
     "grade": true,
     "grade_id": "cell-1db11bbb4212e83d",
     "locked": true,
     "points": 0.5,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "tiny2 = factory.create_problem_from_json(json_path='boards/tiny2.json')\n",
    "assert(GBFS(chebyshev_heuristic).solve(tiny2).get_action_sequence_hash() == '919c8fb20a877be0b0da8aeda03a070febb5607348e0c7f733c2405fdb9b4f74'), \"Chebyshev-GBFS did not return the expected solution path\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "d5c02b3e9f7fc8522f91023cb92d8d73",
     "grade": true,
     "grade_id": "cell-0e8036184401604e",
     "locked": true,
     "points": 0.5,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "tiny3 = factory.create_problem_from_json(json_path='boards/tiny3.json')\n",
    "assert(GBFS(cityblock_heuristic).solve(tiny3).get_action_sequence_hash() == '0123d362bf2df8f84e7c41197827be005159724c07774ef32d9f15373a440091'), \"City block-GBFS did not return the expected solution path\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ad55064773115aa4d3020f95be536dc9",
     "grade": true,
     "grade_id": "cell-900e396bd7fa8958",
     "locked": true,
     "points": 0.5,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "tiny3 = factory.create_problem_from_json(json_path='boards/tiny3.json')\n",
    "assert(GBFS(euclidean_heuristic).solve(tiny3).get_action_sequence_hash() == 'c283a9803562a0053fc1ea0c30d421e0b4a7a9f599c699d74477cbeeffec23bc'), \"Euclidean-GBFS did not return the expected solution path\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing A*\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "9336ab8123003b4c601e75b88ab5c28b",
     "grade": false,
     "grade_id": "cell-d2df9b0e3d90cf00",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "state (4, 4) was reached following the sequence ['R', 'D', 'D', 'D', 'D', 'R', 'R'] (cost: 16, depth: 7)\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA94AAAIxCAYAAAC7CGDIAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjUsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvWftoOwAAAAlwSFlzAAAPYQAAD2EBqD+naQAATU1JREFUeJzt3Xl4FFW+xvG3shOymUggLCYgsgmCiDogozC4sLqMjo4ruN07LPcqiKOOCyjOIDg6jBph9CqiooAycUNRFFlUQERxlChuLCpLEIRAIJB0n/tHJj02CSEdqlKpru/neerRrlSfOunucPLLe+qUZYwxAgAAAAAAjohxuwMAAAAAAEQzCm8AAAAAABxE4Q0AAAAAgIMovAEAAAAAcBCFNwAAAAAADqLwBgAAAADAQRTeAAAAAAA4iMIbAAAAAAAHUXgDAAAAAOAgCm9AkmVZtdoWLVqkRYsWybIsvfjii47365NPPtEZZ5yh9PR0WZalKVOmhM6/aNGiiNuL5LnDhg1TXl5exOcAgGjTUMeI+rRp0yaNHz9eq1evtr3ta665Rv379w/bV93456bCwkKNHz9e69evd7UfB1u/fr0sy9JTTz3ldlcarEcffbTa16e61+6pp56SZVl1ep+feOIJtWjRQiUlJXXvLKJanNsdABqCZcuWhT2eMGGC3n33XS1cuDBsf6dOnfTxxx/XW7+uueYalZSUaNasWTrqqKOUl5en5ORkLVu2TJ06daq3fgCAnzXUMaI+bdq0SXfffbfy8vLUrVs329r95JNPNGPGDK1YsSJsf3Xjn5sKCwt19913q0+fPq735ZdycnK0bNkyHXvssW53pcF69NFHdfTRR2vYsGFh++1+7YYOHapJkyZp8uTJuvvuu21pE9GFwhuQ9Ktf/SrscZMmTRQTE1Nlf337/PPPdf3112vAgAFh+93uFwD4SUMdI6LBfffdp1NOOUU9evQI23+o8a+uysrKZFmW4uKi61ffxMREPod1ZPdrFxcXp//+7//WhAkTdMsttyg5Odm2thEdmGoO1FFZWZluv/12NW/eXGlpaTrzzDO1du3aKse9/fbb6tevn9LS0pScnKzTTjtN77zzTo1tV051Ki8v19SpU0PTGKVDTxf/6KOPdO655yozM1NJSUk68cQTNWfOnFp9L0899ZTat2+vxMREdezYUU8//XTtXgQAQLWcHCMq7dy5UzfddJPatGmjxMREZWdna+DAgfryyy9Dx+zYsUMjRoxQixYtlJCQoDZt2uj222/X/v37w9p64YUXdOqppyo9PV3Jyclq06aNrrnmGkkV487JJ58sSbr66qtDY9L48eMlSd99951+//vfq3nz5kpMTFTTpk3Vr1+/w05L37p1qwoKCnTllVeG9tU0/kkVBfl5552no446SklJSerWrZtmzJgR1m7lOPnMM8/opptuUosWLZSYmKhvvvnmkH2ZOnWqunbtqpSUFKWmpqpDhw7605/+FOrT7373O0lS3759Q3365RTl2ryP48ePl2VZ+uSTT/Tb3/5WaWlpSk9P1xVXXKFt27aFHZuXl6fBgweroKBAJ5xwgpKSktSmTRs99NBDYcdVN1268jxr1qzRpZdeqvT0dDVt2lTXXHONdu3aFfb8nTt36tprr1VmZqZSUlI0aNAgfffdd2Hvb002btyoK664QtnZ2aHfIR544AEFg8EqffzrX/+qBx98UK1bt1ZKSop69uyp5cuXH/Yc27Zt04gRI9SpUyelpKQoOztbv/nNb7R06dLDPjcvL09r1qzR4sWLQ+9b5YyFSKbp1/bn9PLLL1dxcbFmzZp12DbhPxTeQB396U9/0oYNG/R///d/euyxx/T1119ryJAhCgQCoWOeffZZnX322UpLS9OMGTM0Z84cZWZm6pxzzqnxF6tBgwaFpjZedNFFWrZsWZWpjr/07rvv6rTTTtPOnTs1bdo0vfzyy+rWrZsuueSSww4oTz31lK6++mp17NhRc+fO1R133KEJEyZUmUIJAKg9J8cISdq9e7d69+6tf/zjH7r66qv16quvatq0aWrXrp02b94sSSotLVXfvn319NNPa8yYMZo3b56uuOIKTZ48Wb/97W9DbS1btkyXXHKJ2rRpo1mzZmnevHm66667VF5eLknq3r27pk+fLkm64447QmPSddddJ0kaOHCgVq1apcmTJ2vBggWaOnWqTjzxRO3cubPG7+Gtt95SWVmZ+vbtG9pX0/i3du1a9erVS2vWrNFDDz2kf/7zn+rUqZOGDRumyZMnV2n/tttu08aNGzVt2jS9+uqrys7OrrYfs2bN0ogRI3TGGWeooKBAL730kkaPHh26VnfQoEH6y1/+IknKz88P9WnQoEGSIn8fL7jgArVt21Yvvviixo8fr5deeknnnHOOysrKwo5bvXq1brzxRo0ePVoFBQXq1auXbrjhBv31r3+t8XWtdOGFF6pdu3aaO3eubr31Vj333HMaPXp06OvBYFBDhgzRc889p1tuuUUFBQU69dRTq1xvfyjbtm1Tr1699NZbb2nChAl65ZVXdOaZZ2rs2LEaNWpUlePz8/O1YMECTZkyRTNnzlRJSYkGDhxY5Y8BB9uxY4ckady4cZo3b56mT5+uNm3aqE+fPodds6agoEBt2rTRiSeeGHrfCgoKavX9VYrk/W3WrJk6dOigefPmRXQO+IQBUMXQoUNN48aNq/3au+++aySZgQMHhu2fM2eOkWSWLVtmjDGmpKTEZGZmmiFDhoQdFwgETNeuXc0pp5xy2H5IMiNHjqz2/O+++25oX4cOHcyJJ55oysrKwo4dPHiwycnJMYFAoNrnBgIB07x5c9O9e3cTDAZDz1u/fr2Jj483ubm5h+0jAPhNQxgj7rnnHiPJLFiw4JDHTJs2zUgyc+bMCds/adIkI8m89dZbxhhj/vrXvxpJZufOnYdsa+XKlUaSmT59etj+n376yUgyU6ZMqbG/1Rk+fLhp1KhR2PhTqbrx7/e//71JTEw0GzduDNs/YMAAk5ycHOp/5Xtw+umn16ofo0aNMhkZGTUe88ILL1QZe42J7H0cN26ckWRGjx4dduzMmTONJPPss8+G9uXm5hrLsszq1avDjj3rrLNMWlqaKSkpMcYYs27duirvS+V5Jk+eHPbcESNGmKSkpNDrPW/ePCPJTJ06Ney4iRMnGklm3LhxNb4mt956q5FkVqxYEbZ/+PDhxrIss3bt2rA+dunSxZSXl4eO+/DDD40k8/zzz9d4noOVl5ebsrIy069fP3PBBRcc9vjjjz/enHHGGVX2V/faTZ8+3Ugy69atM8bU7ef08ssvN02bNo3oe4I/kHgDdXTuueeGPT7hhBMkSRs2bJAkffDBB9qxY4eGDh2q8vLy0BYMBtW/f3+tXLnSlpUvv/nmG3355Ze6/PLLJSnsXAMHDtTmzZurnd4oVaQHmzZt0mWXXRY2lS83N1e9evU64r4BgF85PUa88cYbateunc4888xDHrNw4UI1btxYF110Udj+ykWmKtO6ymnkF198sebMmaMff/yx1t9nZmamjj32WN1///168MEH9cknn4RNM67Jpk2b1KRJk7DxpyYLFy5Uv3791KpVq7D9w4YN0969e6vMDLvwwgtr1e4pp5yinTt36tJLL9XLL7+sn376qVbPk+r2PlaO15UuvvhixcXF6d133w3bf/zxx6tr165h+y677DIVFxfXahG/6j6DpaWlKioqkiQtXrw4dP5fuvTSSw/btlTxfnTq1EmnnHJK2P5hw4bJGFNl5tygQYMUGxsb1h/pPz8TNZk2bZq6d++upKQkxcXFKT4+Xu+8846++OKLWvW1rury/mZnZ6uoqCg0YwSoROEN1FFWVlbY48TEREnSvn37JFVcuyZVTJWLj48P2yZNmiRjTGj61JGoPM/YsWOrnGfEiBGSdMhfIrZv3y6pYmrUwarbBwCoHafHiG3btqlly5Y19mH79u1q1qxZlcI2OztbcXFxoTHg9NNP10svvaTy8nJdddVVatmypTp37qznn3/+sN+nZVl65513dM4552jy5Mnq3r27mjRpov/93//V7t27a3zuvn37lJSUdNhz/PL7ycnJqbK/efPmoa//UnXHVufKK6/Uk08+qQ0bNujCCy9Udna2Tj31VC1YsOCwz63L+3jw+BoXF6esrKwq/a9pbD742Ooc7jO4fft2xcXFKTMzM+y4pk2bHrbtyudH8n4crj+H8uCDD2r48OE69dRTNXfuXC1fvlwrV65U//79D/vcI1WX9zcpKUnGGJWWljraN3hPdC3tCDQgRx99tCTp4YcfPuSqmbUd3Gpznttuuy3smr1fat++fbX7KwfBLVu2VPladfsAAPY40jGiSZMm+uGHH2o8R1ZWllasWCFjTFjxXZnGVfZBks477zydd9552r9/v5YvX66JEyfqsssuU15ennr27FnjeXJzc/XEE09Ikr766ivNmTNH48eP14EDBzRt2rRDPu/oo4+O6PZrWVlZoevXf2nTpk2h9n6ptkm6VLFo3NVXX62SkhItWbJE48aN0+DBg/XVV18pNzf3kM+ry/u4ZcsWtWjRIvS4vLxc27dvr1KY1jQ2H3xsXWRlZam8vFw7duwIK75rO/5H+n7U1bPPPqs+ffpo6tSpYfsP94cdO9Tl/d2xY4cSExOVkpLieP/gLSTegENOO+00ZWRkqLCwUD169Kh2S0hIOOLztG/fXscdd5w+/fTTQ54nNTX1kM/NycnR888/L2NMaP+GDRv0wQcfHHHfAADVO9IxYsCAAfrqq69qXAizX79+2rNnj1566aWw/ZV3rujXr1+V5yQmJuqMM87QpEmTJFXcZ7tyv3T4dLJdu3a644471KVLl8MW1R06dND27dsPu7jWL7+fhQsXhgq7X34/ycnJttwaqnHjxhowYIBuv/12HThwQGvWrJF06O+/Lu/jzJkzwx7PmTNH5eXl6tOnT9j+NWvW6NNPPw3b99xzzyk1NVXdu3c/4u/1jDPOkCTNnj07bH9tV+Tu16+fCgsLq7zPTz/9tCzLCls070hYlhV6/Sv961//qnHR2V9KTEysczJel/f3u+++U6dOnep0PkQ3Em/AISkpKXr44Yc1dOhQ7dixQxdddJGys7O1bds2ffrpp9q2bVuVv97W1T/+8Q8NGDBA55xzjoYNG6YWLVpox44d+uKLL/Txxx/rhRdeqPZ5MTExmjBhgq677jpdcMEFuv7667Vz506NHz+eqeYA4KAjHSNuvPFGzZ49W+edd55uvfVWnXLKKdq3b58WL16swYMHq2/fvrrqqquUn5+voUOHav369erSpYvee+89/eUvf9HAgQND14ffdddd+uGHH9SvXz+1bNlSO3fu1N///nfFx8eHirNjjz1WjRo10syZM9WxY0elpKSoefPm+umnnzRq1Cj97ne/03HHHaeEhAQtXLhQ//rXv3TrrbfW+Br06dNHxhitWLFCZ5999mFfs3Hjxum1115T3759dddddykzM1MzZ87UvHnzNHnyZKWnp0fwDvzH9ddfr0aNGum0005TTk6OtmzZookTJyo9PT10/Xvnzp0lSY899phSU1OVlJSk1q1bKysrK+L38Z///Kfi4uJ01llnac2aNbrzzjvVtWvXKtdaN2/eXOeee67Gjx+vnJwcPfvss1qwYIEmTZpkyz2i+/fvr9NOO0033XSTiouLddJJJ2nZsmWhP8zExNScz40ePVpPP/20Bg0apHvuuUe5ubmaN2+eHn30UQ0fPlzt2rU74j5K0uDBgzVhwgSNGzdOZ5xxhtauXat77rlHrVu3rtV11F26dNGsWbM0e/ZstWnTRklJSerSpUutzh3pz2kwGNSHH36oa6+9ts7fL6KYa8u6AQ1YbVasfeGFF8L2V7c6pjHGLF682AwaNMhkZmaa+Ph406JFCzNo0KAqz6+OarmquTHGfPrpp+biiy822dnZJj4+3jRr1sz85je/MdOmTTvsc//v//7PHHfccSYhIcG0a9fOPPnkk2bo0KGsag4A1WgoY8TPP/9sbrjhBnPMMceY+Ph4k52dbQYNGmS+/PLL0DHbt283f/jDH0xOTo6Ji4szubm55rbbbjOlpaWhY1577TUzYMAA06JFC5OQkGCys7PNwIEDzdKlS8PO9/zzz5sOHTqY+Pj40KrXW7duNcOGDTMdOnQwjRs3NikpKeaEE04wf/vb38JWsK5OIBAweXl5ZsSIEVW+Vt34Z4wxn332mRkyZIhJT083CQkJpmvXrlVe00O9B4cyY8YM07dvX9O0aVOTkJBgmjdvbi6++GLzr3/9K+y4KVOmmNatW5vY2Ngq72Vt3sfK1cZXrVplhgwZYlJSUkxqaqq59NJLzdatW8POlZubawYNGmRefPFFc/zxx5uEhASTl5dnHnzwwbDjalrVfNu2bWHHHrxitzHG7Nixw1x99dUmIyPDJCcnm7POOsssX77cSDJ///vfD/vabdiwwVx22WUmKyvLxMfHm/bt25v7778/dDeVX/bx/vvvr/J81WL19P3795uxY8eaFi1amKSkJNO9e3fz0ksv1fr3lPXr15uzzz7bpKamGkmh59RmVfNKtf05feedd0LvMXAwy5hfzC8FAAAA6skDDzygP//5z/rxxx/VqFEjt7vjqPHjx+vuu+/Wtm3bDnv9c15enjp37qzXXnutnnr3H88995wuv/xyvf/++9zhJEJXXnmlvvvuO73//vtudwUNEFPNAQAA4IqRI0fqkUceUX5+vsaOHet2d3zn+eef148//qguXbooJiZGy5cv1/3336/TTz+dojtC3377rWbPnl3jugvwNwpvAAAAuCIpKUnPPPNMaBE31K/U1FTNmjVL9957r0pKSpSTk6Nhw4bp3nvvdbtrnrNx40Y98sgj6t27t9tdQQPFVHMAAAAAABzE7cQAAHDBkiVLNGTIEDVv3lyWZVW55RMAAGh4Jk6cKMuydOONN0b0PApvAABcUFJSoq5du+qRRx5xuysAAKAWVq5cqccee0wnnHBCxM/lGm8AAFwwYMAADRgwwO1uAACAWtizZ48uv/xyPf7443VaByHiwjsYDGrTpk1KTU2VZVkRnxAAADcZY0K384mJsXfilzGmytiYmJioxMREW89TG4zXAACvc2rMrst4PXLkSA0aNEhnnnmms4V3fn6+8vPzdeDAAX377bcRnwgAgGiXkpKiPXv2hO0bN26cxo8fX299YLwGAESTZtmx2lIUsLXNSMfrWbNm6eOPP9bKlSvrfM6IVzXftWuXMjIy9P333ystLa3OJwYAwA0//vijOnXq5Fj7B4+PtUm8LctSQUGBzj//fNv6UTleb/g4T2kpLOlit+Hf93S7C1FraqtlbncBQAPx45ZydT59o9atylVaqj1jWfHuoFqftKHW4/X333+vHj166K233lLXrl0lSX369FG3bt00ZcqUWp834qnmlZF8WloahTcAwHOKi4tD/2/nFOzKv2M3lPExNF6nxNj2ywr+IyElwe0uRC0+rwAqFe+p+PcgLdX+say24/WqVatUVFSkk046KbQvEAhoyZIleuSRR7R//37FxsYeth0WVwMA+JJlWbZf+xzhJDIAAFALARNUwKYhNmCCER3fr18/ffbZZ2H7rr76anXo0EG33HJLrYpuicIbAABX7NmzR998803o8bp167R69WplZmbqmGOOcbFnAACgUmpqqjp37hy2r3HjxsrKyqqyvyYU3gAAX3I78f7oo4/Ut2/f0OMxY8ZIkoYOHaqnnnrK1n4BAOBlQRkFZU/kbVc7kaLwBgD4khOFdyT69OnD1HQAAGohqKAimyBec1tHatGiRRE/h9UrAAAAAABwEIk3AMCX3E68AQBA7QSMUcCmWWJ2tRMpEm8AAAAAABxE4g0A8CUSbwAAvIHF1QAA8CgKbwAAvCEoo4DHC2+mmgMAAAAA4CASbwCAL5F4AwDgDdEw1ZzEGwAAAAAAB5F4AwB8icQbAABv4HZiAAAAAACgRiTeAABfIvEGAMAbgv/e7GrLDRTeAABfovAGAMAbAjbeTsyudiLFVHMAAAAAABxE4g0A8CUSbwAAvCFgKja72nIDiTcAAAAAAA4i8QYA+BKJNwAA3sDiagAAeBSFNwAA3hCUpYDsGbODNrUTKaaaAwAAAADgIBJvAIAvkXgDAOANQVOx2dWWG0i8AQAAAABwEIk3AMCXSLwBAPCGgI3XeNvVTqQovAEAvkThDQCAN0RD4c1UcwAAAAAAHETiDQDwJRJvAAC8IWgsBY1NtxOzqZ1IkXgDAAAAAOAgEm8AgG/ZmXgb49L9SQAAiHJc4w0AAAAAAGpE4g0A8CW7r/HmenEAAJwRUIwCNmXGAVtaiRyFNwDAlyi8AQDwBmPj4mqGxdUAAAAAAIg+JN4AAF8i8QYAwBuiYXE1Cm9ELBA0+nDdDhXtLlV2apJOaZ2p2Bh+4QQAAACA6lB4IyLzP9+su18t1OZdpaF9OelJGjekk/p3znGxZwAQGRJvAAC8IWBiFDA2La7m0t0/ucYbtTb/880a/uzHYUW3JG3ZVarhz36s+Z9vdqlnABC5ysLbzg0AANgvKEtBxdi0MdUcDVggaHT3q4Wq7g9ElfvuKPhcTRJjmHZeB5Yl5WanKSMlye2uAACiSJJJ1TGBrkoxR+mAtc/t7tTKp0Wd3O5CjVISflRe2luKjTngdlcAeAiFN2rlw3U7qiTdB/up5IDeXrNZbbOS66lX0eWbH3eqeVZjdTwmiwIcqAdMNYcfdC3vr6bBY93uRkS+2+V2Dw5v7Y5L1O6oF9Q6fT4FOFAPWFwNvlG0u+aiu1JxqVu3pI8OP+3ap0Wffi/LspSbnaZubbPd7hIAwMPiTaLbXYhKZYHGWvPTNfpi+5WSZXRm7nA1itvudrcANGAU3qiV7NTaJbCtsxsrJ6uxw72JPjGylNs0TRu3FeuHbXskGQWCQbe7BUQ1Em/4weq4N3Rs4BSlmEzPTDXv3qhhF7ApCT8qp/EyLfnhAQVNfMU1dy4t1gT4hb2Lq7nzA0vhjVo5pXWmctKTtGVXabVjiyWpWXqSru7Tnmu8j8D323a73QXANyi84Qd7Yrbr05g33O5GREY0X+p2Fw5r94HmbncB8JWKxdXsGWfdWlyNVc1RK7ExlsYNqVjs5OCPauXjcUM6UXQDAAAAwEEovFFr/TvnaOoV3dUsPXzaebP0JE29ojv38QbgKdxODAAAbwgqRgGbtqBLJTBTzRGR/p1zdFanZvpw3Q4V7S5VdmqSTmmdSdINAAAAAIdA4Y2IxcZY6nlsltvdAIAjwjXeAAB4QzQsrsZUcwAAAAAAHETiDQDwJRJvAAC8IWjjtdlBl+7/R+ENAPAlCm8AALwhYCwFjD3jrF3tRIqp5gAAAAAAOIjEGwDgSyTeAAB4Q+WtwOxpi8XVAAAAAACIOiTeAABfIvEGAMAbgiZGQZtuJxZ06XZiFN4AAF+i8AYAwBuYag4AAAAAAGpE4g0A8CUSbwAAvCEo+24DFrSllciReAMAAAAA4CASbwCAL5F4AwDgDUHFKGhTZmxXO5Gi8AYA+BbFMgAADV/AxChg06rmdrUTKaaaAwAAAADgIBJvAIAvMdUcAABvCMpSUHYtrubOeE3iDQAAAACAg0i8AQC+ROINAIA3RMM13hTeAABfovAGAMAbAopRwKbJ2na1EymmmgMAAAAA4CASbwCAL5F4AwDgDUFjKWhsWlzNpnYiReINAAAAAICDSLwBAL5E4g0AgDcEbbzGO8g13gAAAAAARB8SbwCAL5F4AwDgDUETo6BNtwGzq51IUXgDAHyJwhsAAG8IyFJA9oyzdrUTKaaaAwAAAADgIBJvAIAvkXgDAOAN0TDVnMQbAAAAAAAHkXgDAHyJxBsAAG8IyL5rswO2tBI5Cm8AgC9ReAMA4A1MNQcAAAAAADUi8QYA+BKJNwAA3hAwMQrYlFTb1U6kSLwBAAAAAHAQiTcAwJdIvAEA8AYjS0GbFlczNrUTKQpvAIAvUXgDAOANTDUHAAAAAAA1qnXinZ+fr/z8fAUCbt35zB9ITJxjjHG7C1GLzy28KFoTb8br+jH9mKVudyFqXb3x12534bAaB49Sv188HrPpVJVau13rT23xuXWOFz63XlSytUTSegWNpaCxZ5y1q51I1TrxHjlypAoLC7Vy5Uon+wMAAI4A4zUAAA0P13gDAHwpWhNvAACiTUAxCth0lbRd7USKa7wBAAAAAHAQiTcAwJdIvAEA8IZouMabwhsA4EsU3gAAeENQMQraNFnbrnYixVRzAAAAAAAcROINAPAtUmoAABq+gLEUsGmKuF3tRIrEGwAAAAAAB5F4AwB8iWu8AQDwBhZXAwDAoyi8AQDwBmNiFDT2TNY2NrUTKaaaAwAAAADgIBJvAIAvkXgDAOANAVkKyKbF1WxqJ1Ik3gAAAAAAOIjEGwDgSyTeAAB4Q9DYtyha0NjSTMQovAEAvkThDQCANwRtXFzNrnYixVRzAAAAAAAcROINAPAlEm8AALwhKEtBmxZFs6udSJF4AwAAAABQjalTp+qEE05QWlqa0tLS1LNnT73xxhsRt0PiDQDwJRJvAAC8IWAsBWxaXC3Sdlq2bKn77rtPbdu2lSTNmDFD5513nj755BMdf/zxtW6HwhsAAAAAgGoMGTIk7PGf//xnTZ06VcuXL6fwBgDgcEi8AQDwBidWNS8uLg7bn5iYqMTExBqfGwgE9MILL6ikpEQ9e/aM6Lxc4w0A8KXKwtvODQAA2C8oS0Fj0/bvxdVatWql9PT00DZx4sRDnv+zzz5TSkqKEhMT9Yc//EEFBQXq1KlTRN8DiTcAAAAAwFe+//57paWlhR7XlHa3b99eq1ev1s6dOzV37lwNHTpUixcvjqj4pvAGAPgSU80BAPAGY+PtxMy/26lcpbw2EhISQour9ejRQytXrtTf//53/eMf/6j1eZlqDgAAAABALRljtH///oieQ+INAPAlEm8AALyh8vpsu9qKxJ/+9CcNGDBArVq10u7duzVr1iwtWrRI8+fPj6gdCm8AgC9ReAMA4A1OrGpeW1u3btWVV16pzZs3Kz09XSeccILmz5+vs846K6J2KLwBAAAAAKjGE088YUs7FN4AAF8i8QYAwBvcnGpuFxZXAwAAAADAQSTeAABfIvEGAMAbgjbeTsyudiJF4Q0A8CUKbwAAvIGp5gAAAAAAoEYk3gAAXyLxBgDAG0i8AQAAAABAjUi8AQC+ROINAIA3REPiTeENAPAtimUAABq+aCi8mWoOAAAAAICDSLwBAL7EVHMAALzByL77bxtbWokciTfQgMT84hf3mBh+iQcAoCEKWsGwx0YBl3oCwCtIvIEGJLdpmjYUFUuS8pqmu9wbILqReAOoq33WLm2zNqiJydWWmG+039rrdpeAqMY13gBs1SQjWU3SG6lZZmMdlZrkdncAAMAhfBX3niRpbex7LvcEgBeQeAMNSHkgqONaHqW4mBiVB4KKi+VvY4BTSLwB1JmxtMsqUmHMIpVYP1dcNMo/AYBjoiHxpvAGGpCPv96q77ftliTlNU3TSe2audwjIHpReAOoq8YmQ/3K/luS1OlAH72VkK9S7Xa5V0D0iobCmzgNAAAAAAAHkXgDAHyJxBsAAG8g8QYAAAAAADUi8QYA+BKJNwAA3mCMJWNTUm1XO5Gi8AYA+BKFNwAA3hCUpaBNtw6wq51IMdUcAAAAAAAHkXgDAHyJxBsAAG9gcTUAAAAAAFAjEm8AgC+ReAMA4A0srgYAgEdReAMA4A1MNQcAAAAAADUi8QYA+BKJNwAA3hANU81JvAEAAAAAcBCJNwDAl0i8AQDwBmPjNd4k3gAAAAAARCESbwCAL5F4AwDgDUaSMfa15QYKbwCAL1F4AwDgDUFZsmTT7cRsaidSTDUHAAAAAMBBJN4AAF8i8QYAwBu4nRgAAAAAAKgRiTcAwJdIvAEA8IagsWTZlFTbdVuySFF4AwB8icIbAABvMMbGVc1dWtacqeYAAAAAADiIxBsA4Esk3gAAeAOLqwEAAAAAgBqReAMAfIuUGgCAhi8aEm8KbwCALzHVHAAAb4iGVc2Zag4AAAAAgINIvAEAvkTiDQCAN3A7MQAAAAAAUCMSbwCAL5F4AwDgDRWJt12Lq9nSTMRIvAEAAAAAcBCJNwDAl0i8AQDwBm4nBgCAR1F4AwDgDebfm11tuYGp5gAAAAAAOIjEGwDgSyTeAAB4QzRMNSfxBgAAAADAQSTeAABfIvEGAMAjouAibwpvAIAvUXgDAOARNk41F1PNAQAAAACIPiTeAABfIvEGAMAbjKnY7GrLDSTeAAAAAAA4qNaJd35+vvLz8xUIBJzsDwAPMm796RCogx9++EGtWrWK2sT74PF6+Pc9lZCS4HKvos+SZce73YWodXrPNW53IWpdvfHXbnchan0zqZPbXYhK+/fulOSz24mNHDlShYWFWrlypZP9AQCgXlQW3nZuDQHjNQAg6hjL3s0FTDUHAAAAAMBBLK4GAPClaJ1qDgBAtGFxNQAAAAAAUCMSbwCAL5F4AwDgEebfm11tuYDCGwDgSxTeAAB4g69WNQcAAAAAAJEj8QYA+BKJNwAAHuLSFHG7kHgDAAAAAOAgEm8AgC+ReAMA4A1c4w0AAAAAAGpE4g0A8CUSbwAAPILbiQEA4F0UywAAeIH1782utuofU80BAAAAAHAQiTcAwJeYag4AgEdEwVRzEm8AAAAAABxE4g0A8CUSbwAAPCIKEm8KbwCAL1F4AwDgEcaq2OxqywVMNQcAAAAAwEEk3gAAXyLxBgDAG4yp2Oxqyw0k3gAAAAAAOIjEGwDgSyTeAAB4BIurAQDgTRTeAAB4BIurAQAAAACAmpB4AwB8icQbAABvsEzFZldbbiDxBgAAAADAQSTeAABfIvEGAMAjomBxNRJvAAAAAAAcROINAPAlEm8AADwiClY1p/AGAPgShTcAAB7BVHMAAAAAAFATEm8AgC+ReAMA4BEk3gAAAAAAoCYk3gAAXyLxBgDAI6Ig8abwBgD4EoU3AAAeEQWrmjPVHAAAAAAAB5F4AwB8icQbAABvsEzFZldbbiDxBgAAAADAQSTeAABfIvEGAMAjomBxNRJvoAGJjf3Pj2RcLD+egJMqC287NwD+ELDKQ/9vFFRAZS72BoCTJk6cqJNPPlmpqanKzs7W+eefr7Vr10bcDr/ZAw3IsTnpof9vnZPhXkcAAMAhlVq7tTmm4hfvH2MKVWaVutwjAE5ZvHixRo4cqeXLl2vBggUqLy/X2WefrZKSkojaYao50IBkpCSpeVaKYmMspSUnuN0dIKox1RzAkVgb+76aBo/TV7EfuN0VIOpZsnFxtQiPnz9/ftjj6dOnKzs7W6tWrdLpp59e63YovIEGZG9pmVo2SVGMFaO9+8uUnBjvdpcAAMBBYkysJKMvYhcpRrGyTIyMFXS7WwAiUFxcHPY4MTFRiYmJh33erl27JEmZmZkRnY+p5kAD8vn6n/Thl1u0/ItN+mLDdre7A0Q9ru8GUBeNTJr6lF2r4wO/UZ+ya5Woxm53CYhuxrJ3k9SqVSulp6eHtokTJx6+G8ZozJgx6t27tzp37hzRt0DiDQAAAADwle+//15paWmhx7VJu0eNGqV//etfeu+99yI+H4U3AMCXuMYbAACPcOB2YmlpaWGF9+H8z//8j1555RUtWbJELVu2jPi0FN4AAF+i8AYAwCNcvI+3MUb/8z//o4KCAi1atEitW7eu02kpvAEAAAAAqMbIkSP13HPP6eWXX1Zqaqq2bNkiSUpPT1ejRo1q3Q6FNwDAl0i8AQDwBsvYeDuxCNuZOnWqJKlPnz5h+6dPn65hw4bVuh0KbwAAAAAAqmGMPRU/hTcAwJdIvAEA8AgXr/G2C4U3AMCXKLwBAPCIKCi8Y9w5LQAAAAAA/kDiDQDwJRJvAAC8wc3F1exC4g0AAAAAgINIvAEAvkTiDQCARxirYrOrLRdQeAMAfInCGwAAj2BxNQAAAAAAUBMSbwCAL5F4AwDgDSyuBgAAAAAAakTiDQDwJRJvAAA8Igqu8abwBgD4EoU3AAAeYeNUcxZXAwAAAAAgCpF4AwB8icQbAACPiIKp5iTeAAAAAAA4iMQbAOBLJN4AAHgEiTcAAAAAAKgJiTcAwJdIvAEA8AbLxlXNbVsdPUIU3gAAX6LwBgAA9YWp5gAAAAAAOIjEGwDgSyTeAAB4BIurAQAAAACAmpB4AwB8icQbAABvYHE1AAA8jGIZAACPcKlgtgtTzQEAAAAAcBCJNwDAl5hqDgCAR7C4GgAAAAAAqAmJNwDAl0i8AQDwBhZXAwDAoyi8AQDwCKaaAwAAAACAmpB4AwB8icQbAABviIap5iTeAAAAAAA4iMQbAOBLJN4AAHgE13gDAAAAAICakHgDAHyJxBsAAI+IgsSbwhsA4EsU3gAAeEM0LK5W68I7Pz9f+fn5CgQCTvYHgAdRcDjHGJdGB3jWweP1d1M6KC4+yeVeRaHT3e5A9Jp+zFK3u3BYuw8019sb/jv0+MHmK9QofruLPaqdqzf+2u0uAL5V62u8R44cqcLCQq1cudLJ/gAAUC8qE287t4aA8RoAEHWMzZsLWFwNAAAAAAAHcY03AMCXuMYbAACPYHE1AAC8icIbAABviIbF1ZhqDgAAAACAg0i8AQC+ROINAIBHRMFUcxJvAAAAAAAcROINAPAlEm8AALwhGq7xpvAGAPgShTcAAB7BVHMAAAAAAFATEm8AgC+ReAMA4BEk3gAAAAAAoCYk3gAAXyLxBgDAG6x/b3a15QYSbwAAAAAAHETiDQDwJRJvAAA8Igqu8abwBgD4EoU3AADeEA338WaqOQAAAAAADiLxBgD4Fik1AAAeEAVTzUm8AQAAAABwEIk3AMCXuMYbAAAPcSmptguFNwDAlyi8AQDwBhZXAwAAAAAANSLxBgD4Eok3AAAeweJqAAAAAACgJiTeAABfIvEGAMAbouEabwpvAIAvUXgDAOARTDUHAAAAAAA1IfEGAPgSiTcAAN4QDVPNSbwBAAAAAHAQiTcAwJdIvAEA8IgouMabwhsA4EsU3gAAeEQUFN5MNQcAAAAAwEEk3gAAXyLxBgDAG1hcDQAAAAAA1IjEGwDgSyTeAAB4BNd4AwAAAACAmpB4AwB8icQbAABvsIyRZeyJqu1qJ1IU3gAAX6LwBgDAI5hqDgAAAAAAakLiDTQgCXGx//n/+NgajgRwpEi8AdRVfMxeWQrIKFYxVpliY0rd7hIQ1bidGABbtW2RIUtSjGXp2OYZbncHAABUIylup1qlLpQk5aa9qYTYEpd7BKChI/EGGpCURgk6pmmaYmMsJSfGu90dIKqReAM4Eu0zZ+vHPb9Wu6NecLsrQPSLgmu8KbyBBuTnPaXKTE1SjGVp5579ykhJdLtLQNSi8AZQV+XBJO0+0FLtj5qlXftbKzG2WLExB9zuFhC1omGqOYU30IB8/cPP+n7bbklSXtM0ndSumcs9AgAAB9tXnqnlm8eHHvfPu0qNYra71yEADR6FNwDAl0i8AQDwiCiYas7iagAAAAAAOIjEGwDgSyTeAAB4A9d4AwDgURTeAAB4BFPNAQAAAABATUi8AQC+RUoNAIA3uDVF3C4k3gAAAAAAOIjEGwDgS1zjDQCARxhTsdnVlgtIvAEAAAAAcBCJNwDAl0i8AQDwBm4nBgCAR1F4AwDgEdxODAAAAAAA1ITEGwDgSyTeAAB4gxWs2Oxqyw0k3gAAAAAAOIjEGwDgSyTeAAB4RBRc403hDQDwJQpvAAC8IRpWNWeqOQAAAAAADqLwBgD4UmXibecGAAAcYIy9W4SWLFmiIUOGqHnz5rIsSy+99FLEbVB4AwAAAABwCCUlJerataseeeSROrfBNd4AAF/iGm8AALzBiWu8i4uLw/YnJiYqMTGx2ucMGDBAAwYMOKLzkngDAHyJqeYAAHiEsXmT1KpVK6Wnp4e2iRMnOvotkHgDAAAAAHzl+++/V1paWujxodJuu1B4AwB8ianmAAB4gxNTzdPS0sIKb6cx1RwAAAAAAAeReAMAfInEGwAAj6jjbcAO2ZYLKLwBAAAAADiEPXv26Jtvvgk9XrdunVavXq3MzEwdc8wxtWqDwhsA4Esk3gAAeIMT13hH4qOPPlLfvn1Dj8eMGSNJGjp0qJ566qlatUHhDQDwJQpvAAA84he3AbOlrQj16dNH5ginqLO4GgAAAAAADiLxBgD4Eok3AADe4PZUczuQeAMAAAAA4CASbwCAL5F4AwDgEUFTsdnVlgsovAEAvkThDQCAR7i8uJodmGoOAAAAAICDSLwBAL5E4g0AgDdYsnFxNXuaiRiJNwAAAAAADiLxBgD4Fik1AAAeYEzFZldbLqDwBgD4ElPNAQDwBu7jDQAAAAAAakTiDQDwJRJvAAA8gtuJAQAAAACAmpB4AwB8icQbAABvsIyRZdOiaHa1E6laF975+fnKz89XIBBwsj++Z1z6IABHgs8tvChaC++Dx+vkVz9SnBXvcq+i0Om/crsHUeuc5t3c7sJhpbfM0qUz//P48h7Hq2RbsXsdqrXdbncgam36W8MYA6JN+U5Lmi8p+O/NDna1E6FaTzUfOXKkCgsLtXLlSif7AwAAjgDjNQAADQ9TzQEAvhStiTcAANEmGqaas7gaAAAAAAAOIvEGAPgSiTcAAB7B7cQAAAAAAEBNSLwBAL5E4g0AgEcYU7HZ1ZYLKLwBAL5E4Q0AgDdYpmKzqy03MNUcAAAAAAAHkXgDAHyJxBsAAI+IgqnmJN4AAAAAADiIxBsA4Esk3gAAeIMVrNjsassNFN4AAF+i8AYAwCOYag4AAAAAAGpC4g0A8CUSbwAAPML8e7OrLReQeAMAAAAA4CASbwCAL5F4AwDgDZYxsmy6NtuudiJF4Q0A8CUKbwAAPILF1QAAAAAAQE1IvAEAvkTiDQCARxhJdt1/m8XVAAAAAACIPiTeAABfIvEGAMAbomFxNRJvAAAAAAAcROINAPAlEm8AADzCyMZVze1pJlIU3gAA36JYBgDAA7idGAAAAAAAqAmJNwDAl5hqDgCARwQl2TXM2nVbsgiReAMAAAAA4CASbwCAL5F4AwDgDdFwOzEKbwCAL1F4AwDgESyuBgAAAAAAakLiDQDwJRJvAAA8gsQbAAAAAADUhMQbAOBLJN4AAHhEFCTeFN4AAF+i8AYAwCO4jzcAAAAAAKgJiTcAwJdIvAEA8IZouI83iTcAAAAAAA4i8QYA+BKJNwAAHsHiagAA3wsGpA0fSHu2SilNpdxeUkys270CAABoMCi8gQakUWLcL/4/3sWeALVU+Io0/xapeNN/9qU1l/pPkjqd616/aoHEG0Bdle7aq/L9ZYpLjNeBvft1YE+p210ColvQSJZNSXWQxBvwvbYtjtLXP/6sGEvKbZqm8oBL9zuIIpYlxcZULGdhjFHApX9so5H15auKfWGopINe0+LN0pyrpIufbtDFN4U3gLrav3ufCl/5UCf87jQVvvyhjKS4Rglud8vzykvLQtOAYxPiZMV6ZzmqhAY+0+tAMOB2F44MU80B2KlRQpzaNEvXt5t3af7KdW53JypYlpTXNF3tW2XKGKM3P1rvdpeigwlo4PtjlSRTzW01jSRLmn+r1GEQ084BRKXVzy1Vx8Enq9ulv1a3S3/tdneiws8birRqxrv69t3PdMbNF6jd2d3c7lLU2Fjys97a/JW+LC5yuyu+5Z0/IwE+cVzLTLe7EFWMkdZt2aU3P1qnH3/a7XZ3osbRO1er0f6iaoruSkYq/rHi2u8GqjLxtnMD4B97d+zW12+vdrsbUeWo3GydedclOj//vxUTzx9t7XRM46N0XdtTdc2xpyjO8mIJaP6Teh/pdvBMvXrixVcdiGqNEpiIYrestEbqfXxLNc9KcbsrUSNp/0+1O3DPVmc7AgAuKt251+0uRJUDJaVaNeNdvf7HGQqWeXxqdAOzp2y/Xv1hjZ5dt0rlhksZ3cBv+EADY1lS326t3O5G1IiNiVFacoIsy1IgGOS1tUnc9x2lNbU4MKWp432pK67xBnCk1rz8oda/94Xb3YgaO3/4KbRQ3UfT39Hnc5e53KPa+350Z7e7UKOtpbu9fZ0313gDsJtlWcpMbeR2N6JSbEwMr61dOvStWL28eLOqn7JlVXw9t1d996zWKLwBHKmSbbtUsm2X292ISsWbdqh40w63u1Fr3+9t6XYXolvQxiniLi20y1RzAEDkYmIrbhkmSVWu9P734/73sbAaAACAKLwBAHXV6dyKW4al5YTvT2ve4G8lJrG4GgAAnmGC9m4uYKo5AKDuOp1bccuwDR9ULKSW0rRiejlJNwAAQAiFNwDgyMTESq29dw9brvEGAMAjWFwNAABvovAGAMAjWFwNAAAAAADUhMQbAOBLJN4AAHhEFEw1J/EGAAAAAMBBJN4AAN8ipQYAwAOMbEy87WkmUhTeAABfYqo5AAAewVRzAAAAAABQExJvAIAvkXgDAOARwaCkoI1t1T8SbwAAAAAAHETiDQDwJRJvAAA8gmu8AQAAAABATUi8AQC+ROINAIBHREHiTeENAPAlCm8AADwiaGTbDbiDTDUHAAAAACDqkHgDAHyJxBsAAG8wJihj7LkNmF3tRIrEGwAAAAAAB5F4AwB8icQbAACPMMa+a7NZXA0AgPpD4Q0AgEcYGxdX4z7eAAAAAABEHxJvAIAvkXgDAOARwaBk2bQoGourAQAAAAAQfUi8AQC+ROINAIBHRME13hTeAABfovAGAMAbTDAoY9NUc+7jDQAAAABAFCLxBgD4Eok3AAAeEQVTzUm8AQAAAABwEIk3AMCXSLwBAPCIoJEsEm8AAAAAAHAIJN4AAF8i8QYAwCOMkWTTauTcTgwAgPpD4Q0AgDeYoJGxaaq5Yao5AAAAAADRh8QbAOBLJN4AAHiECcq+qeY2tRMhEm8AAFz06KOPqnXr1kpKStJJJ52kpUuXut0lAABwkCMdrym8AQC+VJl427lFavbs2brxxht1++2365NPPtGvf/1rDRgwQBs3bnTgOwYAwJtM0Ni6RcqO8ZrCGwDgSw2h8H7wwQd17bXX6rrrrlPHjh01ZcoUtWrVSlOnTnXgOwYAwKNM0N4tQnaM1xFf4125ClxxcXGkTwUAwHW7d++WZP84Vtnewe0mJiYqMTGxyvEHDhzQqlWrdOutt4btP/vss/XBBx8ccX8qx+tylUnuLOAa1YKlpW53IWqVmzK3uwBEjH8TnBEs3S/J3rGsXBX/xtT3eF3rwjs/P1/5+fk6cOCAJKlVq1a1PgkAAA2NE+NYSkpKlXbHjRun8ePHVzn2p59+UiAQUNOmTcP2N23aVFu2bKlzHw4er9/T63VuCzW49WW3exC1uNACnsS/CY6yeyxzY7yudeE9cuRIjRw5UsFgUO3atdOqVatYwdUBJ598slauXOl2N6ISr60zeF2dw2vrDGOMTjzxRH388ceKibH3iitjTJWxsbq/nv/SwcdX10YkGK/rBz+fzuG1dQ6vrXN4bZ3h1Jjtxngd8VTzmJgYJSQkKD09PdKnohZiY2OVlpbmdjeiEq+tM3hdncNr65ykpCRlZGS42oejjz5asbGxVf5aXlRUVOWv6nXBeO0sfj6dw2vrHF5b5/DaOsftMduu8bpOfzYYOXJkXZ6GWuC1dQ6vrTN4XZ3Da+uchvDaJiQk6KSTTtKCBQvC9i9YsEC9evWy5RwN4fuMVry2zuG1dQ6vrXN4bZ3j9mtr13htmcrVVwAAQL2aPXu2rrzySk2bNk09e/bUY489pscff1xr1qxRbm6u290DAACyZ7yOeKo5AACwxyWXXKLt27frnnvu0ebNm9W5c2e9/vrrFN0AADQgdozXJN4AAAAAADjI3uVcAQAAAABAGApvAAAAAAAcROENAAAAAICDKLwBAAAAAHAQhTcAAAAAAA6i8AYAAAAAwEEU3gAAAAAAOIjCGwAAAAAAB1F4AwAAAADgIApvAAAAAAAcROENAAAAAICDKLwBAAAAAHBQnNsdgHcFAgGVlZW53Q0gIvHx8YqNjXW7GwBQbxiv4VWM2YgmFN6ImDFGW7Zs0c6dO93uClAnGRkZatasmSzLcrsrAOAYxmtEA8ZsRAsKb0SschDPzs5WcnIy/xDCM4wx2rt3r4qKiiRJOTk5LvcIAJzDeA0vY8xGtKHwRkQCgUBoEM/KynK7O0DEGjVqJEkqKipSdnY2U9gARCXGa0QDxmxEExZXQ0QqrxFLTk52uSdA3VV+frnmEUC0YrxGtGDMRrSg8EadMF0NXsbnF4Bf8O8dvI7PMKIFhTcAAAAAAA6i8AZ8aNiwYTr//PMP+fWnnnpKGRkZ9dYfAABQPcZsIDqwuBpsMXfpV/V6vgt/3a5ez2dZlgoKCmoc+PzmUFO/Jk+erJtvvtmWc5SWluoPf/iDVq1apS+++EKDBw/WSy+9VOW4/fv365577tGzzz6rLVu2qGXLlrr99tt1zTXX2NIPAIgmjNn+w5gNuI/CG6hHBw4cUEJCgm3HuWnz5s1hj9944w1de+21uvDCC207RyAQUKNGjfS///u/mjt37iGPu/jii7V161Y98cQTatu2rYqKilReXm5bPwAA/sOYHRnGbKBmTDWHL8yfP1+9e/dWRkaGsrKyNHjwYH377behrx84cECjRo1STk6OkpKSlJeXp4kTJ0qS8vLyJEkXXHCBLMsKPf7222913nnnqWnTpkpJSdHJJ5+st99+O+y8eXl5uvfeezVs2DClp6fr+uuvr7Z/ffr00ahRozRmzBgdffTROuussyRJDz74oLp06aLGjRurVatWGjFihPbs2RN6XuX0sjfffFMdO3ZUSkqK+vfvHzbABgIBjRkzJvS9//GPf5Qx5ohf02bNmoVtL7/8svr27as2bdrU+Lwnn3xSxx9/vBITE5WTk6NRo0Yd8tjGjRtr6tSpuv7669WsWbNqj5k/f74WL16s119/XWeeeaby8vJ0yimnqFevXkf0/QEA3MGYzZgNRCMKb/hCSUmJxowZo5UrV+qdd95RTEyMLrjgAgWDQUnSQw89pFdeeUVz5szR2rVr9eyzz4YG65UrV0qSpk+frs2bN4ce79mzRwMHDtTbb7+tTz75ROecc46GDBmijRs3hp37/vvvV+fOnbVq1Srdeeedh+zjjBkzFBcXp/fff1//+Mc/JEkxMTF66KGH9Pnnn2vGjBlauHCh/vjHP4Y9b+/evfrrX/+qZ555RkuWLNHGjRs1duzY0NcfeOABPfnkk3riiSf03nvvaceOHSooKIjo9Vu/fr0sy9KiRYuq/frWrVs1b948XXvttTW2M3XqVI0cOVL/9V//pc8++0yvvPKK2rZtG/r6sGHD1KdPn4j69sorr6hHjx6aPHmyWrRooXbt2mns2LHat29fRO0AABoGxmzGbCAaMdUcvnDwVKonnnhC2dnZKiwsVOfOnbVx40Ydd9xx6t27tyzLUm5ubujYJk2aSJIyMjLC/oLbtWtXde3aNfT43nvvVUFBgV555ZWwvwj/5je/CRtUD6Vt27aaPHly2L4bb7wx9P+tW7fWhAkTNHz4cD366KOh/WVlZZo2bZqOPfZYSdKoUaN0zz33hL4+ZcoU3XbbbaHXYNq0aXrzzTcP259fio+PV/v27Q95P9gZM2YoNTVVv/3tb2ts595779VNN92kG264IbTv5JNPDv1/Tk5O6Ber2vruu+/03nvvKSkpSQUFBfrpp580YsQI7dixQ08++WREbQEA3MeYzZgNRCMKb/jCt99+qzvvvFPLly/XTz/9FBooNm7cqM6dO2vYsGE666yz1L59e/Xv31+DBw/W2WefXWObJSUluvvuu/Xaa69p06ZNKi8v1759+6r89bxHjx616mN1x7377rv6y1/+osLCQhUXF6u8vFylpaUqKSlR48aNJUnJycmhAVyqGAiLiookSbt27dLmzZvVs2fP0Nfj4uLUo0ePiKautWjRQl9++eUhv/7kk0/q8ssvV1JS0iGPKSoq0qZNm9SvX79DHlM5VTASwWBQlmVp5syZSk9Pl1Qx3e+iiy5Sfn6+GjVqFHGbAAD3MGYzZgPRiKnm8IUhQ4Zo+/btevzxx7VixQqtWLFCUsV1YpLUvXt3rVu3ThMmTNC+fft08cUX66KLLqqxzZtvvllz587Vn//8Zy1dulSrV69Wly5dQm1WqhxsD+fg4zZs2KCBAweqc+fOmjt3rlatWqX8/HxJFX8xrxQfHx/2PMuybLkerLaWLl2qtWvX6rrrrqvxOKcG05ycHLVo0SI0gEtSx44dZYzRDz/84Mg5AQDOYcx2DmM24B4Kb0S97du364svvtAdd9yhfv36qWPHjvr555+rHJeWlqZLLrlEjz/+uGbPnq25c+dqx44dkioGykAgEHb80qVLNWzYMF1wwQXq0qWLmjVrpvXr19vW748++kjl5eV64IEH9Ktf/Urt2rXTpk2bImojPT1dOTk5Wr58eWhfeXm5Vq1aZVs/n3jiCZ100klhU/iqk5qaqry8PL3zzju2nVuSTjvtNG3atClsAZuvvvpKMTExatmypa3nAgA4izGbMRuIVhTeiHpHHXWUsrKy9Nhjj+mbb77RwoULNWbMmLBj/va3v2nWrFn68ssv9dVXX+mFF15Qs2bNlJGRIUmhwWfLli2hXwDatm2rf/7zn1q9erU+/fRTXXbZZRFf61STY489VuXl5Xr44Yf13Xff6ZlnntG0adMibueGG27Qfffdp4KCAn355ZcaMWKEdu7cGVEbP/74ozp06KAPP/wwbH9xcbFeeOGFw/7lvNL48eP1wAMP6KGHHtLXX3+tjz/+WA8//HDo67fddpuuuuqqsOcUFhZq9erV2rFjh3bt2qXVq1dr9erVoa9fdtllysrK0tVXX63CwkItWbJEN998s6655hqmrAGAxzBmM2YD0YrCG1EvJiZGs2bN0qpVq9S5c2eNHj1a999/f9gxKSkpmjRpknr06KGTTz5Z69ev1+uvv66YmIofkQceeEALFixQq1atdOKJJ0qqGPiPOuoo9erVS0OGDNE555yj7t2729bvbt266cEHH9SkSZPUuXNnzZw5s07XU91000266qqrNGzYMPXs2VOpqam64IILImqjrKxMa9eu1d69e8P2z5o1S8YYXXrppbVqZ+jQoZoyZYoeffRRHX/88Ro8eLC+/vrr0Nc3b95c5Xq7gQMH6sQTT9Srr76qRYsW6cQTTwy9B1LFe7dgwQLt3LlTPXr00OWXX64hQ4booYceiuh7BAC4jzGbMRuIVpapzwtL4HmlpaVat26dWrduXeOiHEBDxucYQLTj3zlECz7LiBYk3gAAAAAAOIjCGwAAAAAAB1F4AwAAAADgIApvAAAAAAAcROENAAAQpVhDF17HZxjRgsIbAAAgysTHx0tSlVtKAV5T+Rmu/EwDXhXndgcAAABgr9jYWGVkZKioqEiSlJycLMuyXO4VUHvGGO3du1dFRUXKyMhQbGys210CjgiFNwAAQBRq1qyZJIWKb8CLMjIyQp9lwMsovAEAAKKQZVnKyclRdna2ysrK3O4OELH4+HiSbkQNCm8AAIAoFhsbS/ECAC5jcTX43rBhw3T++efb1l6fPn1044032tYeAAAAAG8j8YYrAkGjD9ftUNHuUmWnJumU1pmKjfH2oi9lZWWsuAkAAACgChJv1Lv5n29W70kLdenjy3XDrNW69PHl6j1poeZ/vtnR87744ovq0qWLGjVqpKysLJ155pm6+eabNWPGDL388suyLEuWZWnRokWSpFtuuUXt2rVTcnKy2rRpozvvvDPsGrnx48erW7duevLJJ9WmTRslJiZq6NChWrx4sf7+97+H2lu/fr2j3xcAAACAho3EG/Vq/uebNfzZj2UO2r9lV6mGP/uxpl7RXf0759h+3s2bN+vSSy/V5MmTdcEFF2j37t1aunSprrrqKm3cuFHFxcWaPn26JCkzM1OSlJqaqqeeekrNmzfXZ599puuvv16pqan64x//GGr3m2++0Zw5czR37lzFxsYqNzdXX3/9tTp37qx77rlHktSkSRPbvx8AAAAA3kHhjXoTCBrd/WphlaJbkowkS9LdrxbqrE7NbJ92vnnzZpWXl+u3v/2tcnNzJUldunSRJDVq1Ej79++vcquKO+64I/T/eXl5uummmzR79uywwvvAgQN65plnworrhIQEJScnc+sLAAAAAJKYao569OG6Hdq8q/SQXzeSNu8q1Yfrdth+7q5du6pfv37q0qWLfve73+nxxx/Xzz//XONzXnzxRfXu3VvNmjVTSkqK7rzzTm3cuDHsmNzcXBJtAAAAADWi8Ea9Kdp96KK7LsdFIjY2VgsWLNAbb7yhTp066eGHH1b79u21bt26ao9fvny5fv/732vAgAF67bXX9Mknn+j222/XgQMHwo5r3Lix7X0FAAAAEF2Yao56k52aZOtxkbIsS6eddppOO+003XXXXcrNzVVBQYESEhIUCATCjn3//feVm5ur22+/PbRvw4YNtTpPde0BAAAA8C8Kb9SbU1pnKic9SVt2lVZ7nbclqVl6xa3F7LZixQq98847Ovvss5Wdna0VK1Zo27Zt6tixo0pLS/Xmm29q7dq1ysrKUnp6utq2bauNGzdq1qxZOvnkkzVv3jwVFBTU6lx5eXlasWKF1q9fr5SUFGVmZiomhsklAAAAgF9RDaDexMZYGjekk6SKIvuXKh+PG9LJkft5p6WlacmSJRo4cKDatWunO+64Qw888IAGDBig66+/Xu3bt1ePHj3UpEkTvf/++zrvvPM0evRojRo1St26ddMHH3ygO++8s1bnGjt2rGJjY9WpUyc1adKkynXhAAAAAPzFMsZUFz4C1SotLdW6devUunVrJSXVbUr4/M836+5XC8MWWstJT9K4IZ0cuZUYcDA7PscAAABAbTHVHPWuf+ccndWpmT5ct0NFu0uVnVoxvdyJpBsAAAAA3EbhDVfExljqeWyW290AAAAAAMdxjTcAAAAAAA6i8AYAAAAAwEEU3gAAAAAAOIjCGwAAAAAAB1F4AwAAAADgIApvAAAAAAAcROENAAAAAICDKLyBIzB+/Hh169bN7W4AAAAAaMAovAEAAAAAcFCc2x2ATwUD0oYPpD1bpZSmUm4vKSbW7V4BAAAAgO1IvFH/Cl+RpnSWZgyW5l5b8d8pnSv2O8gYo8mTJ6tNmzZq1KiRunbtqhdffFGStGjRIlmWpXfeeUc9evRQcnKyevXqpbVr14a1cd9996lp06ZKTU3Vtddeq9LSUkf7DAAAAMD7KLxRvwpfkeZcJRVvCt9fvLliv4PF9x133KHp06dr6tSpWrNmjUaPHq0rrrhCixcvDh1z++2364EHHtBHH32kuLg4XXPNNaGvzZkzR+PGjdOf//xnffTRR8rJydGjjz7qWH8BAAAARAfLGGPc7gS8o7S0VOvWrVPr1q2VlJQU2ZODgYpk++CiO8SS0ppLN35m+7TzkpISHX300Vq4cKF69uwZ2n/ddddp7969+q//+i/17dtXb7/9tvr16ydJev311zVo0CDt27dPSUlJ6tWrl7p27aqpU6eGnv+rX/1KpaWlWr16ta39hbOO6HMMAAAARIjEG/Vnwwc1FN2SZKTiHyuOs1lhYaFKS0t11llnKSUlJbQ9/fTT+vbbb0PHnXDCCaH/z8nJkSQVFRVJkr744ouwol1SlccAAAAAcDAWV0P92bPV3uMiEAwGJUnz5s1TixYtwr6WmJgYKr7j4+ND+y3LCnsuAAAAANQFiTfqT0pTe4+LQKdOnZSYmKiNGzeqbdu2YVurVq1q1UbHjh21fPnysH0HPwYAAACAg5F4o/7k9qq4hrt4s6Tqlhb49zXeub1sP3VqaqrGjh2r0aNHKxgMqnfv3iouLtYHH3yglJQU5ebmHraNG264QUOHDlWPHj3Uu3dvzZw5U2vWrFGbNm1s7y8AAACA6EHhjfoTEyv1n1SxerkshRffFdO61f8+x+7nPWHCBGVnZ2vixIn67rvvlJGRoe7du+tPf/pTraaTX3LJJfr22291yy23qLS0VBdeeKGGDx+uN99805H+AgAAAIgOrGqOiNiyGnThK9L8W8IXWktrUVF0dzrXno4CNWBVcwAAANQnEm/Uv07nSh0GVaxevmdrxTXdub0cS7oBAAAAwE0U3nBHTKzU+tdu9wIAAAAAHMeq5gAAAAAAOIjCGwAAAAAAB1F4o05Ykw9exucXAAAA9YnCGxGJj4+XJO3du9flngB1V/n5rfw8AwAAAE5icTVEJDY2VhkZGSoqKpIkJScny7Isl3sF1I4xRnv37lVRUZEyMjIUG8tK+gAAAHAe9/FGxIwx2rJli3bu3Ol2V4A6ycjIULNmzfijEQAAAOoFhTfqLBAIqKyszO1uABGJj48n6QYAAEC9ovAGAAAAAMBBLK4GAAAAAICDKLwBAAAAAHAQhTcAAAAAAA6i8AYAAAAAwEEU3gAAAAAAOIjCGwAAAAAAB1F4AwAAAADgoP8HIWX3knITiL4AAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 1000x700 with 4 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "class ASTAR(object):\n",
    "    def __init__(self, heuristic):\n",
    "        self.heuristic = heuristic\n",
    "        self.visited = None\n",
    "        self.fringe = None\n",
    "    \n",
    "    def solve(self, problem: Problem):\n",
    "        # YOUR CODE HERE: make sure to initialise self.visited and self.fringe here!\n",
    "        self.fringe = PriorityQueue()\n",
    "        self.visited = set()\n",
    "        end_node = problem.get_end_node()\n",
    "        start_node = problem.get_start_node()\n",
    "        self.fringe.put(self.heuristic(start_node, end_node), start_node)\n",
    "        values = {start_node: 0}\n",
    "\n",
    "        while self.fringe.has_elements():\n",
    "            current = self.fringe.get()\n",
    "            \n",
    "            if problem.is_end(current):\n",
    "                return current\n",
    "\n",
    "            if current in self.visited:\n",
    "                continue\n",
    "\n",
    "            self.visited.add(current)\n",
    "            for successor in problem.successors(current):\n",
    "                tentative = values[current] + successor.cost\n",
    "\n",
    "                if successor not in values or tentative < values[successor]:\n",
    "                    values[successor] = tentative\n",
    "                    self.fringe.put(self.heuristic(successor, end_node) + tentative, successor)\n",
    "            \n",
    "            \n",
    "        return None\n",
    "\n",
    "\n",
    "# reset maze before search\n",
    "maze.reset()\n",
    "astar_rand = ASTAR(random_heuristic)\n",
    "astar_rand_sol = astar_rand.solve(maze)\n",
    "if astar_rand_sol is not None:\n",
    "    astar_rand_sol.pretty_print()\n",
    "    maze.visualize(sequences=[('astar rand', \"\".join(maze.get_action_sequence(astar_rand_sol)))])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Basic checks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "f61060cb80e1b3fc067eeec7d8f39e54",
     "grade": true,
     "grade_id": "cell-a755d290a7174b17",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# this is a testing cell, do not edit or delete\n",
    "\n",
    "assert(astar_rand_sol is not None), \"A* did not return a solution\"\n",
    "assert(astar_rand_sol.state == (4, 4)), \"A* did not return the expected solution\"\n",
    "assert(astar_rand.visited is not None), \"it seems you did not correctly initialize the visited set\"\n",
    "assert(astar_rand.fringe is not None), \"it seems you did not correctly initialize the fringe\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "maze.reset()\n",
    "astar_cb_sol = ASTAR(cityblock_heuristic).solve(maze)\n",
    "assert(astar_cb_sol.depth == 7), \"the solution found by city block-A* does not have the expected length\"\n",
    "assert(astar_cb_sol.cost == 16), \"the solution found by city block-A* does not have the expected cost\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Check different mazes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "f4d306cb3c9cb1e6a4b650a38476bcc5",
     "grade": true,
     "grade_id": "cell-68702797ea5b6849",
     "locked": true,
     "points": 0.5,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "tiny1 = factory.create_problem_from_json(json_path='boards/tiny1.json')\n",
    "assert(ASTAR(cityblock_heuristic).solve(tiny1).get_action_sequence_hash() == '0123d362bf2df8f84e7c41197827be005159724c07774ef32d9f15373a440091'), \"City block-A* did not return the expected solution path\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ce0da3488b52d208fad0a40ff0a4a55a",
     "grade": true,
     "grade_id": "cell-0de1bd74e742f9e0",
     "locked": true,
     "points": 0.5,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "tiny1 = factory.create_problem_from_json(json_path='boards/tiny1.json')\n",
    "assert(ASTAR(chebyshev_heuristic).solve(tiny1).get_action_sequence_hash() == '0123d362bf2df8f84e7c41197827be005159724c07774ef32d9f15373a440091'), \"Chebyshev-A* did not return the expected solution path\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "b44c62aad8ed48f02b7f9b5895adc43a",
     "grade": true,
     "grade_id": "cell-64c86a0262c4475d",
     "locked": true,
     "points": 0.5,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "tiny2 = factory.create_problem_from_json(json_path='boards/tiny2.json')\n",
    "assert(ASTAR(cityblock_heuristic).solve(tiny2).get_action_sequence_hash() == '919c8fb20a877be0b0da8aeda03a070febb5607348e0c7f733c2405fdb9b4f74'), \"City block-A* did not return the expected solution path\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "766452fa6f1d78aa6e32b0a7c50b3d49",
     "grade": true,
     "grade_id": "cell-2af20325ececdc6f",
     "locked": true,
     "points": 0.5,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "tiny2 = factory.create_problem_from_json(json_path='boards/tiny2.json')\n",
    "assert(ASTAR(euclidean_heuristic).solve(tiny2).get_action_sequence_hash() == '919c8fb20a877be0b0da8aeda03a070febb5607348e0c7f733c2405fdb9b4f74'), \"Euclidean-A* did not return the expected solution path\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "c22e6b33c93fc7256859a7dc0feab21a",
     "grade": true,
     "grade_id": "cell-f2ad770abd459722",
     "locked": true,
     "points": 0.5,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "tiny3 = factory.create_problem_from_json(json_path='boards/tiny3.json')\n",
    "assert(ASTAR(cityblock_heuristic).solve(tiny3).get_action_sequence_hash() == '061c3912f2db8f3b1418829bc321fea4dfddba01ad42d45cecf22aed99a74475'), \"City block-A* did not return the expected solution path\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "6c3c40282e5d9f28262454b2099dec72",
     "grade": true,
     "grade_id": "cell-c099857f831b0c3a",
     "locked": true,
     "points": 0.5,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "tiny0 = factory.create_problem_from_json(json_path='boards/tiny0.json')\n",
    "assert(ASTAR(chebyshev_heuristic).solve(tiny3).get_action_sequence_hash() == '061c3912f2db8f3b1418829bc321fea4dfddba01ad42d45cecf22aed99a74475'), \"Chebyshev-A* did not return the expected solution path\""
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.13.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}