C4W4_34LOCAL_SEARCH_ALGORITHMS_35THE_WIDER_WORLD_OF_ALGORITHMS.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# XXXIV. LOCAL SEARCH ALGORITHMS \n",
    "\n",
    "### Local search Paradigm\n",
    "Local search is a general heuristic design paradigm. At a higher level, you should think of it that we're always maintaining a candidate cut. And we just want to iteratively make it better and better via small, that is local, modifications.\n",
    "\n",
    "#### Principles of Local search\n",
    "\n",
    "![Local Search](images/23_LocalSearch.png)\n",
    "\n",
    "![Local Search](images/24_LocalSearch.png)\n",
    "\n",
    "\n",
    "\n",
    "### The Maximum Cut Problem\n",
    "\n",
    "We're given, as input, an undirected graph g. And the responsibility of the algorithm is to output a cut that is a partition of the vertices into two non-empty sets, A and B, that maximizes the number of edges that have exactly one endpoint in each of the two groups of the partition.\n",
    "\n",
    "Sadly, unlike the minimum cut problem which we saw in part one is computationally tractable, the maximum cut problem, in general, is computationally intractable, it's NP-complete. More precisely, the decision version of the question where you're given a graph you want to know whether or not there exists a cut that cuts at least a certain number of edges, that's an NP-complete problem. There's no polynomial time algorithm for it unless P equals NP. Like most NP-complete problems, there are some computational tractable special cases. For example the case of bipartite graphs.\n",
    "\n",
    "One definition of a bipartite graph is a graph in which there exists a cut, so that every single edge is crossing it. And then obviously, that would be the maximum cut of the graph.\n",
    "\n",
    "A slick way to solve this problem in linear time is to use breadth-first search. You just root the breadth-first search at a arbitrary vertex of the graph. You draw for your breadth-first search tree. You put the even layers as one of your groups A. You take the odd layers and make it the other group B. This will have no crossing edges, if and only if, the graph is bipartite.\n",
    "\n",
    "\n",
    "![The Maximum Cut Problem](images/26_MaxCutAlgo.png)\n",
    "\n",
    "\n",
    "To succinctly state the algorithm I'm going to need a little bit of notation. So imagine that we have some undirected graph and we're trying to approximate the maximum cut. And suppose we have some current candidate cut A,B. Some of the vertices are in A the rest are in B. Now focus on some arbitrary vertex $v$, $v$ can be an A or B I don't care. There is some incident edges to this vertex $v$, in the graph on the right, I've shown you a vertex $v$, it has degree five, five incident edges. Now, some of these edges are crossing the cut, some of the edges are not. So I'm going to use the notation $C_v (A, B)$ to denote the number of v's incident edges that are crossing the cut. And $d_v (A, B)$  to denote the edges, the number of edges which are not crossing the cut. So in the picture that I've drawn, $C_v$  would be equal to two, $d_v$ would be equal to three.\n",
    "\n",
    "Here then is the local search algorithm for maximum cut. In step one, we just begin with an arbitrary cut of the graph, so we just somehow, I don't care how, put some of the vertices in A, some of the vertices in B.\n",
    "\n",
    "Now, we just iteratively try to make the cut that we're working with better until we don't see any easy way to improve it further.\n",
    "\n",
    "So what's a principled way to take a given cut and make it better? Well, let's just focus on very simple modifications. Let's suppose the only thing we're allowed to do is take a vertex from one of the two groups say, from group A, and move it to group b.\n",
    "\n",
    " Well here are the two ramifications of moving v from A to B. So, first of all, the two edges incident to v that used to be crossing the cut, they no longer cross the cut. When we put v over on the right hand side the two edges who's other end points are in B those edges get sucked in internally to B. They are no longer crossing the cut. On the other hand, the good news is, is that the three edges incident to v with the other endpoint in A they used to be internal to the group A, but when we bring v over to the right hand side to the group B, now those three edges cross the cut. So we lost two edges from the cut but we gained three so that's a net improvement of one more edge crossing the cut. In general this argument shows that for any vertex so that the number of edges incident to it that are not crossing the cut, if that's bigger than the number which are crossing the cut incident to it, Then switching sides with that vertex will improve the cut. And the improvement is exactly the difference between the two quantities $d_v$ and $C_v$\n",
    " \n",
    " If we find ourself with a cut such that there's no vertex switch that improves the cut, that is if $d_v (A, B)$ is at most $C_v (A, B)$ for every single vertex $v$. Then we stop and we just return to the cut that we ended up with.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before A: ['a', 'c', 'd', 'g', 'h', 'i', 'j', 'k', 'n', 'o', 'q', 's'], B: ['b', 'e', 'f', 'l', 'm', 'p', 'r', 't']\n",
      "After A: ['a', 'c', 'g', 'i', 'k', 'n', 'o', 'q', 's', 'm'], B: ['b', 'e', 'f', 'l', 'p', 'r', 't', 'd', 'j', 'h']\n",
      "Number of edges in Max-Cut: 17\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvnQurowAAIABJREFUeJzsnXdYVNfWxt+hCVIUlaa0QRQ7FppioZgY7Iq5eqM3iYJojC0aSzSa6NVYEqPRaEDFmC8m0RswJho1NsAKqCiCgop0kA4OA0zf3x9mTmacGcr0wfN7Hp9H4MyZveCcd/ZZ+91rMQghBDQ0NDQ0WsFI1wOgoaGheZ2gRZeGhoZGi9CiS0NDQ6NFaNGloaGh0SK06NLQ0NBoEVp0aWhoaLQILbo0NDQ0WsRE1wOgoaHRT6rYXMTdLUZ2GQssjgA25ibo42iDt4c5o6tVB10PT+1oK14GvTmChoZGkvSiOuxPzEHSk0oAAFcgon5mbmIEAiDIyw6LxnjC26WzjkapPrQdLy26NDQ0FMeS87H1bDY4AiGaUwYGAzA3Mcb68X0wJ8Bda+NTN7qI1/jzzz//XKUz0NDQtAteClAWmvgvZ3oFOyaDYWIKc+d+co8XiAhu5Vajs4UpBjkb3oz31XglkRe7uuKlF9JoaGiQXlSHrWez5QpQczTxRdh6NhsPius0NDLNoMt4adGloaHB/sQccARCpV7LEQhxIDFHzSPSLLqMlxZdGprXnCo2F0lPKpvNaTY+u42CHZNRczFa5meEAAmPK1HN5mpwlOqjNfE2h6rx0qJLQ/OaE3e3uNmfsx8moDLuv7AZ/i90eWOh3GMYAOLSmj+PvtBSvK1BlXhpny4NzWtOdhlLyiYlSdOzO+AWP4Jt8FzY+E1TeA6OQITs5/WaGqJaaS7e1qJKvLTo0tC8xgiFQpRU1Cj8ObfoIYytuzYruGJYHL46h6YyfD4fhYWFyMvLQ25uLvLy8pCXl4c0a3+gW2+Vz69svLTo0tC8Rjx//hwpKSlITk5GSkoK7t69i26TVgKuPnKPt/Gfjvq0P1F6ZCm6z9vb7LltzE01MWSFiEQilJWVUWIq/icW2LKyMjg5OYHJZMLDwwNMJhOTJk2Cca0dbpSo/gGhbLy06NLQtFOamppw9+5dpKSkUELb0NAAf39/+Pv7Y+3atfD19cX/Mmqx+9ITuY/cRhbW6B6xH6WHP8Dz/1sJp3d3yX0vcxMj9HGyVnsMdXV1cgU1Ly8P+fn5sLa2pgSVyWRi+PDhmD17NphMJlxcXGBqKiuM9UnPcKdcfrytRZV4adGloWkHiEQiPH36VGoWm52djX79+sHf3x+TJ0/G1q1b4enpCQaDIfXaGcMssfvSE4XnNunsAKeI/Sg9vAhlx1bDcc5OmWMIgBlDnds8bg6Hg4KCAikxlRRYgUBACSqTyYSXlxfeeustMJlMuLu7w8rKqs3vOWOYM75uJt7WoGy8AL0NmIbGIKmurkZqaiolsKmpqbCxsUFAQAA1kx0yZAgsLCxadb6oH+/gYla5UjYqBgMY188B0XNkUxRCoRAlJSUKUwBVVVVwcXGRSgFI/uvWrZvMh4SqXL9+He8evAZR9wEAo+0GrubibdXradGlodFveDwe0tPTpdIE5eXl8PX1pQTW398fjo6OSr9HelEdZh1KRhO/7RsGzE2M8PmoTjCqK5aZsRYVFaFr164yYioW2B49esDY2FjpcbeF+vp6fPLJJzh58iRWb9+PmBwLpeK1MDXGiagApbcC06JLQ6NHEEJQUFAglSZIT09Hz5494e/vT81k+/btq3axaq4WgcLx8jlouvUznJvyZASVyWTCzc2t1bNtTXL+/HksWLAAoaGh2LVrF2xtbZWK18LUCOvH91Wp6A0tujQ0OqS+vh63b9+mBDYlJQUMBkNKYH18fGBtrf5FKjF8Ph9FRUXIy8tD3P0yXKiyhpAwmn30ZoDAzJiBFSEeWBDSV2NjU5Xq6mqsWLECV69excGDB/HGG29I/VwXVcZo0aWh0RJCoRAPHz6UShPk5eVhyJAhVIogICAALi4uas1jEkJQXl4u1wGQl5eH0tJSODo6UrNTa7f+yDHzwNOGDjBiMMAV/iMR4vqywV52WBTkqbfVxQghiIuLw9KlSzFz5kxs2bJF4aLbg+I6HEjMQcLjSjDwcuODGE3ES4suDY2GkOeJdXJykprFDho0SK6tqa2wWCy5gpqbm4v8/HxYWlrKffxnMplwdXWFmZmZzDmr2VzEpRUj+3k9WBw+bMxN0cfJGjOG6nfniNLSUnz44Yd4/PgxYmNjMXz48Fa9Tlvx0qJLQ6MGmpqakJaWJpUmYLPZ8PPzowTWz88PXbp0Uer8XC4XBQUFCj2rHA5HoQOAyWRqND2hLxBCcOTIEXzyySdYuHAh1q9fjw4d9O/DgRZdGpo2IumJFc9ks7Ky0L9/f6k0gTxPbHPnLC0tlTtbzcvLQ0VFBZydneU6AJhMJuzs7NRurTIkcnNzMX/+fLx48QJHjhzBoEGDdD0khdCiS0PTAoo8sZJpgpY8sYQQ1NbWKtwEUFhYCFtbW4UpAGdnZ5iY0HuZXkUoFGLv3r3YunUr1qxZg48++kjvf0+06NLQSMDj8fDgwQNKYMWeWB8fH6mNB/I8sY2NjcjPz1e4YAVA7uO/h4cH3N3d9cJaZUg8fPgQERERMDc3x6FDh9CrVy9dD6lV0KJL89oi6YkVC6ykJ1Y8kxV7YgUCAYqLixWmAGpra+Hm5qYwBWBra/tapwDUBY/Hw/bt27Fv3z5s2bIF8+fPh5GR4ZQGp0WXxqCoqKjA48ePMWrUqDa/tiVPrJ+fH9zd3VFRUSF3waqkpAT29vYKF6y6d+9uUDe/vtLU1AQLCwsIhUKZDSAikQgXLlzAt99+i+joaDg7K1f/QJfQoktjMMTExGDbtm2UFWvw4MEghMidPQqFQjx69EgqTZCXl4eBAweid+/ecHBwgIWFBWpra6mUQH5+Pjp06CAjqOKvXV1d9XI1vD2xefNmnDp1CufPn4e9vT1EIpHMB5lAIICxsbHBPjXQoktjMDx79gzm5ubYsmULBg4ciEWLFsnMhggheOedd/DHH3/A2toa3bp1g5mZGbhcLsrKytDU1KTw8Z/JZMLGxkaHEb7e/PLLL4iJiUH37t1hbGyMH3/8UddD0gj6vcxHQyNBz549AQC9evVCSkoKFi1aJHMMIQReXl4YOnQovLy8ZFIADg4OBjtDau+Eh4fD29sbLi4uePPNN3HixAnMnDlTbprBkKFnujR6R21tLfLy8tDY2IjAwEAZkbx69SpWr16N5ORkmdcqSjfQGBYnT57Eli1bkJCQgE6dOrWrvystujRah8PhID8/X64DICcnBwKBANbW1jA1NUVRUZHMzVZWVoY333wTly5dgr29vY6ioNE0UVFRAICDBw+Cy+XCxMSkXcx46fQCjdoRCoWUtUqeZ7WmpgYuLi5wd3eHjY0NBAIBamtrUVVVBUII5YcNCAiQe35HR0e4u7ujrKxM4WILjWEhbyb71VdfISwsDPPmzQOXy8WWLVvAZDJ1NEL1QYsuTZshhKCqqkrhJoCioiLY2dlJ5VJDQ0PRsWNHVFVV4enTp0hNTcXNmzfh4eGBgIAATJo0Cf7+/ujXr1+Ls5nCwkJUVlZi/PjxGDduHFasWIH+/ftrKXoadVNUVASBQABXV1epvz2Xy0V5eTkaGhoQHR3dLgQXoNMLNApoaGhotmqVqampQgeAm5sb+Hw+bt++LVVlC4DULFaZOrEvXrzA1KlTYWtrizFjxiAoKAje3t6a+BXQaBiRSISYmBhs3LgRmzdvxsKFC6Vmu2vWrIGlpSU2btyow1GqH1p0X1P4fD4KCwsVpgDq6+vh7u6usGpV587/1BV91RObkpKC3NxcDB48WKo+gaura7tZDKFRjSdPniAyMhICgQCHDx9Gv379ZI5pb64FMbTotlMIISgrK1OYAnj+/DmcnJwUelYdHBwU5knFmxPEs9i7d+/C0dFRqjbBoEGD5NZopXm9EQgE2LVrF7788kts3LgRH374YbsU1uagRdeAefHihcKqVQUFBbCysmq2cHVrimeL68RKpgnq6+ulahOoUieW5vXh/v37iIiIQNeuXRETE9NucrRthRZdPYbD4TRbuJrH4zVbtUpRexJFEELw9OlTqTTBo0eP0K9fP6k0Qa9eveg0AU2r4XA4+O9//4tDhw5h586deO+9917r64cWXR0iFAqbLVxdWVkJFxcXhSmAbt26qXTxiuvEimexqampsLa2lkoTDB06lC45SKM0N27cQEREBPr3749vv/0WTk5Ouh6SzqFFV4MQQlBTUyPXASC2VnXp0qXZwtXqyneJ68RKpgnKysrg4+NDCay/vz99U9CoBTabjXXr1iEuLg779u1DeHi4roekN6hddKvYXMTdLUZ2GQssjgA25ibo42iDt4fpdzM7ZSmqrMORhIfILK5FNasR/AYWBNWFYGdcQsHjTBgZGSlMAbi5uWlkFkkIQWFhoVSa4P79+/Dw8JBKE7TGE0vz+qLsvfzXX39hwYIFCA4Oxq5duwwm368t7VKb6KYX1WF/Yg6SnlQCALhy2hgHedlh0RhPeLvoZ9tmeQgEAhQVFcmkAB5XcVDRbTCMegwEAwBM/lmpN2G83F0zsmcXLH+jr8bjFdeJVeSJ9ff3h4+PD11Bi6ZVKHsv19TU4KOPPkJSUhIOHjyIN998U9tDVwpta5daRPdYcj62ns0GRyBEc2djMABzE2OsH98HcwLcVX1btUAIQXl5uVwHQF5eHkpLS+Hg4CD1+F/RqQ8uVFqCLwSa++VpIl6xJ1ZSYCU9seKZLO2JpVEGZe7l2f5uiI+Px9KlS/H2229j69atbV7E1RW60C6VRffloLPQxBe1fPDfWJgaYf34vloTXhaLpdCvmp+fDwsLi2YLV0v6TeXFW7BjMjqPeRedAmbIfX9V4pX0xKakpODOnTtwdHSUShPQnlgadaDMvWxuYgS74muoSv4NsbGxGDFihAZHqF50pV0qiW56UR1mHUpGE1/Y5tdamBrjRFQABjmrPl3n8XgoKChQ6FnlcDjNFq5u7VZURfG2JLpA6+JV5In18/OjBNbPzw9du3Zt3S+GhqaVqHIvG0OI4/MD4OthOBXfdKldKhW82Z+YA46g7YMGAI5AiAOJOYie49PisSKRiLJWyUsBVFRUoEePHlKCOm3aNOprOzs7tTxqqzPeljyxEydOxJYtW2hPLI1WUOXaFjGMEXuz0KBEV1vaJQ+lRbeKzUXSk0q5eZDyExvBKUgHRELA2AQ2PlNgGzxX6hhCgITHlahmc9HF0owqXC0vBVBQUABbW1up2emoUaPw3nvvUdYqTfe6by5eAOAUpKPu2jFAKICJrROc3tsNI/N/8lqEAJcelWPtZ1uQnnoDKSkpsLa2ptIE77zzDu2JpdEJr17bBTsmw9xjKDj56YCQDxPb7rCbvg7lP6+DqIkFI3MrOL6/B6adX7ahl7yXDcGh1Ny9/DL2YeDk3weEfBhbd0P3iG9l7mVV4lVaqeLuFiv8mWk3V3Qe8y5M7d1RdyUWrJR4dOw3Bh0cPKSO4/F4CPzPSjy/8rIXkuTjf//+/TFx4kQwmUy4u7ujY8eOyg5VLTQXLwBwCjPh8M52GHfshOffL0V53GY4zdkpdYxQwEcW6YwFCxbgyJEjtCeWRi+Qd21zCzPh9P5uEAEfZT+sQNkPK9A1bBksevqi+Lu5qD77DRzf2UYdzwAQl1aMBaN7anHkytHSvcwtfADH/3wJow6WKD38AaovHIDd5NVSx6gSr9Kim13GkrJWSNIlNPKf/49dgPr7f6Ex65qM6BIjE/i9OQ17YjfD1tZWrx+jm4sXADp6DYd5jz4AABu/aXhx84TMMcTYFB6DR2Lq1MEaGycNTVuRd21bDgiBmZ07AMDYyhYMc0tY9h8DADB3GwxuySOp4zkCEbKf12tlvKrS0r1s2T8EHRw9AQBm9kzwyvNkjlElXqVFl8URKPxZ9bl9YD9MAAQ86ntCdo3cY0072hiEebq5eAHAxLYH9X9Te+bL1Irc8/DVOi4aGlWRd22bdJLIzxqbwNiiE/Ulw6wDIJS9jvX52pbsZvLwaQ0AxWkBk84O1P8ZJh1AGl/IPU7ZeJUWXRtz+S/lFD8CO/0v2L6xEFbeb8LIxAwFX00HUeBotTFvudKVPqAoXjGC2hLq//yKfMBI/k4vQ4mXpv1CCEFBQQG1gHur1h5wHKjyeXV5bUt2M5HnYhJ3M3Fzc0P9gHCgi5fK76lsvEqLbh9HG3QwKZOZpgubXk65xUn2qj/3SM14JTE3MUIfp7Z1DtAViuIV0/j4FrilT2BkYQ1W6kmYOfWSOcaQ4qVpP4h3LEo6ZYB/dixOHDAEf+QJwRUob9nXxrXNZrNlxFRSZM3MzKTWhYYMGYKpU6eCx+Ph8ePHuHbtGq5duwYn+6EwsvWEiKH8FnhV4lVadGcMc8buS09kvm/Zyx+sHn1R8evnABgwdfAAo4P8RTACYMZQZ2WHoFUUxSvG3HUAyn5a/dK90NkRduEbZI4xpHhpDJOWuni888472Lt3r9SOxSo2F79vv6zS+6rj2n61m8mrM1Z53UxGjx5NfS1u1f706VNcuXIFly9fRkJCArp27YrQ0FC8//77OHr0KGBujcAdV5rN62oyXpU2R0T9eAcXs8qb3T6nECJCqJcdYufK7/iqj6gSL4MBjOvnoLS3j4ZGHoq6eLRlx+Lp06fx4fF0GLl4A4y2d1Vu7bUt2c1EXgpA2W4mxcXFuHz5Mq5cuYIrV64AAEJDQxEaGorg4GA4O8uKoy7vZZ3tSDMiAgjOf4nvtn6CCRMmKDsEraIvO/BoXk/EOxYlZ7GSXTzaumOxsrISy5Ytw+3bt/HJV9H48i5f5WtbXjcT8dfq6mZSWVmJxMREajZbW1uL4OBghIaGIiQkBJ6eni06oXR5L+u09kL3xlzMnz8fAQEB2LNnD+zs7FQZilYwhFoTNIaPJrt4EELw888/Y8WKFXj33XexadMmdOzYUalr25gI0aMiBQ3p5zXSzQR4WTvl2rVr1Gw2Pz8fo0aNQkhICEJDQzFgwACF/fyawyBrL4hRpVJPY2MjNm7ciGPHjmH37t2YNWuWXvt1AcOuqkajnyjq4iEpsOrYsVhUVIQPPvgAhYWFiI2Nha+vr9TP/+9mHraeywJPoMhv9DdEBCOIMMK8DJP6dlZbNxPgZXufmzdvUumCjIwM+Pn5USLr4+Ojth2oBlllTMyD4jocSMxBwuNKMPDSPCxGXJMy2MsOi4I85U7LU1NTERERAXd3d3z33Xdy8zD6hKrx0ry+6KKLh0gkwsGDB7FhwwZERkZi0qRJlG/11W4mXXsNgbX/DHC79YIRAxDin1V+TVzbAoEAd+7codIFqampGDBgAJUuGDFiBMzNzVV+H0Vo+15We+eIajYXcWnFyH5eDxaHDxtzU/RxssaMoS1XX+fxeNi2bRu+/fZbbNmyBfPnz1fqsUGbqBIvTftHF108GhsbpXKqd+/exZkzZ9DU1AQAMDU1bVU3E01d2yKRCJmZmZTIXrt2De7u7ggJCUFISAhGjx6tk4L72rqX9bJHWmZmJiIiItCxY0ccOnQInp6euh4SDU2r0EYXD0XdTMT/Xrx4ATc3N7i5uYHFYuHBgweYOXMmPvjgA3h6esLW1lZd4bYKQgiePXtG5WQTEhLQuXNnKl0QFBRkEOs56kIvRRd46Tfcu3cvtm7dirVr12L58uUaryRGQ9MWNNXFgxCCiooKhS4Aed1MJP85OTkhIyMD8+bNQ5cuXXDw4EEwmUwN/iZkKSkpoXKyly9fhkgkotIFISEhcHFx0ep49Am9FV0xubkvHQ4sFguxsbEYNGiQrodE85pSVlYmlSaQ7OIhFtjWdvGQ7Gby6oxVUTcTsci+2s1EEg6Hgy1btuDgwYPYsWMH3n//fa0sTFdXVyMxMZGazVZVVSE4OJiazdJ1of9B70UXePnJf+TIEaxduxYffPAB1q9fjw4d6HwpjeaQ7OIhnsm2pYuHuJuJvBSAvG4mr85aW9vNRJKbN28iIiICffv2xf79+zVaOpTNZuPq1avUbPbZs2cYOXIkNZsdNGiQ3q/H6AqDEF0xpaWlWLRoEZ48eYLY2FgMHz5c4bHiqkJubm5aHCGNISL2xEqmCSQ9seJZrORsTSQS4fnz5wpTAPK6mUj+s7e3V9vMj81mY926dYiLi8O+ffsQHh6ulvNKwuFwkJycTKUL0tPT4evrS4msr69vqzY20BiY6AIvb5C4uDgsXboUH330EVatWiX34r148SKWL1+OCRMmYOfOnXLORGOIVFRU4PHjxxg1apTS56ipqZFq9vlqFw9/f38MGTIEHA5HYQqgoKAAnTt3VpgC0EY3EwC4cOECoqKiEBQUhK+//lptZVIFAgHS0tKodEFycjL69+9PpQtGjBhBdzlREoMTXTHV1dXgcrlwdHSU+xjD4XBw+vRpLFy4EBkZGejevbsORkmjTmJiYrBt2zaq3sDgwYNBCGl2xijpiRXPZMvKyjBs2DD4+PjA1dUVtra2qKurkxFYAAof/3XdzaSmpgYrV65EQkICYmJiMG7cOJXORwihbFxXrlzB1atX4eLiQons6NGj0alTp5ZPRNMiBiu6LdHY2Ig5c+bAz88Pa9euhUgkonNMBs6zZ89gbm6OLVu2YODAgVi0aBGEQqGUv5UQgt9//x1Xr15FcnIy7t+/D0dHRzg7O1N50pqaGuTn56O2thaurq4KUwBdunTRy8Wf+Ph4LFmyBDNmzMDWrVuVyv8SQpCbmytVjcva2ppKFwQHB8Pe3nAaTRoS7daDFRMTAxaLhbVr1wKAXt48NG2jZ8+X/ah69eqFlJQULFq0SO5xf/75J+Lj41FfXw87Ozs4OzvLTQF0797doD6Inz9/jsWLF+PRo0f49ddfERgY2KbXl5aWIiEhgUoZ8Hg8hIaGYty4cdixYwe9/qEl2uVM9969e3jvvfdw5MgR+Pj4yMyGaAwHeemDq1evYvXq1UhOTpZ7fFFRETgcDtzc3NqFy4UQgqNHj2LNmjWIiorCp59+2qptsTU1NVLVuCoqKhAUFETNZr28vOjJiA5oNzNdQgjOnz+PsLAwfP3115g4cSJ8fHxACKEFV4/h8XhShavF/x4/foympiZkZWXJvKZ3795obGxERUWFzCMwg8GAq6urtoavcfLy8hAVFYWamhpcuHABgwcrbmrKZrNx/fp1SmSfPn2KwMBAhIaG4qeffoK3tzd9L+gB7UZ02Ww29u7di8jISHTu3Bk//viyrXtLCy00mkUkElGFq+W5AMrKyuDg4AA7OzuYmJigsbERz58/B4/Hw7Bhw+Se09HREe7u7igrK4O9vX27zNcLhUJ8++23+O9//4tVq1Zh5cqVMm4ILpeLlJQUKl1w7949+Pj4ICQkBHv37oWvr2+rNmrQaJd2l17Yt28f1q1bh59++gmTJk2iBJfP58PY2Ljd3Zz6gHjlX14dgPz8fNjY2Eit+ltaWoLNZqO0tBQPHz5EVlZWs57YVyksLMTMmTNRVFSEcePGYcWKFejfv7+Wo9Ycjx49QmRkJExMTHD48GH07t0bwEshTktLoxwGt27dQp8+fSiHQWBgoE4dFTSto92JLvCyfUdWVhbGjh0LBoMBkUiEv/76C1u2bMHhw4fRt29fXQ/RoOBwOMjPz1fYEFAgECjsBmBjYyPVsys1NRVWVlZK14l98eIFpk6dCltbW4wZMwZBQUHw9vbW8G9AO/B4POzcuRPffPMNNm/ejKioKGRnZ1PpgqSkJPTo0YPKyY4ZMwadO9NlQw2Ndim68hCJRIiOjsbGjRvx0UcfYfXq1fQOmr8RCoUoKSlRmAKoqqqCi4uLjKCKv+7atSsYDAb4fD4ePHggVZ/g+fPnGDZsmFSVLU1uTzVU7ty5g4iICNja2mL8+PG4f/8+rly5AktLS6pITHBwMBwdHXU9VBoVeW1EV0xBQQEWLlyI58+fIzY2VmHesD1BCEF1dbXCLquFhYXo1q2bwo0APXr0kFmAEbsExAIr9sSK68SKZ7LqrBPbHnn27BmWLVuGy5cvw8rKCsbGxlRTxZCQELi7u+t6iDRq5rUTXeClYBw7dgwff/wx5s6di88++8zgtzQ2NDQgPz9fYS0AExMThSkAycLViqivr8edO3ek6hMQQqQEVtU6sa8DtbW1SEpKwuXLl3H69GkUFRXByckJH374IaZMmYK+ffvSC7/tnNdSdMWUl5dj6dKluHfvHg4fPozRo0frekgK4fP5VOFqeTNWFosFNzc3hSmAtuT+hEIhsrKypNIEz549g7e3t1SawM3NjRaIFmhoaMCNGzcoh8Hjx4/h6+uLhoYG5OXlISYmBlOnTtX1MGm0yGstumJOnTqFxYsXY/Lkydi+fbtOZmuEEJSXlytMAZSWlsLR0VFhCkBRDYrWUFZWJlWbQJU6sa87PB4PKSkp1OJXWloahg4dSjkMqqqqsHTpUowfPx47d+6k6xm8htCi+zd1dXVYtWoV/vrrL0RHR2P8+PFqfw9x4Wp5KYD8/HxYWloqTAE0V7i6LTQ1NeHevXtSaQIWi9XqOrE00giFQmrR6/Lly7h58yZ69+5N5WRHjhwJS0tLVFZWYtmyZUhNTcWhQ4cQHBys66HT6Ai1i24Vm4u4u8XILmOBxRHAxtwEfRxt8PYww2jUePnyZURFRWH48OHYs2cPunXr1uzxkvHWNfJgJOCiM9hw5hWjvPCZlMCKC1fLSwG4u7srVbikOQghyMnJkUoTPHz4EH379pVKE/Tq1Yv2L7cSQgiys7OpdEFiYiKcnJwoh0FQUJBUDzJCCH755ResWLECc+bMwebNmw3GS2vo93Jb0Va8ahPd9KI67E/MQdKTSgAAV04b4yAvOywa4wlvF/32FjY0NGDjxo346aefsGfPHsycOZPy+5aWliIvLw/XHxXiXCFBkdAGRCQCjP+xnzGEfDCMjOBqUo8JHqYY3d8NTCYTdnZ2Gs2B1tTUIDU1VapOrNgTK04TtMUTS/OS/PzvjYgBAAAgAElEQVR8aiZ75coVdOjQgXIYBAcHK7TAFRcX44MPPkBBQQFiY2Ph6+ur5ZErR3u6l1uDtuNVi+geS87H1rPZ4AiEaO5sDAZgbmKM9eP7YE6Au6pvq3YIIaitraUe+ZOSkvDzzz/DxMQEVlZWKC0tha2tLexHTEe955sQGRkDUCyimoxX7ImVTBPQnlj1UF5eLlWNq6GhgZrJhoSEwMPDo9nXi0QiHDx4EBs2bMCSJUuwdu1ag8mHt5d7ubXoIl6VRffloLPQxBe1fPDfWJgaYf34vjr5YzU2NsrsrpJMAQCQevx3cXFBamoqzp07hy1btsBm6AR8cU678b7qiU1JScH9+/fh7u5OCSztiVWeuro6JCUlUbPZkpISjBkzhlr86tevX6ufUJ4+fYr58+eDw+EgNjbWoLYnG9q9rCq6ilcl0U0vqsOsQ8lo4gvb/FoLU2OciArAIGf1Pp4IBAIUFxcrdAHU1tbCzc1NoQvA1tZW7g2WkZGBd5dvQN2w90GMm9/JVhI9H0ZWtnCa80+boLbEK+mJFc9kaU+s+mhsbMSNGzcokc3KysLw4cMpkR0yZEibW+0IBALs3r0bO3bswKeffoolS5YY1AegPt7LmkSX8apUZWx/Yg44grYPGgA4AiEOJOYgeo5Pm15HCEFlZaXc4iq5ubkoKSmBvb29lKCOGzeO+lrZwtUDBw6Ez3vrcTGrvM2vBRTHK/bESqYJJD2xs2bNwu7du2lP7N9kZ2eDzWa3qU4yn89HamoqlS64c+cOBg8ejNDQUHz55ZcICAhQqe5ueno6IiIi0LlzZ6SmpraYftBHdHEv6xJdxqu06FaxuUh6UtlsHqQ5CAESHleims2VWRmsr69XWFwlPz8fHTp0kJqdDhs2DDNmzICHhwdcXV01Uri6is3F1adVaC6H2xzieLPzivEkI40S2Dt37sDBwYGaxS5YsID2xMpBIBBg1qxZuHLlCpycnPDw4UOFgisSiZCenk6J7I0bN+Dp6YmQkBCsWbMGo0aNgpWVlcpj4nK52LJlC2JiYrB9+3bMnTvXID8YNXkv6yO6jldp0Y27W6zwZ5ySbFT+9gVE7FoABKZ2bugesV/mOJFIhI8PxMOh5oGUwDY0NMi0VwkODpaqXKVtmou34WESqs99AyLgwdi6m0Jd5nI4CJq7BoPNqxEQEICPP/6Y9sS2EhMTE0RGRmLfvn2YOnUqCgsL5RYr5/P58PDwgJWVFUJCQhAZGYkff/xR7b/jmzdvIjIyEl5eXrh//75BNz5t7tpufJqKqjNfgXAbAWNT2PhNg+2Yd2WOYwCISyvGgtE9NThS9dBcvAU7JsPc3RucwgxAKICJrROc3tsNI3PpD2lV4lVadLPLWFLWCjEiAQ/lP38C064ucJq7F0bGJmA/TJR7Dr4IyCqtg6edNaZMmUKJqoODg97NGBTGy2tE1ZldsOjpi26TV6Hu2jHU3z4FYxs5Tf1MzDDrg4+xZ+YQLYy4/fHmm2/CyMgIzs7OuHz5MubOnSu3MeW9e/da9FcrC5vNxvr16/Hrr79i7969CA8P17trta0ovrY5qPxtK8xdB8Fu+ieov3cedQlHYO7cDxY9pR+tOQIRsp/Xa2vIKqEoXjGcwkw4vLMdxh074fn3S1Eet1lqfQZQLV6lHfEsjkDu9xsyLwNCARzf/Qomlp1hZG4Fm2ETFZ6n/xBfrF+/Hu+88w6GDx8OR0dHvbyIFcXLfnAJAEG36ethZGaOLqGRYJgp9sHWKzgPTcuIc/GBgYFISEiQe4yZmZnGBPfChQsYOHAgXrx4gYyMDMyYMUMvr9W2ovDazrgIEBHs/vUZjMw6opP/dBjb2OFFcpyC8/A1OUy1oSheMR29hsO8Rx+Y2jrBxm8aeKWPFZxHuXiVFl0bc/mTZH5VERgmZjAyaV1O0sbcMGraKopXUFsKhrGZ1OLcq48ikgib6iEQ0MLbEi9evMDZs2fl/q5GjBiBzMxMANCKQ6CmpgZz585FVFQUoqOjcfTo0XaREiKE4OnTp6h6XiT35/9c2/9c+8ZWXSBsqJV7vKHfy2JMbHtQ/ze1ZwIi+QtuysartOj2cbRBBxPZl5t2cwER8CAS8Fo8h7mJEfo4qXfrq6ZQFK9JZycQIQ8i0T+PKyIOW+45jEQCXP/zV6rrwerVqxEfH4+SkhKNjdtQaGpqwuXLl7Fu3ToEBATA2dkZX3/9NWpqamSODQgIgKWlJerq6gBAox9i8fHxGDBgAKysrJCRkYFx48Zp7L00TU1NDc6fP49NmzYhLCwM3bp1w9ixY1HzLAPGkH3cNrHt/ve1/c/vV8iuhbGlrcyxhnIvC4VCmDVWwYgodi4Iav+5H/kV+YCR7Ae7KvEqLbozhjnL/b7lgFDA2ATlx1ZD0FAHEYcNVtpZuccSADOGyj+PvqEoXivvNwAwUPXbNogEPNReOQLCa5J7rKmZGVJ+2YOioiJ8+umnsLGxwffff4/BgwfD2dkZ4eHh+PLLL3H16lU0NDRoMBrdw+fzcfPmTWzZsgXBwcGws7PDxo0bYWxsjG3btqGyshKXLl2S6fYLAJmZmSguLoaHhwdmz56NoiL5MzVVKCsrw4wZM7B+/Xr873//w759+9ReG0OT8Pl83L17F/v378e7774LLy8vuLu7Y8eOHeBwOFiwYAEyMzNRUFCAU7vXyvUlWw0MBRhGqPx1M0Q8DlippyBkVcAmIFzmWH2+l/l8Pi5cuIAFCxage/fu+Ct6U7NpocbHt8AtfQJ+7XOwUk/CzKmXzDGqxKvS5oioH+/gYla5jPWCU5z10r3QUAuAAVM7d3SP2Cf9xgDG9XcwKG+fonjZGZdR/dd+QOxeAGDcyV4q+c5gAOP6yY+XEIK8vDypHWcZGRno3bu31IYILy8vgy1MIxKJ8ODBA2pDwvXr1+Hh4UFtSBg1alSrRK2iogKzZs1Cr169MGHCBISGhsLS0lJt4ySE4IcffsDq1asxf/58bNiwAebm5mo7vyZQtGORyWS2qotHY2Mj3tj0PxSjKxivXF8NT26h+s/df7sXTGDjMwW2wXOljmnu2tYVHA4HFy9eRHx8PE6fPo1evXohPDwc06dPR8+ePRXeyzLuhc6OcHh3F0w6/lOCU9V4dbYjjfC5GGfyCN98ttJgCrBocxcLl8vF/fv3pW6k6upq+Pn5UTeSv78/7Ozs2jwWbSDOF4q9sgkJCejatStV8jAoKEhjC17Kkp+fj6ioKFRVVeHIkSMYPHiwrockl+a6eIi3hbd2x2JSUhIiIyPRZ8Q4PHWdAE4zq/qK0JcdaQ0NDTh37hzi4+Nx7tw5eHt7Izw8HNOmTYOLi4vUsYru5YIdk9F5zLvoFDBD4fuoGq/Oai8sGeWMpMNbDKJrgyS63J9eWVkptTX49u3b6Nq1q9TNNnjwYI1sDmkNxcXFlMheuXIFACiRDQkJgbOzfj5+CoVC7N+/H5s3b8aqVauwcuXKNm8D1hQt7VhUtovHixcvsGbNGpw5cwYHDhzA5MmTDbL2wosXL3DmzBnEx8fj0qVL8Pf3x4wZMzB16lQ4ODg0+1p58bYkujqvvSBGlUo9+tC1oa3oSyUmkUiEx48fS82Gnzx5goEDB0oJMZPJ1Ii1qbKyEomJiZTQ1tbWIjg4mBJaT09PvbdUZWVlISIiAiYmJjh06BC8vLx0Oh7JLh4pKSm4ffu22rt4/Pnnn1i4cCHCwsKwc+dOqVZOrb22AQII+Ng4eQDmjZLNeWqS6upq/P7774iPj8e1a9cwevRohIeHY/LkyW12lbwaryLR1asqY2IeFNfhQGIOEh5XggFIPaaIa1IGe9lhUZCnzLRcG10b1I0q8WqShoYG3L17V2pmxOPxpFISfn5+SrWJYbFYuHbtGiWyeXl5GDVqFCWyAwcONJicM5/Px44dO7Bnzx5s3rwZCxcu1PrYORwO0tLStNbFo7KyEsuXL0dycjIOHTqEkJAQuce15toO8rJD6cXvYW/yspqapikrK8OpU6cQFxeH27dvY+zYsQgPD8fEiRNVnqhp+15We+eIajYXcWnFyH5eDxaHDxtzU/RxssaMoS1XX29r1wZ9QJV4tUVxcbFUWiItLQ2urq5Ss+EBAwbIPFJzOBzcvHmTWvzKzMyEn58flS7w8fGBqalheDMluXv3LubNm4cePXogOjpa7nZidSPu4iEpsNrq4kEIwfHjx/HRRx+1qXtFS9c2m82Gn58fVq5ciYiICLWOGQAKCwvx22+/IT4+HhkZGQgLC0N4eDjeeusttS6eitHWvax3PdIUdW2gUR8CgQCZmZnUzZ+cnIzi4mIMGTIErq6uEIlEKCwsRHp6OgYMGEA5DIYPH24wi57yaGpqwueff46jR49i165dmD17tsauLXldPCwtLaXqH2uji4e4e0V+fj5iY2Ph5+en1vNnZWVh9OjRuHDhAoYMUX17+7NnzxAfH4/4+Hjk5ORg8uTJCA8Px9ixY/XeRdJqiJ6SnJxM+vfvTyZPnkyKi4t1PZx2iVAoJOnp6eTrr78m48aNI5aWlsTBwYEwmUxiY2NDnJycSHh4ONm5cydJSkoibDZb10NWmsTEROLp6UlmzpxJysvL1XpuHo9H7ty5Q/bv30/effdd0rt3b2JtbU2CgoLImjVryG+//UZKS0vV+p4tIRQKSXR0NOnWrRvZtGkT4XK5Gnuv48ePEw8PD1JbW6vU6x8+fEg2b95MvL29ib29PVmwYAG5cOEC4fF4ah6pfqB3M11JeDwevvjiC+zfvx9bt25FZGSkweQM9RHy9yOu2F2QkJCATp06UTlZ8SYF8bG5ublSaYnMzEzKOyyesem7d5jFYmHNmjU4ffo09u/fjylTpqh0PvK3J1YyTfBqFw9/f3/0799fZ0XMddG9YunSpcjPz8epU6davB4IIbh//z41o2Wz2Zg+fTrCw8MRGBhoUMXflUGvRVdMRkYGIiIiYGlpiUOHDsHT01PXQzIYSkpKpJoqCoVCqaaKbclnyvMO19TUwNfXV0qI9SUX/+eff+KDDz7AW2+9JbNK31rkdfEQiURSaQJ96eKhy+4VPB4PY8aMwZQpU7B27VqZn4tEIqSmpiI+Ph4nT54EAISHhyM8PBy+vr56/cGtbgxCdIGXfsVvvvkGX3zxBT755BMsW7ZMb7yU+kR1dTUSEhKo2WxlZaWUjat3795qzWNWVFQgNTWVEmKxd1hy1qdt77BIJEJUVBQSEhKaXaV/FUlPrFhgxZ5YyQ8VfeziIdm94uDBgzrpXlFcXAxfX1/8/PPPCA4OhlAoxPXr1ymhtbGxoYTW29tb736H2sJgRFfMs2fPMH/+fLDZbBw5cgQDBgyQe5xQKERxcTHc3Ny0PELtUl9fj2vXrlGz2dzcXIwcOZJa/Bo0aJBWZxEikQjZ2dlSwvX06VOteYeBlymFX375Bf/5z3+aXaUvLy+XShPcuXMH9vb2Uh8Y3t7eet3FQ9y9Ijo6Gtu3b8e8efN0Kmbnzp3DnDlzEBYWhosXL8LJyYkS2n79+ulsXPqEwYku8DInFBsbC0II3nvvPbk3xcWLF7F8+XJMmDABO3fulHMWw4TD4SA5OZlKF6Snp8PX15cSWV9fX72zcbHZbMo7LBY5Pp8vZfj39fVtlXe4qakJFhYWzfZHEwgEcu1v9+7dk3JsvHjxQsa/rC+pkdZw69YtREREoHfv3jhw4IDOule8WufAwsICpqamOHfuHPr06aOTMekzBim6YkQikcJZHIfDwenTp7Fw4UJkZGQYbDsVgUCAtLQ0SmSTk5PRr18/Kl0wYsSIVnku9Q2xd1gsgmLvcEBAAKZPn46wsDAZUd28eTNOnTqF8+fPw97eXuHfnxCCZ8+eSQnso0eP0KdPH6nZtiY8sdqAzWbj008/xYkTJ7B3716dFFNvaGjA+fPnER8fj7Nnz2LQoEFUQZkePXpg4sSJ6Nu3L3bt2qXVcRkCBi26zdHY2Ig5c+bAz88Pa9eubVag9QlCCDIzM6l0wdWrV+Hi4kKJ7JgxY5TaTabv8Pl8ZGZmIiUlBeXl5Vi1apXUh8kvv/yCmJgYdO/eHcbGxvjxxx8VnuvFixcYOHCgVJpg6NChBvnh9CoXL15EVFQURo8eja+//lqrxdRZLJZUnQM/Pz+Eh4dj6tSpcHR0lDq2pqYGw4YNw1dffYXwcNlSkK812vSnaZOvv/6ahIaGUl+LRCIdjkYxIpGI5OTkkIMHD5KZM2cSe3t70rNnTzJ//nxy/PhxUlZWpush6gzJvxmXyyUPHz4kLBaLBAQEkOPHjxNCCBEIBM2+rr1QU1ND5s6dS1xdXcm5c+e09r5VVVXkyJEjZMKECcTa2ppMmDCBHDlyhFRVVbX42tu3bxM7Ozvy+PFjLYzUcGiXopuWlkYGDhxIbt++TQiRf2PqkpKSEvLjjz9SN5GTkxOZPXs2OXLkCMnPz9f18PQGReIZHx9PhgwZQurq6uQe195ENz4+nnTv3p0sXryYsFgsjb/f8+fPyXfffUfGjh1LbGxsyPTp08lPP/1E/b7bQnR0NBkwYIBBb6xRN+0mvUAIwfnz5xEWFob//Oc/cHFxwRdffAFCiM6tKTU1NUhMTKRSBhUVFQgKCqIWv7y8vHQ+Rn2AzWbjzp07VC523bp18PHxkfu7iYqKAgAcPHgQXC4XJiYmUjngxsZGnDlzBpaWlnrlHW4LZWVlWLx4MTIzM3H48GGMHDlSY+9VVFSEkydPIj4+Hg8ePMD48ePVUueA/L3YDQA//PADfZ2jHeV06+vr8a9//QsPHjxA586d8fDhQwD/LLZpM6fLZrNx/fp1avHr6dOnCAwMpETW29u73e+6aQmhUIjs7GypjRY5OTmUJ9bf3x/Tp09XaNdisVgICwuDl5cXZZtiMpnUz0UiERITE7Ft2zakpqbCzs5Oyi3h7e2ts7rDLUEkuldERkZi48aNGqk7oK06B42NjfD398fixYuxYMECtZ3XUGk3oitm3759WLduHX766SdMmjSJ+mQtKipCYmIi5syZo/ZPWy6Xi+TkZGpDwr179zBs2DBq8cvPz0+vvZ7aQOyJFbsJxJ5YSTfBq57Y5p5SKisrMXz4cFhZWSE6OhoBAQEK31vSOywWebF3WHJnmbu7u85nYpLdK2JjY9VSREaSR48eUUL7/PlzTJs2DeHh4QgKCtKo1fDJkycYOXIkzp49Cx8f/WnrowvanegCL+1IWVlZGDt2LHUTZWdn49///jccHBwQExOj0qYJoVCItLQ0Kl1w69Yt9OnThxLZkSNHtouVcmURe2IlRa6urq5NntiEhAQEBgYq/LBas2YNLC0tsXHjRqXGKOkdFo9R7B0WC3FrvcPqQCgU4sCBA9i0aRM+/vhjrFy5Ui0iSF6pc1BfX0/VORg5cqRWn7hOnjyJFStW4O7du+2ihb2ytEvRVQSfz8dXX32FXbt24fPPP8eiRYtalXIghODRo0dUuiApKQk9evSg0gWjR4+Gra1sW+rXAfKKJ1ZcJ1bsiRWLWGs9sbW1tVi5ciUSExPx8OFDhaUPm9scoSzFxcVScaSlpcHNzU0qjv79+6t9+3lWVhZVzOnw4cMqd68QiUS4ffs24uLicPLkSRBCqF1hfn5+OrVOrly5EllZWThz5oxBWDg1wWslumKys7MRGRkJADh8+LDcXTN5eXlS/b46duxIiWxwcLCML/F1oba2lqoTm5ycjNTUVHTs2FFqhqisJ/bkyZNYsmQJpk2bhm3btum85bmkd1gsxsXFxRg6dKhUWkLZjTd8Ph87d+7Enj17sGnTJpW6VwiFQty4cYOqc2BlZUUJ7eDBg3WeNhHD5/MREhKCN998Exs2bND1cHTCaym6wMvZwHfffYfPPvsMK1aswJw5c6QWvzgcDtUhISQkRGqR5nWBz+cjIyNDSnRKSkowbNgwqY0Hqu72E6/SZ2Rk4PDhwxg1apSaIlA/tbW1uH37ttTvxMLCQupDZ9iwYS1+6Ii7V3Tv3h0xMTFKda/g8/lITExEfHw8Tp06BUdHR4Ooc1BaWgofHx/88MMPeOONN3Q9HO2jRXuaXlFTU0N+++038t577xFLS0tibGxMgoKCyN69e8nDhw/bndezJUQiESksLCS//vorWblyJRk5ciSxtLQk/fv3J/PmzSMxMTEkPT2d8Pl8tb7n999/T+zs7Mgnn3xCmpqa1HZubSESicjTp0/JsWPHyJIlS4ivry/p2LEjGTJkCFm4cCH5/vvvSVZWFhEKhYQQQhobG8nq1auJvb09+fHHH9t8nXE4HHL69Gny/vvvk65duxI/Pz+yY8cO8vTpU02EpzESEhKIg4MDKSws1PVQtM5rM9NtaGjA9evXqcWvx48fY8SIEVS64OHDh1izZg3mzp2Lzz77zKDb0rQGsSdW0lEgFAplFpI0VSc2Pz8fCxYsQEVFBY4cOaL2VXpdwuFwZOoO19bWwtPTE7m5uejfvz9iYmLQt2/fVp1Pss7BuXPnMHDgQKrOgYuLi4aj0Rzbt2/HqVOncPXq1dfK3dNuRZfH4yElJYUS2bS0NAwdOpRKF/j7+8v4NMvLy7F06VLcv39f7x9z24JIJKLqxIqFICcnB4MGDZLKTWqjTqxIJML+/fvVvkqvz7BYLCxduhRnzpxBcHAwlaIQe4fFf4PBgwdT4tOWOgeGikgkwrRp0+Dm5oa9e/fqejhaQ+2iW8XmIu5uMbLLWGBxBLAxN0EfRxu8PUyz3XGFQiHu379P5WRv3ryJ3r17U4tfI0eObPXOmlOnTuHDDz/ElClTsH379mZne7qKtzkkPbHiwuJiT6zk5gBtzy7UvUpvCCjqXiH2DkvOhp88eQInJyeIRCKUl5cjICAAc+bMwZQpU3RisdLGtV1XV4dhw4Zh69atmDVrllrOqSzaupfVJrrpRXXYn5iDpCeVAACunN7xQV52WDTGE94uqveOJ4QgOzubEtnExEQ4OjpKVePq0qWL0uevra3FqlWrcOHCBURHR2P8+PFSP9d2vIqQ9MSKZ7J1dXXw8/OjBFbXdWLFq/S7d+/G5s2bVVqlNxQqKyuxfPlyJCcnN9u9ory8HKdOnUJcXBxSUlIwePBg9OjRg/IRCwQCqUVLbXiHtX1t37t3D2+++SauXr3a6pSLOtF2vGoR3WPJ+dh6NhscgRDNnY3BAMxNjLF+fB/MCXBv8/vk5+dL9fvq0KEDJbIhISFwcnJSPggFXL58GfPnz0dgYCB2796Nbt26aS3eVyF/e2Il0wQPHz6El5eX1I3Zu3dvvRE1dazSGxKEEJw4cQLLly/H7NmzsXnzZpknrOLiYqrOQXp6OsLCwhAeHo6wsDCpYwkhMnWH7927R3mHxX9zdXqHdXVtx8bGYteuXUhNTYWVlZXK52stuohXZdF9OegsNPFFLR/8NxamRlg/vm+Lgy8vL6d8sleuXAGbzabSBWIblzb8hw0NDdiwYQN++eUXzPz0W5wv7wiOnHibnt1BxW9fAAIeLHqPgP30dQBaH++r1NXVSfUfS0lJoTyx4ptOX+vENjU14fPPP8fRo0fx1VdfaWT7tb5RXFyMRYsWITc3F7GxsfD396d+lpubS+0Ke/r0KSZNmoTw8HC88cYbbapzIGnjE4ux2MYnKcTK2Pg0eS+3hg0bNmDZsmXo2rWrVq4VXcWrkuimF9Vh1qFkNPGFbX6thakxTkQFYJDzP9P1uro6JCUlUbPZ4uJijBkzhhLZ/v376/TG/encday/UgmYyM+FlsREgWFqju7zZBcF5MUrSXM3kzo9sdrg6tWriIyMxJAhQ7B37144ODjoekhq4dq1a/Dz85NZgBU/gQwfPhyLFy/GJ598AjMzM2RlZVFCW1paiqlTpyI8PBzBwcFqXTwUL8xJfjhbWFhIXTcteYfVfS8rA3lZalbhUxohBCwWSy3pFV3Gq5LoRv14Bxezypudlit8YwYQ6tUNM7uzqHRBVlYWhg8fTs1mhwwZolcdf6N+vIOLj8qhKNyiPbNg7ukHu4krZH7GYADj+jkgeo5Ps4+NkjeKJracahIWi4W1a9fijz/+wLfffoupU6fqekhqISkpCfPnz0dubi6OHj2KOXPmyGxDbmxsxLNnzyAUCimhZbFYOqlz0FwaSnI2LJmGUvVeFl/bmkIkEuHo0aM4duwYLl68qPLvsrXxigQ8GL0yyVI1XqVFt4rNReCOK1JJZzHcshxUxm2GkF0LMBiw6BVAPWpLQgQ8dL9zAG+MGo7Q0FAEBATobbm95uIFgMLdM0G4DdTX9v/aDAuPoVLHGEOEfjm/4O6NRJ0skGgS8Sr9uHHj8OWXX1Kr9O2BiooKZGdnIzc3F2fPnsX//vc/mVKhHA4H8+fPx40bN/SmzoEkzS24DvILxG/CYRDIUYKGh0moPvcNiIAHY+tuAAMwtrGH0xzpZq8dTIxwc02IRh07HA6Hqt6nisWspXu5YMdkmDOHgFPwABDy4fLxSRnhVSVepadRcXeL5X5fJBKg/NhqmHXvg+5R0eCWPUPFL5+i7uYJdB4xU+pYc3NzvL8pGgtG91R2GFpDUbxiXD86gcLd/4JFrwC5M13g5QzEeVQ49u7cqhdlBNVBVVUVli9fjlu3buH7779HaGioroekduzt7WFvbw9HR0fs2rULjY2NMo/qZmZm2L17t9bykW3F3Nwcw4cPx/Dhw6nvlZeXIzU1FbE3CyEU8QEj6ZSHiNeIqjO7YNHTF90mr0LdtWOov30Kxjb2MudnAIhLK9bYvfzixQt88cUX6NixI2bOnNnyC5qhpXsZADiFGXB4ZxtMbLvLCC6gWrxKfwxnl7HkflI0ZFwBEQrg+M4XMDLrCAvXgTB3H4SGjEsyx3IFImQ/r1d2CFpFUbxtQcQwhrlDT60tAGoSQgiOHz+OAQMGwMHBAQ8ePGiXgitJr1694OLigjNnzgB46Q0XY2RkhG7duuWnsDAAACAASURBVBnU39XBwQGTJk2C++ARIEayOWb2g0sACLpNXw8jM3N0CY0Ew0z+Tk2Omu9lkeifey0rKwuzZ8/G48ePce7cOQQGBkKV9f/W3MuWfUbBvEcfmHSU79FXJV6lZ7osjkDu9/mV+QARoWD7RKnvG1nIHzyLw1d2CFpFUbxtP49hxNsckqv0v//+u9QqfXuGwWBg7NixOHnyJP71r3+1m+4frCb516SgthQMYzOpFImRuWI7l7qubYFAgPfffx+rVq1CbW0tVqxYgfHjx2PLli0A2l7Ws6GhAXl5edS/5GIbwNiu2deYdnVu8bzKxqu06NqYy3+paTcXwMgYbqt/b+V5DGMLqKJ4234ew4hXHiKRCIcPH8b69euxePFixMXFtbs9842NjTh//jyMjIwQFhYms8bw73//GydOnADwslqWvb29QS12ArI7Fh/a+KCDl+yWd5POTiBCnlT+WsRhw9hGvmCp69o2MTFBaGgoAgMD4e7ujl27dmHcuHEA5Asun89HUVGRlLDm5uZS/2exWHB3d4e7uzu6dOkCXmc/QEEMFK14YlE2XqWvlj6ONuhgUiYzTbccEIraS4dQ/r/P0HXiShiZmaPp2R0QXiOsBo6VOtbcxAh9nHRbM7W1KIq3LRhSvK+Sk5OD+fPno7GxEQkJCRgwYICuh6Q2WCwW/vzzT8THx+PixYvw9fXF/Pnz5c6mMjIykJ6ejo4dO2LBggX47LPP9HrRUFEXD/GOxRUrViALzjh4q0Tm2rbyfgO1V2JR9ds2dJuyCi+uHgPhNcl9H3Vf23PnzsXt27fx4MEDSnBFIhH1N+FyuTh16hTWr1+PoqIiODo6gslkgslkwsPDAxMmTACTyUSHDh2QkZFBNYYlhKDX5P5gMQgERPlUkCrxKi26M4Y5Y/elJzLfNzIxg8Ocnag8uRUl+2YDhIBhao5OgbL7qgmAGUNbnsbrA4ribQuGFK8YgUCAPXv2YPv27Vi3bh2WLVvWLh6ra2pq8McffyA+Ph5JSUkYNWoUwsPDERMTAyMjI3z88ccIDg6Gvf0/i0ZPnz7Fl19+iU2bNmHWrFkqtXzSBGKrmKRfNzMzE3369EFAQADCwsLw+eefy+xY9GNzcfBWicz5jMw6ouv4Zaj+az+KvpoOY+tuLx0M8t4b6r+2Dxw4gE8++QRPnjyhxiwUCiEQCJCQkIAuXbrg/PnzcHV1pZ64KisrKYHdvHkzamtrERwcjJCQEKxfvx69evVCdQMPgTuuQKDCBEqVeHXq09W0t0+dVFVV4c3/xqHGvAeghA3I0OIFXs7qIiIiYG1tjYMHD6JnT/13mTSHuM5BfHw8UlJSEBoaivDwcEycOJGy6/32229YvHgxpk2bhl27dumthRGQ7uKh6o7F1t7LJdHzYWRlK2UZa821zeVyUVBQIPP4X19fjxMnTii0S/L5fGojSVNTE3g8ntSxLBYL165do7z+eXl5GDVqFOX1HzhwoFzbni61S6Vk1IdBnrj2tEqpXR3mJsZYFOSpyttrBcm99GFzFuKWmRs4SnxCGkq8wMsbZOvWrfjuu++wbds2REREGNSqvCTy6hxERUXht99+k6pzUFZWhiVLluDBgwc4fvy43pX1bKmLR2RkJA4dOqT0jkVV7+WFo3uiuLhYJp8q/ldRUQFnZ2epFMDQoUPBZDIhEokUdn6W3LnH4XAwcOBAfP7551QdlgcPHsDPzw+hoaH47rvv4OPj06rdfrrULr2uvaBrSkpKsGjRIjx79ozaS9+e4wWA5ORkREREwNPTEwcOHECPHj10PaQ205Y6B4QQ/N///R9WrVqFyMhIbNy4sU21EDSBrnYstubafnWmyxDyYZR+CiVJx2Fra0sJqlhcxV/36NFDqbESQiASiXD27Fns2bMH169fh5GRET788EOEhYVhxIgRSjccMMjaC2J0VZlIUxBCcPjwYaxbtw4ffvgh1q1bJ7VK397iBV7aaj799FMcP34c33zzDd5++22Dmt0qU+dAX7pXyOvioYsdi42Njdj/1wMculMNnojg5RYABRARTIyAGT2N8N4ID7i7u6ul24rkjJfL5aKmpgZLliyBi4sLQkNDMWrUKKxZswZVVVX49ddfVb5GDbLKmJgHxXU4kJiDhMeVYABSj+DimpTBXnZYFOSpcmEMTZKTk4OoqCiw2WzExsZi4MCBco9rL/ECwKVLlxAVFYWRI0dSu6r0HUIIHjx4QAntixcvWl3nQLJ7xcqVK/Hxxx9rrXtFc108JOsiaGLHokAgaDYFUFtbCzc3Nzj28wfHYzSqzBzAYDCkVvnVfW2LF/8uX76MpKQkBAYGYtSoUXB1dUVFRQVsbW1hZydt7+JwOBg5ciRmz56Njz76SKX3B7R/L6u9c0Q1m4u4tGJkP68Hi8OHjbkp+jhZY8ZQ3XVSaA0CgQDffPMNtm3b1qZVekONF3i5EPPxxx/j0qVLiI6ORlhYmK6H1CyEENy+fZsSWqFQiBkzZrSpzoG4ewWDwcDhw4fRp08fjY5ZXhcPOzs7qVmst7e3WhbsCCGorKyUEVTx1yUlJbC3t5d5/BenAJycnKR+h5q6tktKSqhyrZcvX4ZQKJSqi92amsv5+fnw9/dHfHw8Ro4cqfRYJNHWvdxue6S1BfEqvZWVFQ4dOmTwq/StQXKVftu2bbC21k//sFAoxM2bNxEfH4+TJ0/ijTfewBdffAE7OzswGIxWzwb5fD6+/PJLfP3119i0aRM++OADtRejackTq44uHvX19Qo3AeTn58Pc3FyuoDKZTLi6uurEjVFdXY3ExETKYVBZWUnZuEJDQ9G7d2+lZvVnz55FVFQU7t69a1DlQ19r0eVyufjiiy9w4MABg1+lby2Sq/T62nyTz+cjKSkJ8fHxOHPmDN59913MnTsXTCZTKY9wWloa5s2bBycnJ0RHR6vFX6tM+cTWwOPxUFhYqDAF0NjYCHd3d7kLVkwmU2Pdm9sCm83G1atXqdlsTk4ORo4cSc1mvb291faBt2HDBty4cQMXLlwwmJ2Br63otodV+rYgXqVfvXo15s2bh88++0znq/SScLlcXLp0CfHx8fjjjz/g4eGBt99+Gx999JHSN1NTUxM2bdqE77//XuXuFfI8sRYWFlIC21KhcOBlTresrExhCqC8vBzdu3eX6wBgMpmwt7fXu4kBh8NBcnIylS5IT0+Hr68vlS7w8/PTWM5cKBTirbfego+PD7Zt26aR91A3r53oSrbeMcRVemWQXKWPjY3F0KFDW36RFhDXOYiPj8fZs2cxYMAAhIeHY/r06Sr3UlOle0VznlhxHtbf31/hB3Vtba3CFEBBQQE6deokV1CZTCZcXFz0fsYmEAiQlpZGpQuSk5PRr18/Kl0wYsQIrbaQqqysxNChQ7F//35MnjxZa++rLK+V6IpX6QMDA7Fnzx6DWKVXBV2u0itCXp2D8PBwTJ06VS2NRYVCIZYsWdLq7hXKNH/kcDjIz8+XmwLIzc2FSCSSK6hMJhPu7u4yjSr1HUIIMjMzqXTB1atX4ezsTKULRo8erfP6E7du3cKUKVOQnJwMDw8PnY6lJV4L0SWE4PTp01i8eLHcdurtkezsbERGRgKAVlbpm0NRnYPJkyervTV8Q0MDli1bhq+++kquELTGEzt06FCw2WyFKYCamhq4uroqXLDq0qWLQT89EUKQm5tLpQsSEhJgZWVFiWxwcLBeLlzt3bsXR48exY0bN9TiGdYU7UZ0m5qaYGFhobDWJo/HA4/H02p7Z12gjVX61tCaOgfK0NLfWdJcL+mJFQus2BM7aNAg/H97Zx4V1ZWu/YdBGQQREQQFGYVCVKYEUNFisDVKm0VEjL0S+7ZibCVfYoZOom1f9bM1rm5NjG3UDJJllppOp0k0ye2ko5FB0QAigqJQKHPJIHNRWvPZ9w9vna5DVTHUXHB+a7lYWMU5+6XOedjn3e9+Xj8/P7i5uUEoFDLElc/nY9q0aVpnqzNmzBgTpj+qtLa2Ij8/n04ZSKVSOl2QnJyMgIAAcw9xWAghWLduHVxdXXHy5ElzD0crY0J09+7di/Pnz+Pf//43vLy81PpXjReMsUo/Gh48eED7HFRUVGDFihXIyMjAihUrDPJIPZLPmRCC3NxcHD9+HGVlZXBxccHMmTPh4uICiqLQ09ODpqYmTJgwQWsFgL+/v0UtMhqDnp4e2o3r0qVL6OjoQFJSEj2b5XA4VjlbHxgYQFxcHN5++21s2LDB3MPRiNWL7t///nd8/PHH9Ozj9OnT5h6SyTHkKv1oaWhooDcr1NbWDulzoA+j+ZwHBgYQEBAADw8PzJ49W2MKwJqbgOqCUChEUVERLbL37t3DokWL6AqDqKioMTN7v3v3LrhcLi5evIioqChzD0cdYuVIJBJy584dIhAISEJCAvnyyy8JIYTI5XIzj8w0FBYWktmzZ5O1a9eS9vZ2k5yzurqa7Nu3j0RHRxNPT0+yefNm8tNPPxGpVGqwc1AURSiKor8fzec8+GfHI2KxmBQWFpJdu3aRxMREMmnSJLJkyRKyZ88ecuXKFSKRSMw9RKPyxRdfkODgYNLb22vuoahh9TNdVb755hvs27cP+fn5cHNz02oXNxYQCATYvn07vv32Wxw7dmzYVXp9IIN8Dvr6+mifg8WLF+s8Q+rv79dYVnX//n00Njbi8uXLiIuLU/sMx9PnPFIUCgXKy8vpCoNr166Bw+HQ6YLExESTlnFZAq+88gpaWlpw7tw5i7o+xpToAsDmzZsBAJ988gkkEgns7e3HzGOTkh9++AFbtmzBsmXLcPDgQbi7uxv8HESDz0FGRgYyMjIQHx8/opy5RCKhS6s0VQHIZDK6b5WdnR2EQiFaW1vR29uLmJgYrFy5Etu3b9d4w4yHz3koCCG4e/cunS4oLCzEzJkz6XQBl8s1ynVhTUilUixZsgSrV6/G22+/be7h0Fit6MpkMkilUrUFGoFAgBUrViAsLAwSiQT79u1DYGCgmUZpWLq6uvD666/j6tWr+PTTTw3e8nywz4GzszMttNHR0Wrip1Ao0NraqnUjQFdXF8O4WrlNVSAQoKWlBbdv32bUxCrrYlVrYrVVKYzlz1kbDQ0NdHVBXl4enJ2dGRUG3t7e5h6ixdHc3Iy4uDh8+eWXSEpKMvdwAFip6JaXlyMrKwvPPPMM9u/fz5h1dXZ2YsGCBXBxccFHH32EhIQEM47UMBBC8NVXX+G1117Db37zG/z5z382WIG9XC5HYWEhcnNzcf78eXh5edFCGx4ezthdNbhutbm5GVOnTtXqWuXm5oaKigp604GyJlZVYLX5xCp9MdLT0zX63I7Fz3kwbW1tyM/Pp2ezIpGI4cY11v/IGIoLFy7gd7/7HW7cuGGQDTj6YlWiKxKJsHfvXnz22Wc4ePAg1q9frzb7eueddzBp0iTs2rXLTKM0LMruFffv30dOTo5BxEXpc/DNN9/gu+++g7e3N2JjYzFr1iy6ZlUpsLa2tlp9APz9/ekidG01sfPmzWNsPAgMDBw2v6bqi3H27FmNtdVj7XMGnmwfLiwspGezra2tSEpKomez4eHhFpWbtCb27t2LixcvIi8vz+y7Mq1GdK9cuYJNmzYhMjISR48e1bojRtvjqLVBBnWv2LFjh062fHK5HC0tLaiursa//vUvXL58GTweD46OjiCE0HlVbTWr2vKCDx8+ZAis0idWdRY7Wp/Y0fhijIXP+dGjR7h69SotsjU1NVi4cCE9m42Ojrb6GC0FiqKQlpaGiIgIHDp0yKxjsXjRFQgE2LFjB86fP48PP/wQzz33nLmHZHRG2r0CeCLODx8+1Pj4X1dXBz6fj4kTJ0IqlcLLywsxMTFYvnw5oqOjERQUBG9v72EXxcRiMSNNUFJSgp6eHsTFxdGz2Li4ODWH/9EwHnwxpFIpSkpK6HRBeXk5oqOjaZGNj4+36O7D1k53dzdiY2Px/vvvY/Xq1WYbh0WL7o8//ogtW7bgV7/6ldFW6S0JhUKBDz74QK17hUAgUKsAUIpsY2MjnJ2d6Zmpj48P+vv7UVNTg6qqKiQmJiIzM3PEPgdExSdWOYutqqpCWFgYLbAJCQmj9onVRl9fH958801cvHhxzPliKBQKVFRU0CJ77do1hIaG0jnZxMTEMb8t3dK4fv060tLScPXqVcyePdssY7BI0VVdpf/kk0+wdOlScw/JqEilUly4cAFvvvkmbGxswOVyGQtYIpFIqw9AYGAgRCIR7XNQXFyMlJQUrFmzZkQ+B319fSgtLWXMYh0dHRkCGxMTYxRnrPPnz+Pll19Geno6Dhw4YBEG3PpACEFNTQ2dLigoKIC3tzedk+VyuZg6daq5hznuOXHiBE6cOIHi4mKz1C5blOiqrtKvW7cO+/btszobPE1QFIW2tjatVoCtra0AgNDQUCxatIgWVuVXZWsaVQb7HDzzzDO0z4G22ZNcLsft27cZ1QQPHjxATEwMw8bQ2IbuHR0deOWVV1BRUYGTJ09iyZIlRj2fMWlsbKRnsnl5eXBwcGC4cc2YMcPcQ2QZBCEE69evh52dHU6dOmXyxUmDi26XUILcG3zUtAsgEMsx2dEeHO/JyIwdurlba2srtm7datBVelOgjPdWcxc6egZApI/gIOqGc8cttNbzUF9fj+bmZkyZMkWtAkAsFuPIkSMICwvDiRMnhhU7VZ8DHo9H+xwsW7ZMzeeAqPjEKgX25s2bmDVrFqOaYO7cuSYzzSaE4PTp03jrrbewceNG7Nq1y6It+DTR0dHBcOMSCoV0uiA1NXVE1RnWgq73sjXw6NEjxMfH49VXX6U32pgqXoOJbmVLH44V3EdhbScAQKKhjXFSmCeyuSGI9PuPzykhBDk5OdixYweys7Pxxz/+0SIXE0QiEWN3VVlDJ8rFnuh3nglCKNjY/2fMdkQB2Nhg7lRbbIifgWVPhTEeY1RX6T/44AOsXbtW641aU1NDCy2fz0d6ejoyMjKQnJyMiRMn0u8TCoW4ceMGI00gk8lGVBNrCpqamvD73/8eHR0dFtW9Yjj6+vpQWFhIz2b5fD64XC49m42IiBgzIqtE13vZ2uDxeEhMTMTRs98hr2OCyeI1iOieKW7E/h9qIJYrMNTRbGwAR3s77FzJwYsJAairq8NLL72EgYEB5OTkYP78+foORWcUCgX4fL7WhoA9PT3w9/dHYGAgbMO4qHWeCwVsQKD9hhscLwBcunQJL730EhYtWoTDhw+rLW4RQnD79m18/fXXyM3N1ehzMFRNrGqawBJmXRRF4fjx49izZ4/FdK8YisePH+Pq1au0yFZXV2PBggX0bDYmJsbi2+nog673srXyxolz+KaewMbeAUMJoSHj1Vt0n3xI1RDJqOHf/H84TbBFvEMr/ufwO9ixYwe2bdtm9AuZEIKuri6NglpfXw8+nw8vL68hjattbW11jvf15ACUnn0PFy5cUFulJ4SgrKyMntHK5XKGz0FXV5daTey0adMYaYKoqCiLe0KwpO4V2pDJZCgtLaXTBWVlZYiKiqLTBQkJCRb3ezUWul7bO1eGW6XwmitevUS3sqUP6z4thkimGP2JFTJ8+FwI0hbM1fX0agzuADBYYB0cHIY0rh7u5tIWb9NfnsUU7m/hlrBG688SuQSJ4jKc2L8dkydPBkVRDJ8DJycnZGRkYNWqVSCEMLrOKmtiVZsi6lMTa2xUu1fs2bMH2dnZFmMqT1EUKisraZEtKipCSEgILbKJiYlwdXU19zBNjj73stMEO/xjcwLm+1pPqsGc8eo1vTxWcB9i+egH/eTME/B9nRhpC0b+IzKZDM3NzVpTAEKhUE1Mk5OTGWYr+qBPvLb2DpgU9xzt3HXu3Dl4enoiJSUF2dnZ4PP5+Pnnn3H48GGEhYUhPj4ey5cvx65duxAWFmYxojUcSl+M6dOn48aNGwbvXlFTUwOhUIinnnpqRLvSCCHg8Xh0uqCgoACenp5ITU1FVlYWTp8+PSY3YowWfa5tsVyB4wX38dGLTxl4VMZjqHiHm0TpG6/OotsllKCwtnPIvM9QEALk8zrRLZTQK4OEELS3t2tNAbS3t2PGjBmMFMCzzz5Lfz99+nSj5TD1jhfAT7f4KPjrnxHgMw1hYWG4c+cOcnNz6TRBZmYmYmNjrbJMbiS+GPogl8uxbt065OXlwcfHB3fu3NEquM3NzYwyLjs7O6SmpiI9PR1/+9vfjF4SZ20Y4162ZMwdr86im3uDr/U14Z18dP94FJBLYefiAdjYwM7NCz4v/pXxPrlcjhf++yhseXloaGhAU1MTXF1dGY//CxcuxAsvvICgoCD4+vqabRFmqHgBQNxyB31XzgIKGexcp2FG1oewdWTWyxJC4Dw3BVF+tiariTUFqr4Yt27dMkqnWHt7e2zatAlHjx5Feno6mpubMWvWLLX3SaVSLF26lN5eu3v3bgQHB5t9QdGSGera7vhqN8QN5U+UxtYeU5ash1tChtr7bADklvPx+yXBRhypYRgqXv6JLIBQ6Cs4hb6CU3AMisX0tf9f7X36xKuz6Na0CxilFUoo6WN0/89hOIXEY9qqN9Ff9AUEpd/Azs1L7b0K2MJmii+ys7MRGBiIgIAAi53laYtXiaT5FrzXH4StwyS0ntyK7gvH4fks0zjZdoIDktNfxF+ft8C+TTpgal+MZcuWwdbWFr6+vrh06RI2bNiglmKws7NDTU2N1aRjLAFt17aorgzihpvw/q/DcPAOgbj5Dggl13gMsZxCTduAsYdqEIa6l3235oxojUafeHW+MgVizb984a2fARBMe24HbCc6wj1lI2wmai+AnxEQjF//+teIiIiwWMEFtMerZFJEChy8QzDB3QcTvQIh7WjQchyZMYZncn744QfMmzcPEokEVVVVJjEiUgrpokWLkJ+fr/E9dnZ2rOCOEq3Xtp09QAjEjRWgpGI4zoqAU0DkEMexjmt7uHt55MfRLV6dZ7qTHTX/qLy3FTb2ExkX/uDHbOZxLLdmUxVt8Sqxn/KfR2obeweQx/1ajmMd8WpD1RcjJyfHKL4YMpkM169fR0FBAf7whz8wNoEAwMKFC3HmzBkAYK0PdUR1x+L9u/2ArXrXCaeAKLhEr0T/tX+gr+AU7CZPg+fqP8HBO0TjMS3x2hYIBKiurkZ1dTXu3r2L6upq3HaJBQKe1vvYusars+hyvCfDwb5dbZpuP8UHRC4FRVG08FJiIewmq5c4OdrbguNjHeU52uIdDdYU72AG+2Lcvn3bYE8mFEXh1q1b9OJXUVERgoKCkJKSAqFQqGYSk5CQgEmTJqGvrw9TpkyBXC4f0xsWDIFQKERZWRmj3lvZxWN69Cq0KQBN5aoey7fCY/lWyAVdaD/zFjrPHYDv1hy195n72u7q6qJFVfVrb28vOBwOwsPDMWfOHGzcuBFVCh+cqew1272s85W6JtYXh3+uVft/l8hfoTcvB13n/4Jpz76J/qK/g0hFGo9BAKyJ8dV1CCZFW7yjwZriVUW1e8W5c+f09sUghODevXt0dUF+fj48PDyQkpKCDRs24PPPPx/ShrKqqgp8Ph9BQUFYsWLFuOiPNhqG6+KRmZmJQ4cO0TsWu4QSLPpLHkAxRUhUVwZpVzNcI5+BraMzbOzsoW3blimubUIIWltbNYqrTCbDnDlzaHFdvnw55syZg1mzZqmlmxYLJThTmaf1PDb2EyHtbBx6LNA9Xp1Fd5qLA7ihnrhY3cEovbCd6AyPldvQ/dMxtBxaDTsXD9i6TH3ygalgYwMkh3laRYkJoD3ekWJt8QLM7hXZ2dn46quvdN6dxefzGU0VCSFITU3FqlWr8P7778PPz29Ex3n48CFeffVVLFu2DGlpaUhNTbXotQBToOziofTdGLxjcePGjUPuWNR2bVMyMfqLzqIv/zMAgK2zG7w0reQb+NqmKAqNjY1qwlpdXQ1HR0daWCMiIpCZmYnw8HD4+PiMuEJluHvZNXYVBCVfo+lOARyDn8b0zN2M1/WN1yQ70prfWwNnTiKmpb1G/x+7i8WyUfXF+Oyzz4bsXqGJzs5OFBQU0ELb29uL5ORkeudXSEgIW8alA2KxGDdv3mTMYnt7e+kdiwkJCTp18TDHtS2TyXD//n01ca2trYWHhwctrqpfDbWRxZz3slG8FwTXv4XjrPmw95iJnosf4VHlBXhv+Bscpgf936DZ/dqWikKhwJEjR/Duu++OyhdDIBDgypUrtMg2NDRg8eLFtMjOmzePrSoYJSPp4hEfH2+wHYvGurZFIhF4PJ6auNbX18PPz09NXDkcjkm2Ylul94KSwc5End8fwuM7hQAIYDcBkxPWwH3xC2PGmWisOjFVVVUhKysLzs7O+PTTTxESonmVGngy47p27Rq9+HX79m3ExcXRlodPPfWURbuJWSLm7OKhRJ9rWyAQoKamhiGsd+/eRWtrK4KDg9XENTQ0VM0H2tSY4142mJ/uLX4fjhfcRz6vEzZ4UjysROlJmRzmieykEKt5xB6KsRSvRCLBgQMHcOzYMbz77rvYtGmT2qO/XC5HWVkZPZMtLS3F3LlzacvDhQsXWp0huTnR1MWDz+cjNjbWpF08NDHctU0RgvnT7DDX9gH66m/RItvT04OwsDCGsM6ZMwdBQUEW/QfY1PeywTtHdAslyC3no6ZtAAKxDJMdJ4Dj44o1MdbvNq8Ja4+3pKQEWVlZCAoKYnSvoCgKVVVVtMheuXIF/v7+dLpg8eLFZjNEtzaG6uKhKrCm7OIxHIQQ3KlrxqnCatzh96Fr4BEe93aht/EORHfywQn0Vcu3+vv7W3UKyVT3skX1SGMxHcruFV988QWOHDmCzMxM1NXV0dUF+fn5cHNzo9MFSUlJ8PJS38rNoo6mLh5SqZSRh3366acxZYr5n4BGWimg+nU0lQIs6rCiOw5Rdq+IiorC0qVLUVpairy8PCgUClpkU1JSNBrKsDAhmrPSkgAADDVJREFUhKChoQEFBQUW3cVDJpOhrq6OzrOqVgpMnTqVTgUYo1KAhQkruuOI+vp6bN68GSUlJXBzc4NIJGKUcYWGhrIzGB0QiUQ4cuQInJ2dzd7FQyQSoba2Vm3WWldXB19f9ZQAh8PR22eaZXSwojuGGRgYwJUrV5CXl4evv/4aTU1N8PPzw+bNm7Fy5UpERkZadQ7O2BBCLPaPkKZKgerqavD5fAQHB6uJa2hoKLvQaSGwojuGEIvFKC4uphe/KisrERkZif7+fggEApw6dQopKSnmHqZFQghBfX09iouLQQhBRkaGRYhUV1eXxnyrpkqB8PBwBAcHW3SlAAsrulaNXC5HeXk5LbLFxcWYM2cOnZNtamrCzp07sWHDBuzevdsiRERfHj58CB6Ph8WLF+t1HGVNrDIPW1paCgcHByQkJODll18Gl8tlPAVIJBLU1tbC1dUVAQEBDEMnfVF6CmgSV4lEojHfau2VAuMZVnStCEIIqqqq6A0Jly9fhp+fH734xeVy4ebmhqamJmzZsgVtbW3IyclBbGysuYduED7++GMcOHAAbW1tKCkpQVRU1IhSAMqaWFV/Aj6fj5iYmBHVxPb09CAtLQ2VlZVYu3YtTp06NaL+bIOhKApNTU0aDVscHBzUhHXOnDlspcAYhBVdC0b5yKsU2fz8fLi6utIz2eTkZEZrHIqicOLECezevRtvvPEG3nrrrTH1qFlXVwdHR0fs27cP8+bNQ3Z2tkbx4/P5jHKt8vJyvWpi5XI5KioqIBQKsXfvXuTl5Q0501WtFFAVVx6PR1cKqIpreHj4kK5qLGMLVnQtjNbWVrpW9tKlS5DJZHR1QUpKitbuujweD5s2bQJFUcjJyQGHwzHxyE3H+++/j8rKSnz++edqovv48WMkJSVh+vTpBq+J5fF4WLt2LSorK9VeoygK3377Lf70pz+xlQIsQ8KKrpnp6elBQUEBLbIdHR10GVdKSgo4HM6Qj5cymQyHDh3Ce++9hz179iA7O3vM5/ouX76Mt99+G8XFxWqvURQFGxsbozyS9/f3IykpCd9//z18fdW9VNvb29HR0cFWCrAMiWXsORxHCIVCFBUV0Ytf9+7dw6JFi5CSkoKzZ88iMjJyxLnCmzdvYuPGjZg+fTpu3LihdRZsrXR1dcHd3V3t9xEaGorHjx/j4cOHarvk9PmD093dTacCli5diqCgIMbrrq6u8PDwQFVVFXx9fdVSDN7e3vD2Vm97w8KiCiu6RkYikaC4uJhOGdy8eROxsbFISUnBkSNHEBcXp9YDbDhEIhH27t2LnJwcHDx4EL/97W+tfrFFIpGo+cT29PSAz+fDxYXZY8/b2xsBAQFob2+Hl5fXqCoJCCFoa2vTuJilrBQIDw9HbGys2iKdra0twsPD0d7eTn/PwjJa2PSCgVEoFCgvL6fTBb/88gs4HA6dk01MTISzs7POxy8qKkJWVhbmz5+Po0ePWuXMSrlAqFpNUFVVhdDQUMZilzaf2ObmZjz//PNoaWnB8uXL8cYbbyAiIoLxHmNUCvT19WHbtm345ZdfsH79eqxatQpRUVEG//2wjG1Y0dUTQgju3r1LpwsKCwsxc+ZMOifL5XLh7u6u93kGBgawY8cOnDt3DkePHsXq1asNMHrToFoTq/zn4ODAENjY2NgR+cT29/cjPT0d7u7u4HK5SEpKQmQksy24UCjE8uXL0dzcbLBKAbFYjLS0NIjFYkRERCA2NhZr1qxh/QlYRg0rujrQ0NDA6Pfl7OxMVxgkJycbfPb5448/YsuWLVi6dCkOHTpkEBE3Fqo1scqZbEtLC+0Tq/ynaSHKkGOQSCTjvncai2XCiu4IaGtrQ35+Pi20IpGI4cZlrE603d3deP3111FUVIRPPvkES5cuNcp59EHpE6tME9y8eRN+fn4618QODAygurqaTgU0NDTg7NmzY6remGV8w4quBnp7e1FYWEiLbGtrK5KSkujZbHh4uFEXrggh+Oc//4lt27Zh3bp12Ldvn0XM2h49eqTmEyuRSBgCO9KaWNVKAdWv3d3d4HA4jJTAypUrzd7WhYXFULCiiydiUlRURC9+8Xg8LFy4kJ7NRkdHj3rLp660trYiOzsb9+7dw8mTJ7FgwQKTnHcwFEWhpqaGkSa4d+8e7ROrFNqhfGKVlQKDhXVwpYDqV9ZTgGWsMy5FVyqVoqSkhBbZ8vJyxMTE0OmC+Ph4k/uhEkKQk5ODHTt2YOvWrdi5c6dJx9DZ2clIE1y/fh0eHh6MWaw2n1hlpYAmw5aJEydq7D4wY8YMqy9zY2HRhXEhugqFAhUVFXS64Nq1awgNDaXTBYmJiWZ9fK+rq8PmzZshEAiQk5OD+fPnG/V8EokEFRUVjKaIPT09iIuLYyx2eXp6Mn5O6SkwWFyVngKaxJX1FGBhYTImRZcQgpqaGlpkCwoK4O3tTYssl8vF1KlTzT1MKBQKHDlyBO+++y62b9+O1157zeCNCVVrYpUCO1xNrFgsBo/HUxPX+vp6zJw5U01cWU8BFpaRY3DR7RJKkHuDj5p2AQRiOSY72oPjPRmZscbtjtvY2EinC/Ly8uDg4MCoMPDx8THKeXWNt6qqCllZWXBycsLJkycREhJikPH09fXh+vXrjFSBtprYgYEBuvuAqrjy+XwEBQWp+biyngIsLPpjMNGtbOnDsYL7KKztBABINPSOTwrzRDY3BJF++js+dXR00HWyeXl5EAqFtMCmpqYavRGgrvFKpVIcOHAAH374Ifbv349NmzbpvHAkl8tRVVXFqCZobm5Wq4l1cnLSmG/t6urS2H0gJCSELdFiYTESBhHdM8WN2P9DDcRyBYY6mo0N4Ghvh50rOXgxIWBU5+jr60NhYSE9m+Xz+eByufRsNiIiwmQLM7rGW1paiqysLAQEBODEiROj3iDw4MEDRh5WtSY2Pj6eNmgZnBoQi8Ua863+/v4mq8pgYWF5gt6i+0SAqiGSUYz/bzr4HNy5/4XJcelqP+M0wRY7V4YPKbyPHz/G1atX6XRBdXU1FixYQM9mY2JiDJ7/HAna4lWiKW7HCbbgiO6i+PRBfPDBB3j++eeH/QOhrIlVTRNIJBLExcWBw+Fg6tSpoCgKjY2NbKUAC4sVoZfoVrb0Yd2nxRDJFKP+WacJdvjH5gTM933y6C2TyVBaWkqLbFlZGaKiouh0QUJCgtnaWivRJ15bSo5T6yOxZG6A2msURYHH4zHSBLW1tZg9ezZ8fX3h7OwMiUSC5uZm1NbWwt3dXaOnwOBqAxYWFstDr6nisYL7EMtHL0AAIJYrsP98GZ4WPynlunr1KkJCQpCamop33nkHixcvVrP0Mzf6xEvs7PFFRReWzA2ga2JLSkpw7do1XL9+HU5OTvDy8oKdnR0EAgEUCgUGBgZgY2ODgIAAhriylQIsLNaLzqLbJZSgsLZTa06z6S/PYgr3t3BLWKPxdUKAkmYhXB8/wKZNm3DmzBmLdmwaLl4l2uImBPjp9gN4zXoegocP4OrqSgtrYGAg5s+fz5i5hoWFsZUCLCxjEJ1FN/cGX++TOzo44Olf/z9kLAnW+1jGxhDxUhSFwJR1SAtywNy5c9lKARaWcYjOolvTLmCUSemCWE6hpm1Ar2OYCkPEa2M/EQtXZGLX86zxNQvLeEVnZxGBWG6QAQjEMoMcx9iMt3hZWFiMg86iO9nRMOVakx2t49F6vMXLwsJiHHQWXY73ZDjY62fB52hvC46Pq17HMBXjLV4WFhbjoLOKrInVv90KAbAmxnhtWwzJeIuXhYXFOOgsutNcHMAN9YS2jU7+73yntVwMeLJFNjnM06gmOIZkuHhVsbFXb6lubfGysLAYB72el19OCoGjvW579x3t7ZCdZBhnLVMxXLzSrhaAUJjoPVvtNWuMl4WFxfDoJbqRflOwcyUHThNGd5gn3gsceguwtTBUvMLbP6Pt5FZM9JkNR99wxmvWGi8LC4vhsRqXMUtivMXLwsJiOAzmp3uL34fjBfeRz+uEDZ5sfFCi9JdNDvNEdlLImJjxjbd4WVhYDIPBO0d0CyXILeejpm0AArEMkx0ngOPjijUxxu0cYS7GW7wsLCz6MSZ7pLGwsLBYKvpV+7OwsLCwjApWdFlYWFhMCCu6LCwsLCaEFV0WFhYWE8KKLgsLC4sJYUWXhYWFxYT8L7Ip2afDEqsTAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import networkx as nx\n",
    "import random\n",
    "\n",
    "def Maximum_Cut_Problem(G):\n",
    "    # arbitrary cut into sets A(True) and B(False)\n",
    "    nodes = list(G.nodes)\n",
    "    edges = list(G.edges)\n",
    "    crossing_edges = []\n",
    "    A = []\n",
    "    B = []\n",
    "    for node in nodes:\n",
    "        random_choice = random.choice([True, False])\n",
    "        if random_choice == True:\n",
    "            A.append(node)\n",
    "        else:\n",
    "            B.append(node)\n",
    "    print(\"Before A: {}, B: {}\".format(A, B))\n",
    "    for edge in edges:\n",
    "        if (edge[0] in A and edge[1] in B) or  (edge[1] in A and edge[0] in B):\n",
    "            crossing_edges.append(edge)\n",
    "    stopping = False\n",
    "    while stopping != True:\n",
    "        #random_edge = randrange(len(crossing_edges))  \n",
    "        random_node = [random.choice([1, 0]) for _ in range(len(crossing_edges))]\n",
    "        check_nodes = [crossing_edges[n][random_node[n]] for n in range(len(crossing_edges))]\n",
    "        issue_stop = True\n",
    "        for check_node in check_nodes:\n",
    "            check_node_truth = None\n",
    "            if check_node in A:\n",
    "                check_node_truth = True\n",
    "            else:\n",
    "                check_node_truth = False\n",
    "            expected_crossing_truth = not check_node_truth\n",
    "            adjacent_check_nodes = list(G.adj[check_node])\n",
    "            d_v_nodes = []\n",
    "            d_v = 0\n",
    "            C_v = 0\n",
    "            for n in adjacent_check_nodes:\n",
    "                #print(\"check_node: {}, n: {}\".format(check_node, n))\n",
    "                if expected_crossing_truth == True:\n",
    "                    if n in A:\n",
    "                        C_v += 1\n",
    "                    else:\n",
    "                        d_v +=1\n",
    "                        d_v_nodes.append(n)\n",
    "                else:\n",
    "                    if n in B:\n",
    "                        C_v += 1\n",
    "                    else:\n",
    "                        d_v +=1\n",
    "                        d_v_nodes.append(n)\n",
    "            if C_v < d_v:\n",
    "                #print(\"Before A: {}, B: {}, check_node: {}, C_v: {}, d_v: {}\".format(A, B, check_node, C_v, d_v))\n",
    "                #print(\"Before crossing_edges: {}\".format(crossing_edges))\n",
    "                issue_stop = False\n",
    "                if check_node_truth == True:\n",
    "                    A.remove(check_node)\n",
    "                    B.append(check_node)\n",
    "                    for edge in crossing_edges:\n",
    "                        if check_node in edge:\n",
    "                            crossing_edges.remove(edge)\n",
    "                    for new_node in d_v_nodes:\n",
    "                        crossing_edges.append((check_node, new_node))\n",
    "                else:\n",
    "                    B.remove(check_node)\n",
    "                    A.append(check_node)\n",
    "                    for edge in crossing_edges:\n",
    "                        if check_node in edge:\n",
    "                            crossing_edges.remove(edge)\n",
    "                        \n",
    "                    for new_node in d_v_nodes:\n",
    "                        crossing_edges.append((check_node, new_node))\n",
    "                #print(\"After A: {}, B: {}\".format(A, B))\n",
    "                #print(\"After crossing_edges: {}\".format(crossing_edges))\n",
    "        #print(issue_stop)\n",
    "        if issue_stop == True:\n",
    "            stopping = True \n",
    "    print(\"After A: {}, B: {}\\nNumber of edges in Max-Cut: {}\".format(A, B, len(crossing_edges)))\n",
    "    \n",
    "        \n",
    "                \n",
    "    \n",
    "\n",
    "G = nx.Graph()\n",
    "for i,j in zip(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't'],[(5, 25), (10, 25), (5, 20), (10, 20), (5, 15), (10, 15), (5, 10), (10, 10), (5, 5), (10, 5),   (25, 30), (30, 30), (25, 25), (30, 25), (25, 20), (30, 20), (25, 15), (30, 15), (25, 10), (30, 10)]):\n",
    "    G.add_node(i, pos=j)\n",
    "G.add_weighted_edges_from([('a', 'd', 1), ('b', 'k', 1), ('d', 'm', 1), ('c', 'n', 1), ('d', 'q', 1), ('c', 'f', 1), ('a', 'l', 1), ('l', 'm', 1), ('e', 'n', 1), ('m', 'h', 1), ('o', 'f', 1), ('h', 'p', 1), ('h', 'q', 1), ('o', 'j', 1), ('o', 't', 1), ('g', 'f', 1), ('g', 'r', 1), ('r', 'i', 1), ('j', 't', 1), ('s', 'j', 1)])\n",
    "pos = nx.get_node_attributes(G, 'pos')\n",
    "weights = nx.get_edge_attributes(G, 'weight')\n",
    "nx.draw_networkx_edge_labels(G, pos, edge_labels = weights)\n",
    "nx.draw_networkx_labels(G,pos=pos)\n",
    "nx.draw(G, pos, with_labels = True)\n",
    "Maximum_Cut_Problem(G)    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before A: ['c'], B: ['a', 'b', 'd']\n",
      "After A: ['c'], B: ['a', 'b', 'd']\n",
      "Number of edges in Max-Cut: 2\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvnQurowAAIABJREFUeJzt3XlclPX+9/EXW7mkWYpL7rmRDMMuECaaZmnmnZli5T5sGqlp6TFbtDLP6egR84cizNyppeZRi/yllrlGihA7g1tWKC4pKojsy8z9xzl2W+ICA1wzw+f5V4+Za6551x9vPn3n+l6XjdFoNCKEEKJB2CodQAghGhMpXSGEaEBSukII0YCkdIUQogFJ6QohRAOS0hVCiAYkpSuEEA1ISlcIIRqQfX2c9HJhGVuTz3L89wIKSitp2cQep/YtGePZidYP3F8fXymEELXWkJ1lU5c70tJz8ok8cIqDJ3MBKKs0/PFeE3tbjMDAPo5MD+iJa+dWdfW1QghRK0p0Vp2V7udHslm88zillVXc6Yw2NtDE3o4Fw50Y79utLr5aCCFqTKnOqpM13f+EP0ZJxZ3DAxiNUFJRxeKdx/j8SHZdfL0QQtRIdZ11+h8juXZk6y3H1nVnmVy66Tn5LN55nJIKw90PvklJhYHFO4+TcTbf1AhCCHHPlO4sk0s38sApSiuravXZ0soqVh04ZWoE0chMnTqVtm3bolKplI4iLJDSnWXS1QuXC8s4eDK32iWFi5vfpfR0OhiqwM6ell7/h4cGTfnTMUYj7D+Ry5XCMrmqQdyzyZMnEx4ezsSJE5WOIizMnToLoPR0Ovlxn0NVJfYPdaDDpOXYNnngj/frorNMmnS3Jp+97XsObbrQfuIyOs+NpYX7MAoStlF28ddbjrMBtqbc/jxC/NWAAQN4+OGHlY4hLNCdOgug9Iyedi//nUdCY6gqyufi1vdvOcbUzjKpdI//XvCnSyxu9vDgIO5v3xNbW3seHhIK9vdRfCzuluNKKw0cv3DdlBhCCHFP7tRZAM36+NGkoxMOD3WgZb9RlJ8/ccsxpnaWScsLBaWVt33vyq6VFGbth8ryP16rKrxa7bEbtnxJxDh3U6IIK+To6Eh2djbNmjW758/k5+fz8ssvs2vXrnpMJiyV4+h3aNbL57bv2z/U8Y9/dmjb/T/Lo9UoKK2odQaTSrdlk+o/Xnr2KIXp3/HQU2E84DoUW/v7OL30BYxUv5DyypgXWF7NGC9ETbVq1YqdO3cqHUOYqVmbU4lNO3/b9yvzzv3xzxWXssHWrtrjWjZxqHUGk5YXnNq35H77W09RVfKf0duhVXsALu+I+NPEe7Mm9rY4dWhhSgwhhLgnt+usG4pPxFN2/iQVeRcoSPyS+zr0uuUYUzvLpNJ90bNTta837+XDfR0f49KWheQsHU35pd+wub/6/0U0Ai96VH8eIarz0ksv4efnx4kTJ+jUqRM6nU7pSMJC3K6zbmjSRcXvG+Zyfk0wds0exHH0O7ccY2pnmbS80OaB+wno7cj3xy7ecglGhwn/vOvnjQYDTi2NcrmYqJFNmzYpHUFYqLOnjmE4p4e2TmDz55mz67ztd/28jQ0M6uNoUmeZvDni1YE9aWJf/brH3dxvb4v+38t4+eWXyc3NNTWKEEJUq7S0lLfeeouhQ4cyybs9Te6r3bzZxN6O6QN7mpTF5NJ17dyKBcOdaOpQs1M1dbDl3eecyTy4g44dO+Li4sLnn39OHd70TAghiIuLw9XVlZ9//pmMjAzenjaBt4c/VqvOWjDcCXUn0+42ZjZ3GUtKSkKj0dCxY0eioqLo0qVLXcQSQjRSBQUF/O1vf+Prr7/mf/7nfxg1atSf3rfou4wBjPftxuYQX57u24777W1p8pdfCJvY23K/vS1P923H5hDfW8J7eXmRlJRE//798fT0JDIyEoOhZjekEEIIgB07dqBSqaioqCArK+uWwgXTO6u26vQm5jdcKSxja8pZjl+4TkFpBS2bOODUoQUvetzbXdiPHz9OUFAQAFqtFicnp7qOKISwQrm5ucycOZOEhARiYmJ48skn7+lzpnZWTdRL6dYFg8FAVFQU7733HjNnzmTevHk4ONT+gmQhhPUyGo1s3LiR2bNnM3HiRBYtWlSjnYwNyWxL94YzZ84wbdo0zp49i06nw8vLS+lIQggzcubMGcLCwjh37hxarRZvb2+lI92R2T8NuEuXLnzzzTfMmzePESNG8MYbb1BcXKx0LCGEwgwGA5GRkXh6euLv709SUpLZFy5YwKR7s9zcXGbNmkVCQgLR0dH3vF4jhLAuN373MRqNaLVaHnvsMaUj3TOzn3Rv5ujoyIYNG1ixYgWTJ08mKCiI/Hx53I8QjUVFRQWLFy+mf//+jBs3jri4OIsqXLCw0r3h2WefRa/Xc//99+Ps7MxXX32ldCQhRD1LSkrCy8uLQ4cOkZKSQnh4OLa2lldhFrW8UJ24uDiCgoJQq9WsXLmS9u3bKx1JCFGHiouLee+991i/fj3Lli3jlVdewcbGRulYtWZ5fyb+4oknniA9PZ3evXujVqv59NNPZSuxEFZi3759qNVqzp07R2ZmJuPHj7fowgUrmHRvlpaWhkaj4eGHH2bNmjU8+uijSkcSQtRCfn4+b775Jt9++y2rV69mxIgRSkeqMxY/6d7Mzc2NhIQEhg4dSr9+/Vi+fDlVVbV71LIQQhmxsbGoVCocHBzIysqyqsIFK5t0b/bzzz8TEhJCSUkJWq0WlUqldCQhxB38/vvvvPbaa2RkZBATE8OAAQOUjlQvrGrSvVmvXr3Yu3cvGo2GQYMG8d5771FWVqZ0LCHEXxiNRtauXYtaraZXr16kp6dbbeGCFU+6Nzt37hyvvvoqP//8M1qtFj8/P6UjCSGA3377jdDQUK5cuYJWq8Xd3fqfCm61k+7NOnbsyFdffcXChQt54YUXmDlzJoWFhUrHEqLRqqqqYvny5Xh7ezNkyBASEhIaReFCIyldABsbG8aMGYNer+fatWu4uLiwe/dupWMJ0ejo9Xr8/f35+uuviY+PZ+7cudjbm/S4RovSKJYXqvPdd98RFhbGgAED+Ne//kXr1q2VjiSEVSsrK2PJkiVERkayePFigoKCLHJHmaka37/xfz399NNkZmby0EMPoVKp+Pe//y2bKoSoJ0eOHMHDw4PU1FTS0tIICQlplIULjXjSvVl8fDxBQUH07NmTVatW0bFjR6UjCWEVCgsLefvtt9m8eTMrVqxgzJgxFr+jzFSN80/NX/j5+ZGSkoK7uzvu7u5ER0fL89mEMNHu3btxcXEhLy8PvV7P2LFjG33hgky6t9Dr9Wg0Gpo2bUpMTAy9evVSOpIQFuXq1avMnj2bAwcOsGbNGp5++mmlI5kVmXT/QqVScfjwYZ5//nn8/Pz4+OOPqaysVDqWEGbPaDSyZcsWVCoVDz74IHq9Xgq3GjLp3sFvv/1GSEgIV69eRafT4ebmpnQkIczSjQ1IJ0+eRKfTyQakO5BJ9w66d+/O7t27ee211xg6dChvvfUWpaWlSscSwmwYDAaio6Nxc3PD1dWV1NRUKdy7kEn3Ht18Mw6tVssTTzyhdCQhFHXq1CmCg4MpLi5Gq9Xi4uKidCSLIJPuPWrfvj1btmzh73//O+PGjWP69OkUFBQoHUuIBldZWcnHH3+Mr68vI0eO5PDhw1K4NSClW0OjRo0iKyuLiooKVCoVO3bsUDqSEA0mLS0NHx8fdu/eTWJiIq+//jp2dnZKx7Iosrxggn379hEcHIyPjw8rVqzA0dFR6UhC1IvS0lI++OADYmJi+Mc//sHkyZPlmttakknXBE8++SSZmZl07NgRFxcXNmzYIFuJhdWJi4vDzc2NEydOkJGRwZQpU6RwTSCTbh1JSkpCo9HQsWNHoqKi6NKli9KRhDBJQUEB8+fPJzY2lpUrV/LCCy8oHckqyKRbR7y8vEhKSsLf3x9PT08iIyNlK7GwWDt27EClUlFWVoZer5fCrUMy6daD48ePExQUBIBWq8XJyUnhRELcm9zcXGbNmsWRI0eIjo5m8ODBSkeyOjLp1gMnJyd++OEHXnrpJZ544gkWL15MRUWF0rGEuC2j0ciGDRtwcXGhQ4cOZGZmSuHWE5l069mZM2cICwvj3Llz6HQ6vLy8lI4kxJ+cOXOGadOmkZOTg06nw9vbW+lIVk0m3XrWpUsXduzYwdy5cxkxYgRvvvkmxcXFSscSAoPBQGRkJJ6envj5+ZGUlCSF2wBk0m1Aubm5zJw5k8TERGJiYhg0aJDSkUQjdfz4cYKDgzEYDGi1Wh577DGlIzUaMuk2IEdHRzZu3EhERASTJk0iODiY/Px8pWOJRqSiooLFixfTv39/AgMDiYuLk8JtYFK6ChgxYgR6vR4HBwdUKhWxsbFKRxKNQFJSEl5eXvz4448kJycTHh7eaJ9TpiRZXlDYDz/8QHBwMGq1mpUrV9K+fXulIwkrU1xczMKFC1m3bh3Lli3jlVdekR1lCpI/cwobMGAA6enp9OrVC7Vazdq1a2Ursagz+/fvR61Wk5OTQ2ZmJuPHj5fCVZhMumYkLS0NjUZD69atWbNmDd27d1c6krBQ+fn5vPnmm3z77besWrWK5557TulI4r9k0jUjbm5uJCQkMGTIELy9vVm+fDlVVVVKxxIWJjY2FpVKhb29PXq9XgrXzMika6Z+/vlngoODKS0tRavVolKplI4kzNzNTzeJiYlhwIABSkcS1ZBJ10z16tWLffv2MXXqVAYNGsTChQspKytTOpYwQ0ajkbVr16JWq+nZsydpaWlSuGZMJl0LcO7cOaZPn86pU6fQ6XT4+voqHUmYiezsbEJCQrh8+TI6nQ53d3elI4m7kEnXAnTs2JHY2Fjee+89Ro0axaxZsygsLFQ6llBQVVUVEREReHl5MXjwYBITE6VwLYSUroWwsbFh7Nix6PV68vLycHFxYffu3UrHEgrIysrC39+f2NhY4uPjmTdvHvb29krHEvdIStfCtG7dmnXr1hEVFUVoaCiTJ0/m6tWrSscSDaC8vJxFixYxcOBApkyZwr59++jVq5fSsUQNSelaqKeffprMzEwefPBBVCoVW7ZskU0VVuzIkSN4eHiQnJxMamoqoaGhsoXXQskPaVYgPj4ejUZD7969WbVqFY888ojSkUQdKSws5O2332bz5s1EREQwduxY2VFm4eRPpRXw8/MjNTUVV1dXXF1diY6OluezWYHdu3fj4uJCXl4eer2ewMBAKVwrIJOuldHr9Wg0Gpo1a0ZMTAw9e/ZUOpKooatXrzJ79mwOHDhAVFQUzzzzjNKRRB2SSdfKqFQqDh8+zMiRI/H19eXjjz+msrJS6VjiHhiNRrZs2YJKpaJly5ZkZmZK4VohmXSt2K+//kpoaChXr15Fp9Ph5uamdCRxG+fPn2f69OmcPHkSnU6Hn5+f0pFEPZFJ14o9+uij7N69m/DwcIYOHcqCBQsoLS1VOpa4idFoJCYmBldXV9RqNampqVK4Vk4m3Ubi999/Jzw8HL1eT0xMDE888YTSkRq9U6dOERISQmFhITqdDhcXF6UjiQYgk24j0b59e7Zu3cqSJUsYN24cr776KgUFBUrHapQqKyv55z//ia+vLyNGjCA+Pl4KtxGR0m1kRo0ahV6vp6ysDJVKxY4dO5SO1Kikp6fj6+vLd999R2JiIrNnz8bOzk7pWKIByfJCI7Zv3z5CQkLw8fEhIiICR0dHpSNZrdLSUj744ANiYmL4xz/+weTJk+Wa20ZKJt1G7MknnyQjI4NHHnkEFxcXNmzYIFuJ68GPP/6Im5sbJ06cID09nSlTpkjhNmIy6QoAfvrpJzQaDZ07dyYqKorOnTsrHcniFRQUMH/+fGJjY1m5ciUvvPCC0pGEGZBJVwDg7e1NUlISfn5+eHh4EBkZKVuJTbBz505cXFwoKytDr9dL4Yo/yKQrbnHs2DGCgoKwtbUlJiYGJycnpSNZjNzcXGbNmsWRI0eIjo5m8ODBSkcSZkYmXXGLxx57jLi4OAIDA+nfvz+LFy+moqJC6VhmzWg0snHjRlxcXGjfvj0ZGRlSuKJaMumKOzpz5gxhYWGcO3cOnU6Hl5eX0pHMTk5ODmFhYeTk5KDT6fD29lY6kjBjMumKO+rSpQs7duzgzTff5Nlnn2Xu3LkUFxcrHcssGAwGVq1ahbu7O76+viQlJUnhiruSSVfcs0uXLjFz5kx++uknYmJiGDRokNKRFHPixAmCgoIwGAzExMTQt29fpSMJCyGTrrhnbdu2ZdOmTURERDBp0iSCg4PJz89XOlaDqqio4KOPPsLf35/AwEDi4uKkcEWNSOmKGhsxYgR6vR4HBwdUKhWxsbFKR2oQycnJeHt7ExcXR3JyMuHh4fKcMlFjsrwgTPLDDz8QHByMWq1m5cqVtG/fXulIda64uJiFCxeybt06li5dyvjx42VHmag1+TMtTDJgwADS0tLo2bMnrq6urF271qq2Eu/fvx9XV1dycnLIzMxkwoQJUrjCJDLpijqTmpqKRqOhTZs2REdH061bN6Uj1Vp+fj5z585l165drFq1iueee07pSMJKyKQr6oy7uzuJiYkMHjwYLy8vIiIiqKqqUjpWjX399deoVCrs7OzQ6/VSuKJOyaQr6sXPP/9McHAwpaWl6HQ6nJ2dlY50VxcvXuS1114jLS2NmJgYAgIClI4krJBMuqJe9OrVi3379jFlyhQGDhzIwoULKSsrUzpWtYxGI+vWrUOtVtOjRw/S09OlcEW9kUlX1Ltz584xffp0Tp06hU6nw9fXV+lIf8jOziY0NJTc3Fx0Oh3u7u5KRxJWTiZdUe86duxIbGws7733HqNGjWLWrFkUFhYqmqmqqooVK1bg5eXFk08+SUJCghSuaBBSuqJB2NjYMHbsWPR6PXl5ebi4uLB7925FsmRlZeHv78+XX37J4cOHmTdvHg4ODopkEY2PlK5oUK1bt2bdunWsXr2akJAQJk+ezNWrVxvku8vLy1m0aBEDBw5kypQp7N+/n969ezfIdwtxg5SuUMQzzzyDXq/nwQcfRKVSsWXLlnrdVJGQkICHhwdJSUmkpqYSGhoqW3iFIuSHNKG4+Ph4NBoNvXv3ZtWqVTzyyCN1du6ioiLefvttvvjiC5YvX05gYKDsKBOKkj/1QnF+fn6kpqaiVqtxdXUlJiamTqbe77//HpVKxZUrV9Dr9YwbN04KVyhOJl1hVjIzM9FoNDzwwANs3rwZR0fHGp+jtLSUGTNmsHv3bqKionjmmWfqIakQtSOlK8xOVVUVJ06coGvXrjRv3rzGny8pKeHy5cu0atWKFi1a1ENCIWpPSldYlJKSEpo2bUpVVRV2dnZKxxGixmRNV1iM999/H39/fy5duoSdnR0Gg0HpSELUmJSusAibNm1i3759ODk5MWfOHAC55EtYJFleEBahvLycU6dO0blzZ4YOHcqsWbMIDAyUZQZhcaR0hcX58ssv+fDDD9m/fz8PPvggRqNRLgUTFkNKV1ikkJAQAKKjoykrK8Pe3l4mXmERpHSFRSooKGDYsGH06dOHsrIyPvzwQ7p37650LCHuyl7pAELURllZGRcvXqSoqIioqCgpXGExZNIVZunq1as0bdqUpk2bVvv+vHnzaN68Oe++++4t75WXl1NRUUHTpk3lCgdhdqR0hVm5fPkys2bNIikpiX379t325jd3umqhuLiYsWPHcu3aNbRaLX369KnPyELUiIwBwiwYjUY2bdqESqWiXbt2JCcn3/FuY3f60axZs2Zs376dwMBA/P39+eijj6ioqKiP2ELUmEy6QnE5OTlMmzaN06dPo9Pp6NevX52d+/Tp04SFhXHhwgV0Oh2enp51dm4hakMmXaEYg8HA6tWr8fDwwMfHh+Tk5DotXICuXbuyc+dO3njjDYYPH87cuXMpLi6u0+8QoiZk0hWKOHHiBMHBwVRWVqLVaunbt2+9f+elS5eYOXMmSUlJREdHM2jQoHr/TiH+SiZd0aAqKir46KOP8Pf3Z8yYMcTFxTVI4QK0bduWTZs28a9//YuJEycSEhJCfn5+g3y3EDdI6YoGk5ycjLe3Nz/88APJycm89tpriuwie+6559Dr9djZ2aFSqYiNjW3wDKLxkuUFUe9KSkpYuHAha9euZenSpYwfP95s7pVw8OBBgoODcXNzY+XKlbRr107pSMLKyaQr6tWBAwdQq9WcPn2azMxMJkyYYDaFCxAQEEB6ejo9evRArVazbt26en0qsRAy6Yp6ce3aNebOncvOnTuJjIxk5MiRSke6q9TUVDQaDY6OjqxZs4Zu3bopHUlYIZl0RZ3bvn07zs7O2NjYoNfrLaJwAdzd3UlISODJJ5/Ey8uLFStWUFVVpXQsYWVk0hV15uLFi8yYMYOUlBS0Wi0BAQFKR6q1kydPEhwcTFlZGTqdDmdnZ6UjCSshk64wmdFoZP369ajVarp3705GRoZFFy5A79692b9/P1OmTGHgwIEsWrSI8vJypWMJKyCTrjBJdnY2oaGhXLp0CZ1Oh4eHh9KR6tzZs2eZPn06v/76KzqdDh8fH6UjCQsmk66olaqqKlasWIGXlxeDBg0iMTHRKgsXoFOnTnz99de88847PP/887z++usUFRUpHUtYKCldUWNHjx6lf//+fPnllxw+fJi//e1vODg4KB2rXtnY2BAYGIher+fKlSuoVCq+//57pWMJCySlK+5ZeXk5ixYtIiAggEmTJrF//3569+6tdKwG1bp1a9avX8/q1asJDg5mypQpXL16VelYwoJI6Yp7kpCQgKenJ0lJSaSmphIWFtaon8rwzDPPkJmZSYsWLVCpVGzdulU2VYh7Ij+kiTsqKirinXfeYdOmTSxfvpzAwECz2lFmDg4fPoxGo8HJyYnIyMg73nxdiMY7qoi72rNnDy4uLuTm5pKZmcm4ceOkcKvx+OOPk5aWhouLC25ubmi1Wpl6xW3JpCtukZeXx5w5c9i7dy9RUVEMGzZM6UgWIyMjg6CgIB544AGio6Pp2bOn0pGEmZFJV/zJtm3bcHZ2pnnz5uj1eincGlKr1cTHxzNixAh8fX1ZunQplZWVSscSZkQmXQHA+fPnCQ8P59ixY+h0Oh5//HGlI1m8X375hZCQEK5du4ZOp8PV1VXpSMIMyKTbyBmNRrRaLW5ubjg7O5OamiqFW0d69OjBnj17mD59Ok899RQLFiygtLRU6VhCYTLpNmI3JrGCggJ0Oh1qtVrpSFbrwoULhIeHk5WVhVarpX///kpHEgqRSbcRqqysZOnSpfj4+DB8+HDi4+OlcOtZhw4d2LZtG4sXLyYwMJDw8HCuX7+udCyhACndRiYjIwM/Pz927dpFQkICc+bMwd7eXulYjcbo0aPR6/WUlJSgUqnYuXOn0pFEA5PlhUairKyMDz/8kDVr1rBkyRKmTp0q19wqbO/evYSEhODn50dERARt2rRROpJoADLpNgKHDh3Czc2No0ePkp6ejkajkcI1A4MHDyYjI4N27dqhUqnYtGmTbKpoBGTStWLXr1/nrbfeYtu2baxcuZLRo0crHUncRmJiIhqNhq5du7J69Wo6d+6sdCRRT2TStVK7du1CpVJRXFxMVlaWFK6Z69evH8nJyfj4+ODh4cHq1asxGAxKxxL1QCZdK3P58mVef/11Dh06RHR0NEOGDFE6kqiho0ePEhQUhL29PTExMfTp00fpSKIOyaRrJYxGI5s2bUKlUtG2bVsyMzOlcC1U3759iYuLY8yYMfj7+/PRRx9RUVGhdCxRR2TStQI5OTlMnz6d7OxsdDod/fr1UzqSqCOnT58mNDSU33//HZ1Oh6enp9KRhIlk0rVgBoOB1atX4+Hhgbe3N8nJyVK4VqZr167s2rWLOXPmMHz4cObOnUtxcbHSsYQJZNK1UCdPniQoKIjKykq0Wi19+/ZVOpKoZ5cuXWLGjBkkJycTExPDwIEDlY4kakEmXQtTUVHBkiVLePzxx3nxxReJi4uTwm0k2rZtyxdffMGyZcuYMGECoaGhXLt2TelYooakdC1ISkoK/fr14+DBgyQlJTFjxgzs7OyUjiUa2MiRI9Hr9djY2ODs7MzXX3+tdCRRA7K8YAFKSkpYuHAha9euZenSpYwfP152lAkADh48SFBQEB4eHnzyySe0a9dO6UjiLmTSNXMHDx7E1dWV06dPk5GRwYQJE6RwxR8CAgLIyMige/fuqNVq1q9fL1uJzZxMumbq2rVrzJ07l507dxIZGcnIkSOVjiTMXEpKChqNhrZt27JmzRq6deumdCRRDZl0zdD27dtRqVTY2Nig1+ulcMU98fDwIDExkUGDBuHl5cWKFSuoqqpSOpb4C5l0zcjFixeZMWMGKSkpaLVaAgIClI4kLNTJkycJDg6mvLwcrVaLs7Oz0pHEf8mkawaMRiPr169HrVbTvXt3MjIypHCFSXr37s3+/fuZNGkSAwcOZNGiRZSXlysdSyCTruJubPO8ePEiOp0ODw8PpSMJK3P27FmmTZtGdnY2Wq0WHx8fpSM1ajLpKqSqqopPPvkET09PAgICSExMlMIV9aJTp05s376dBQsW8Pzzz/P6669TVFSkdKxGS0pXAUePHqV///5s3bqVQ4cOMX/+fBwcHJSOJayYjY0N48aNIzMzk8uXL+Pi4sKePXuUjtUoSek2oPLyct5//30CAgKYNGkSBw4ckHuligbVpk0bPvvsMyIjI9FoNEydOpW8vDylYzUqUroNJDExEU9PT3766SdSUlIICwvD1lb+8wtlDBs2DL1eT/PmzXF2dmbr1q2yqaKByA9p9ayoqIh33nmHjRs3EhERQWBgoOwoE2bl8OHDaDQanJyciIyM5JFHHlE6klWTUase7dmzB7VaTW5uLnq9nnHjxknhCrPz+OOPk5qaikqlws3NDa1WK1NvPZJJtx7k5eUxZ84c9u7dS1RUFMOGDVM6khD3JCMjA41GQ4sWLYiOjqZnz55KR7I6MunWsW3btqFSqWjevDl6vV4KV1gUtVpNfHw8zz77LL6+vixdupTKykqlY1kVmXTryIULF3j11Vc5duwYWq0Wf39/pSMJYZJffvmFkJAQCgojxUHWAAAKXklEQVQK0Ol0qNVqpSNZBZl0TWQ0GtHpdLi6uuLs7ExqaqoUrrAKPXr0YM+ePYSFhTFkyBDefvttSktLlY5l8WTSNYFMAqKxuHDhAuHh4Rw9elT+T85EMunWQmVlJcuWLcPHx4fhw4cTHx8vhSusWocOHdi2bRsffvghY8aMITw8nOvXrysdyyJJ6dZQRkYGfn5+7Nixg4SEBObMmYO9vb3SsYRoEKNHjyYrK4uSkhJUKhU7d+5UOpLFkeWFe1RWVsaHH37ImjVrWLJkCVOnTpVrbkWjtmfPHkJCQnj88ceJiIigTZs2SkeyCDLp3oPDhw/j7u5OVlYWaWlpaDQaKVzR6A0ZMoTMzEzatWuHSqVi06ZNsqniHsikewfXr1/nrbfeYtu2baxcuZLRo0crHUkIs5SYmIhGo6Fr166sXr2azp07Kx3JbMmkexu7du1CpVJRVFSEXq+XwhXiDvr160dycjL9+vXDw8OD1atXYzAYlI5llmTS/YvLly/z+uuvc+jQIdasWcNTTz2ldCQhLMrRo0cJCgrC3t6emJgYuX3pX8ik+19Go5EvvvgCFxcXHB0dyczMlMIVohb69u1LXFwcL774Iv7+/ixZsoSKigqlY5kNmXSRZ0gJUV+ys7MJCwuTZwDepFFPugaDgaioKNzd3fH29iY5OVkKV4g61K1bN3bt2sXs2bMZNmwY8+bNo6SkROlYimq0k+7JkycJDg6mvLwcrVaLs7Oz0pGEsGoXL15k5syZJCcnExMTw8CBA5WOpIhGN+lWVFTw97//HX9/f0aPHs2PP/4ohStEA2jXrh1ffPEFy5YtY8KECYSGhnLt2jWlYzW4RlW6KSkp9OvXj/379/PTTz8xY8YM7OzslI4lRKMycuRI9Ho9NjY2ODs7s337dqUjNahGsbxQUlLCokWL+PTTT/nnP//JhAkTZEeZEGbg4MGDBAUF4eHhwSeffEK7du2UjlTvrH7SPXjwIK6urvz2229kZGQwceJEKVwhzERAQAAZGRl069YNtVrN+vXrrX4rsdVOuteuXWPevHl88803rFq1ipEjRyodSQhxBykpKWg0Gtq2bcuaNWvo1q2b0pHqhVVOuv/7v/+LSqXCaDSSlZUlhSuEBfDw8CAxMZGBAwfi5eXFJ598QlVVldKx6pxVTbqXLl1ixowZjf6SFCEs3YkTJwgODqaiogKdTkffvn2VjlRnrGLSNRqNfPbZZ7i4uNC1a1cyMjKkcIWwYH369OHAgQNMmjSJgIAA3n//fcrLy5WOVScsftI9ffo0oaGhss1QCCuVk5PD9OnTyc7ORqfT0a9fP6UjmcRiJ92qqipWrlyJl5cXAQEBJCYmSuEKYYU6d+7M9u3bWbBgASNHjmT27NkUFRUpHavWLLJ0jx49yhNPPMG///1vfvzxR+bPn4+Dg4PSsYQQ9cTGxoZx48ah1+vJzc3FxcWFPXv2KB2rViyqdMvLy/nggw8ICAhgwoQJHDx4UO7VKUQj0qZNGz777DMiIyPRaDRMnTqVvLw8pWPViMWUbmJiIp6eniQkJJCSksK0adOwtbWY+EKIOjRs2DD0ej3NmzfH2dmZbdu2KR3pnpn9D2lFRUW8++67bNiwgeXLlzNu3DjZUSaE+MOhQ4cICgriscceIzIykg4dOigd6Y7MelTcu3cvarWaixcvotfreemll6RwhRB/4u/vT2pqKn379sXV1RWtVmvWW4nNctLNy8vjjTfeYM+ePURFRTFs2DClIwkhLEBGRgYajYaWLVsSHR1Njx49lI50C/v6OOnlwjK2Jp/l+O8FFJRW0rKJPU7tWzLGsxOtH7j/jp/98ssvee211xg1ahR6vZ4WLVrUR0QhhBVSq9XEx8ezYsUKfHx8mD9/PjNnzsTe/s5VZ0pn1VSdTrrpOflEHjjFwZO5AJRV/v9HMDext8UIDOzjyPSAnrh2bvWnz164cIHw8HCOHj2KVqvF39+/rmIJIRqhX375heDgYK5fv45Op0OtVt9yjCmdVVt2CxcuXFgXJ/r8SDYzN6dx8tJ1Kg1Gqgx/7vIbr/16uYjYtPO0amqPulMrjEYjn376KS+++CLPPPMMGzdu5NFHH62LSEKIRuzhhx9m4sSJ2NnZMXHiRK5fv46/v/8fU29tO8tUdTLpfn4km8U7j1FSYbj7wf/V1MGW0H5t+SZiHvn5+eh0OlxdXU2NIoQQtzh//jzh4eEcO3YMrVbLb3Yda9VZC4Y/xnjfbiZlMbl003PyGRdzhJKKmt+CzVhRxtg251nyRthd11yEEMJU27ZtY8bCZTR5dh5VNnfunHNRwdg+8BAdxn/8x2tNHezYHOJr0sRr8iVjkQdOUVpZu3te2jrcz/VOvlK4okamTp1K27ZtUalUSkcRFmb06NEMnbWUqlpWX2llFasOnDIpg0mle7mwjIMnc6ntrGwE9p/I5UphmSkxRCMzefJkvv32W6VjCAt0ubCMw9nXwKZ21Wc0mt5ZJo2YW5PP3va90nPHyf3qIwyFeYARB8euPKKJvOU4G2BryllCB5jf9XTCPA0YMIDs7GylYwgLdKfOKso6yJVdKzBWlmPXos1/yqkapnaWSaV7/PeCP11icYOhspyLG+fj0LozHaZ8gq2dPYVZB6o9R2mlgeMXrpsSQwgh7sltO6u8mMvfLKNpD2/ajHyT/LjPuf5TLHYt295yrKmdZVLpFpRWVvt6kX4vVFXSfuJSbO3vA6Cl54jbnmfDli+JGOduShRhhRwdHcnOzqZZs2b3/Jn8/Hxefvlldu3aVY/JhKVyHP0OzXr53PJ6YcYewEibFxZga2vLw4ODKEz/7rbnKSitqHUGk0q3ZZPqP15xOQcb+/v+KNy7eWXMCyzf+r4pUYQAoFWrVuzcuVPpGMJMzdqcSmza+Vter8w7j43dfX+6c6Ftkwdue56WTWp//26Tfkhzat+S++1vPYVDm84YK8sxVN79mUZN7G1x6iBbfYUQ9e92nWXfqgPGqnIMhv+/9GAoLaz2HKZ2lkml+6Jnp2pfb64aDHb2XPx8LpVF+RhKCylIqX76MAIvelR/HiGq89JLL+Hn58eJEyfo1KkTOp1O6UjCQtyusx5wfQqw4fJXSzBUlpO37/9iLC+p9lhTO8uk5YU2D9xPQG9Hvj928U+Xjdna30e7lz4i96uPOLdyPGCDg2M3WnoM/9PnbWxgUB/HOr+hhLBumzZtUjqCsFC37az7mtF6+EyufBdJztIXsGvR5j9XMPxFXXSWojvS6mJ3hxBC1ITSnWXyjjTXzq1YMNyJpg41O9V/9jE7SeEKIRqU0p1VJ/tvb9wAYvHO45RWVt1xh5qNDTSxt2PBcCeTbxwhhBC1oWRn1en9dDPO5rPqwCn2n8jFhv9cRHzDjXtTDurjyPSBPWXCFUIoTonOqpfH9VwpLGNrylmOX7hOQWkFLZs44NShBS961P1d2IUQwlQN2Vlm+Yw0IYSwVmb9NGAhhLA2UrpCCNGApHSFEKIBSekKIUQDktIVQogGJKUrhBANSEpXCCEakJSuEEI0oP8H+Of3YZwI4UYAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "G = nx.Graph()\n",
    "for i,j in zip(['a', 'b', 'c', 'd'],[(5, 25), (10, 25), (5, 20), (10, 20)]):\n",
    "    G.add_node(i, pos=j)\n",
    "G.add_weighted_edges_from([('a', 'b', 1), ('b', 'c', 1), ('d', 'a', 1), ('c', 'd', 1)])\n",
    "pos = nx.get_node_attributes(G, 'pos')\n",
    "weights = nx.get_edge_attributes(G, 'weight')\n",
    "nx.draw_networkx_edge_labels(G, pos, edge_labels = weights)\n",
    "nx.draw_networkx_labels(G,pos=pos)\n",
    "nx.draw(G, pos, with_labels = True)\n",
    "Maximum_Cut_Problem(G)    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2-SAT\n",
    "Input: n Boolean variables $x_1$, $x_2$, ..., $x_n$  (can be set to True or False)<br>\n",
    "m clauseses of 2 literal each<br>\n",
    "\n",
    "eg:  $(x_1 ∨ x_2)$ ^ $(¬x_1 ∨ x_3)$ ^ $(x_3 ∨ x_4)$ ^  $(¬x_2 ∨ ¬x_4) $\n",
    "\n",
    "output: \"yes\" if there is an assignment that simultaneously satisfies every dataset, \"no\" otherwise\n",
    "\n",
    "eg:  \"yes\", via <br>\n",
    "$x_1$ = $x_3$ = True <br>\n",
    "$x_2$ = $x_4$ = False\n",
    "\n",
    "### Papadimitriou's 2-SAT Algorithm\n",
    "\n",
    "![Papadimitriou's 2-SAT Algorithm](images/25_Papadimitrious_2_SAT_Algorithm.png)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "x: [True, False, True, 1]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import math\n",
    "import random\n",
    "from random import randrange\n",
    "\n",
    "\n",
    "\n",
    "def satisfy(x, clauses):\n",
    "    truth_clauses = []\n",
    "    for c in clauses:\n",
    "        if c[0] >= 0:\n",
    "            x1 = x[c[0]-1]\n",
    "        else:\n",
    "            x1 = not x[-c[0]-1]\n",
    "        if c[1] >= 0:\n",
    "            x2 = x[c[1]-1]\n",
    "        else:\n",
    "            x2 = not x[-c[1]-1]\n",
    "        truth_clauses.append(x1 or x2)\n",
    "    return truth_clauses\n",
    "    \n",
    "    \n",
    "\n",
    "    \n",
    "def Papadimitrious_2SAT_Algorithm(parameters_count, clause_count, clauses):\n",
    "    truth = False\n",
    "    for _ in range(int(math.log2(parameters_count))):\n",
    "        x = [random.choice([1, 0]) for _ in range(parameters_count)]\n",
    "        for z in range(2*(parameters_count**2)):\n",
    "            print(z)\n",
    "            truth_clauses = satisfy(x, clauses)\n",
    "            if 0 not in truth_clauses:\n",
    "                truth = True\n",
    "                break\n",
    "            while True:\n",
    "                random_choice = randrange(clause_count)\n",
    "                if truth_clauses[random_choice] == 1:\n",
    "                        continue\n",
    "                var_choice = random.choice([1, 0])\n",
    "                if var_choice == 0:\n",
    "                    x[abs(clauses[random_choice][0])-1] = not x[abs(clauses[random_choice][0])-1]\n",
    "                else:\n",
    "                    x[abs(clauses[random_choice][1])-1] = not x[abs(clauses[random_choice][1])-1]\n",
    "                break    \n",
    "        if truth == True:\n",
    "            break\n",
    "    print(\"x: {}\".format(x))\n",
    "    return truth\n",
    "        \n",
    "            \n",
    "        \n",
    "Papadimitrious_2SAT_Algorithm(4, 4, [[1, 2], [-1, 3], [3, 4], [-2, -4]])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Challenge Problem\n",
    "\n",
    "In this assignment you will implement one or more algorithms for the 2SAT problem. Here are 6 different 2SAT instances:\n",
    "\n",
    "2sat1.txt <br>\n",
    "2sat2.txt <br>\n",
    "2sat3.txt <br>\n",
    "2sat4.txt <br>\n",
    "2sat5.txt <br>\n",
    "2sat6.txt <br>\n",
    "\n",
    "The file format is as follows. In each instance, the number of variables and the number of clauses is the same, and this number is specified on the first line of the file. Each subsequent line specifies a clause via its two literals, with a number denoting the variable and a \"-\" sign denoting logical \"not\". For example, the second line of the first data file is \"-16808 75250\", which indicates the clause ¬x16808∨x75250.\n",
    "\n",
    "Your task is to determine which of the 6 instances are satisfiable, and which are unsatisfiable. In the box below, enter a 6-bit string, where the ith bit should be 1 if the ith instance is satisfiable, and 0 otherwise. For example, if you think that the first 3 instances are satisfiable and the last 3 are not, then you should enter the string 111000 in the box below.\n",
    "\n",
    "DISCUSSION: This assignment is deliberately open-ended, and you can implement whichever 2SAT algorithm you want. For example, 2SAT reduces to computing the strongly connected components of a suitable graph (with two vertices per variable and two directed edges per clause, you should think through the details). This might be an especially attractive option for those of you who coded up an SCC algorithm in Part 2 of this specialization. Alternatively, you can use Papadimitriou's randomized local search algorithm. (The algorithm from lecture is probably too slow as stated, so you might want to make one or more simple modifications to it --- even if this means breaking the analysis given in lecture --- to ensure that it runs in a reasonable amount of time.) A third approach is via backtracking. In lecture we mentioned this approach only in passing; see Chapter 9 of the Dasgupta-Papadimitriou-Vazirani book, for example, for more details."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import urllib3\n",
    "\n",
    "def testcase_2SAT(url):\n",
    "    http = urllib3.PoolManager()\n",
    "    r1 = http.request('GET', url)\n",
    "    IntegerMatrixStringJoin = r1.data.decode('utf8').split('\\n')\n",
    "    IntegerMatrixStringJoin.remove('')\n",
    "    count = int(IntegerMatrixStringJoin[0])\n",
    "    IntegerMatrixStringJoin.remove(IntegerMatrixStringJoin[0])\n",
    "    clauses = []\n",
    "    for i in IntegerMatrixStringJoin:\n",
    "        node_coord = i.split(' ')\n",
    "        x = int(node_coord[0])\n",
    "        y = int(node_coord[1])\n",
    "        clauses.append([x, y])\n",
    "    Papadimitrious_2SAT_Algorithm(count, count, clauses)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "testcase_2SAT(\"https://d3c33hcgiwev3.cloudfront.net/_02c1945398be467219866ee1c3294d2d_2sat1.txt?Expires=1564790400&Signature=ffgIgPVzU4MZQOse2WViVRgwkJWXXOghEUcg4LbzJDd6g0gP0rGnzMGE1mmxRr65wBY4cEp~d0QjEobbPthI5ZaYGjDuNP2JpipoNZhFHt6tN4kNv65sBF63MW43tQ-9KCflTwj3gTZmlRbNfXim41EnbUQANRbP~KHNZ3V4EFk_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A\")\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Output:  Stopped at iteration 119822 and found the value of variables 'x'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "testcase_2SAT(\"https://d3c33hcgiwev3.cloudfront.net/_02c1945398be467219866ee1c3294d2d_2sat2.txt?Expires=1564876800&Signature=Cj7fz4VWGs~PKGNKVtooo2DqvN6sUBjGxiECHx0YiZzjj20TsT3tNs-LIQa1WQD3cPWKATEo2hwKAvWVARDGJb8phaDpRvxY4K-Mc4alYVgSurdXEJAHegMYacFfr5s6IOBDImPQWGAGuNwl4-s-2bjXuu2P7BTKR3fYLSbmkUk_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "testcase_2SAT(\"https://d3c33hcgiwev3.cloudfront.net/_02c1945398be467219866ee1c3294d2d_2sat3.txt?Expires=1565049600&Signature=i4p9N0UQ9XNOq3KpyV1eKPULKVFebC5pHsK~nlPOD14-wuZRjZYAudHdEqLDcLfzBGYtHRfsDvmy8X5AnQz35mMaKxgs4QAd3ouDErD0HtraFErGqR0XrVpWD8GIZR0pwKDxDGudcBPzV2GIYC18ISw0KLIaJtHsq2NJQJ82blM_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "testcase_2SAT(\"https://d3c33hcgiwev3.cloudfront.net/_02c1945398be467219866ee1c3294d2d_2sat4.txt?Expires=1565049600&Signature=HMM~HxCgWppVo2nS94NHiWX1Q7QJrQLwaj3Jawn03sf9JSTC0cwosXrnSaom2HYucohp-EmezuYUNIeifU~IVj6JVrji0S~tycAiIEK9-axNjSmt8QXHiaCsk9AbB0iOB1TuhSm5RLoQ8GB8opsLcqIG2hxUUEc0xkZy9V2Vb0U_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A\")\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "testcase_2SAT(\"https://d3c33hcgiwev3.cloudfront.net/_02c1945398be467219866ee1c3294d2d_2sat5.txt?Expires=1564876800&Signature=jvQdJDaAs8HzO20foYGLMXBt~E9-csHCB~hi8TPNjMzo4qku6FUZ17Hynzm3-e~L3Tqv-DQsiOGZ4xC9iZxriRAdnKQwAOiXPqwpv-i8R90szhPKoVKMSLeQip~tNDBHp0s3Lyns2vZwWtR82w60dzkSDOFGFeT8QE-BPySBaS0_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A\")\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "testcase_2SAT(\"https://d3c33hcgiwev3.cloudfront.net/_02c1945398be467219866ee1c3294d2d_2sat6.txt?Expires=1564876800&Signature=AJwEQNYLc7krEQ2kyPVpbsiF9woiLPtzUpIu5f9BDD8bPvKs7W9HV9-v0fimcFvzH9gHQknQIJoSmR6Np7jZmxUce9AI2nnrBNooPcDwqP8uDf9WZ0yx~H0JCQ0uoBXjKBkVopb4aRjzP34txUWXTRwHYbEIV31tAnCxxI7AP-8_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A\")\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# XXXV. THE WIDER WORLD OF ALGORITHMS \n",
    "\n",
    "### Stable Matching \n",
    "### Gale-Shapley Proposal Algorithm\n",
    "### Bi-Partite Matchings\n",
    "### Maximum Flow Problem\n",
    "### Selfish Flow\n",
    "### Braess's Paradox\n",
    "### Linear Programming , Convex Programming ,  Integer Programming \n",
    "### Geometric Algorithm - eg. Clustering"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}