2021/Day 03.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bit set counts\n",
    "\n",
    "- https://adventofcode.com/2021/day/3\n",
    "\n",
    "We are tasked with counting bits in each column of input, to produce two binary numbers. While there are [some great algorithms for bit counting](https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive), the fact that we are counting bits across columns means we need to use a slightly different approach.\n",
    "\n",
    "The input, can be 'processed' by indexing into the column and testing if that column is equal to `'1'`, and summing these booleans (which in Python have integer values `0` and `1`) gives us the number of rows with the bit set. You can then compare that value with the number of lines and set the corresponding bit in gamma and epsilon (with epsilon being the inverse of gamma). By starting at the left-most column, and left-shifting the accumulated gamma and epsilon values, we naturally build up the bits in the correct order.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def power_consumption(report: list[str]) -> int:\n",
    "    width = len(report[0])\n",
    "    threshold = (len(report) + 1) // 2  # handles odd and even line lengths\n",
    "    gamma = epsilon = 0\n",
    "    for k in range(width):\n",
    "        # The puzzle description just talks about 'most common'; it doesn't\n",
    "        # matter to _my_ puzzle input if we break ties in favour of 1s or 0s.\n",
    "        one_most_common = sum(line[k] == \"1\" for line in report) >= threshold\n",
    "        gamma = gamma << 1 | one_most_common\n",
    "        epsilon = epsilon << 1 | (not one_most_common)\n",
    "    return gamma * epsilon\n",
    "\n",
    "\n",
    "test_report = \"\"\"\\\n",
    "00100\n",
    "11110\n",
    "10110\n",
    "10111\n",
    "10101\n",
    "01111\n",
    "00111\n",
    "11100\n",
    "10000\n",
    "11001\n",
    "00010\n",
    "01010\n",
    "\"\"\".splitlines()\n",
    "\n",
    "assert power_consumption(test_report) == 198"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 1: 845186\n"
     ]
    }
   ],
   "source": [
    "import aocd\n",
    "\n",
    "diagnostic_report = aocd.get_data(day=3, year=2021).splitlines(False)\n",
    "print(\"Part 1:\", power_consumption(diagnostic_report))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2: Reducing the input numbers based on bit counts\n",
    "\n",
    "Instead of accumulating a bit for each column in two numbers, we need to reduce the input lines based on the outcome. We'll have to assume that the puzzle inputs will always lead to a a single line out output for this process.\n",
    "\n",
    "For each column index, calculate the threshold, determine if the `'1'` count is high enough, filter the lines based on the column value and and repeat until there is a single line left. Only then do we need to convert from string of binary digits to a number.\n",
    "\n",
    "This approach takes $O(n \\log_2 n)$ time as we repeatedly pass over the lines but (roughly) half the number each time.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def life_support_rating(report: list[str]) -> int:\n",
    "    width = len(report[0])\n",
    "\n",
    "    def reduce(lines: list[str], filter_on=\"01\") -> int:\n",
    "        for k in range(width):\n",
    "            threshold = (len(lines) + 1) // 2\n",
    "            one_most_common = sum(line[k] == \"1\" for line in lines) >= threshold\n",
    "            lines = [line for line in lines if line[k] == filter_on[one_most_common]]\n",
    "            if len(lines) == 1:\n",
    "                return int(lines[0], 2)\n",
    "\n",
    "    oxygen_generator_rating = reduce(report)\n",
    "    co2_scrubber_rating = reduce(report, filter_on=\"10\")\n",
    "    return oxygen_generator_rating * co2_scrubber_rating\n",
    "\n",
    "\n",
    "assert life_support_rating(test_report) == 230"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 2: 4636702\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 2:\", life_support_rating(diagnostic_report))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Optimising part 2 using a binary tree\n",
    "\n",
    "We can also solve this challenge using a binary tree.\n",
    "\n",
    "Instead of repeatedly looping over the lines to count and then filter, we could build a binary tree structure from the inputs. Each node has left and right subtrees for `0` and `1`, as well as a count of the number of lines that have the same prefix up to this point. Producing the two values is then just a question of following the correct branch down to the leaf, all the while shifting the collected value and including the selected direction via bitwise OR, like in part 1. Here, \"following the correct branch\" means comparing the two counts at that node in the tree and following the higher or lower count to the next node; and what direction you followed determines if a `0` or `1` is added to the accumulating value.\n",
    "\n",
    "This approach is also a $O(n \\log_2 n)$ solution; constructing the btree loops over all $n$ lines and then over $\\log2 n$ bits on each line; reading out the numbers is a fixed cost at the end.\n",
    "\n",
    "And while I'm fond of using OOP for many of my AoC solutions, the binary tree here can trivially be stored in a list instead; just like\n",
    "a [the most common implementation of a heap](https://en.wikipedia.org/wiki/Heap_%28data_structure%29#Implementation), a given node for binary value $v_k$ at a given depth $k$ is found at $2^{k} - 2 + v_k$. We'll need a list of length $2^{k + 1} - 2$, and because each cell represents a line count, the values all start at `0`. E.g., given the inputs `001`, `101`, `110` and `111`, you'd create a btree with the following structure:\n",
    "\n",
    "<!--\n",
    "digraph G {\n",
    "  graph [splines=line,size=3];\n",
    "  node [shape=circle,fontname=\"Arial,Helvetica Neue,Helvetica,sans-serif\",fontsize=10.0];\n",
    "  edge [fontname=\"Arial,Helvetica Neue,Helvetica,sans-serif\",fontsize=10.0,dir=none,labeldistance=3];\n",
    "\n",
    "  root -> node0 [taillabel=\"0\"];\n",
    "  root -> node1 [taillabel=\"1\",labelangle=25];\n",
    "  node0 -> node00 [taillabel=\"00\"];\n",
    "  node0 -> node01 [taillabel=\"01\",labelangle=30,labeldistance=2];\n",
    "  node1 -> node10 [taillabel=\"10\",labeldistance=2];\n",
    "  node1 -> node11 [taillabel=\"11\",labelangle=25];\n",
    "  node00 -> node000 [taillabel=\"000\"];\n",
    "  node00 -> node001 [taillabel=\"001\",labelangle=40,labeldistance=2];\n",
    "  node01 -> node010 [taillabel=\"010\"];\n",
    "  node01 -> node011 [taillabel=\"011\",labelangle=25];\n",
    "  node10 -> node100 [taillabel=\"100\"];\n",
    "  node10 -> node101 [taillabel=\"101\",labelangle=25];\n",
    "  node11 -> node110 [taillabel=\"110\",labelangle=-40,labeldistance=2];\n",
    "  node11 -> node111 [taillabel=\"111\",labelangle=25];\n",
    "\n",
    "  root[label=\"4\",style=dashed];\n",
    "\n",
    "  node0[label=\"1\"];\n",
    "  node1[label=\"3\"];\n",
    "\n",
    "  node00[label=\"1\"];\n",
    "  node01[label=\"0\"];\n",
    "  node10[label=\"1\"];\n",
    "  node11[label=\"2\"];\n",
    "\n",
    "  node000[label=\"0\"];\n",
    "  node001[label=\"1\"];\n",
    "  node010[label=\"0\"];\n",
    "  node011[label=\"0\"];\n",
    "  node100[label=\"0\"];\n",
    "  node101[label=\"1\"];\n",
    "  node110[label=\"1\"];\n",
    "  node111[label=\"1\"];\n",
    "}\n",
    "-->\n",
    "\n",
    "![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAkAAAAFiCAYAAAAeFmeWAAAgAElEQVR4nOzdf5DT9Z0/8PeuMjLYXCIei63bS1wt2vWGZDyZOWfLJfSrVdoyWceDcRSaFK8KSpuV9sTaSqIoKrRkrwf4AzBrS6V65XZHb3B6zpm15aQCGlehMoqNIzB4CH4QRejuss/vH/Qdkt3NJrv5/Hi/k+djhhndH/m8d/eVz+f5ef/6CAAzQURERFQ7WgQYgIiIiKi2MAARERFRzWEAIiIioprDAEREzuju7kZ3dzcymYzTTSGi2sMARETWyWaz6OjoQFtbGwKBANLpdO5zQogh/0KhEOLxuGPtJaKawQBERObr6OhAa2trLtj4/X7EYrGC3p50Ol3wL5lMIhaLIRaL5b6ms7MTXV1dTvwIRFTdGICIyFzpdBpCCASDQaRSKRiGMebXikQiEELA5/Oho6PDxFYSUY1jACKiyqXTaWSz2dz/5/93pbLZbC4IDR5GIyIaIwYgIho7wzDQ1tYGIYTlc3ey2SyCwSCEEEgmk5Yei4iqHgMQEY1NJpNBIBCA2+1GKpWy7bipVIorx4ioUgxARDR6mUwGHo8Hfr/f1OGusbSDYYiIxoABiIhGJ5vN5sJPJROczRAMBuHxeBiCiGi0GICIaPTi8bjj4Qc4PQfJ7/fD5/Mp0R4i0gYDEBHpTYagQCDgdFOISB8MQERUnsGbFKokk8nYshKNiKoGAxARlSY3N+zs7HS6KUUlk0kIITgfiIjKwQBERCMzDAM+nw/BYNDpppTETRKJqEwMQEQ0slQqBSGEo8vdiYhMxgBERCPz+XyIRCJON6NsmUwGbW1tTjeDiNTGAERExenY+yMnRHM4jIhGwABERMUZhqFlkPD7/Vr1WhGR7RiAiKj6yJ4rIqIiGICIaHjZbFaroa982WyWw2BENBIGICIaXiwWg9/vt/QYq1atwtSpUy15ba/Xy40RiagYBiAiGl4wGLR0Hs3rr78OIQRcLpclrx8Oh7XYu4iIHMEARETDE0IgmUxa8trHjx/HlClT0NjYaFkAIiIaAQMQEQ3Pyjk03//+99HS0oJHH32UAYiInMAARERDWTmJ+IUXXoAQAnv37sW6dessC0CGYaC7uxuGYVjy+kSkNQYgIhpKPvzU7AB06NAhNDQ0YMOGDQBgaQCy6mcgoqrAAEREQ2WzWcTjcdOXwd95550QQuDOO+/E4sWLEQqFIITA4sWL8cEHH5h6LBmAdF3KT0SWYgAiIvs8/vjjmDdvXu7ftGnTIITAvHnz8O6775p6LBmAiIiGwQBERM6xcggsmUwyABFRMQxARDS81tZWpFIpS49hZQCKx+Nwu92WvDYRaY8BiIiGZ/VGiFYLh8MIh8NON4OI1MQARETDi8fjCAQCTjdjzDweDx+FQUTFMAAR0fA6OzshhNB2H51wOIxMJuN0M4hITQxARDQ8wzAsfRwGEZGDGICIqLhIJKL1MBgRUREMQERUXGdnJ7xer9PNGJV0Oo1AIKDt0B0R2YIBiIiqSygUQjAYdLoZRKQ2BiAiqh58/hcRlYkBiIhKSyaTCIVCTjejpEAgwN4fIioHAxARlZbJZJRfERaPxyGE4NJ3IioHAxARlScej8Pj8SgZMOSSfW58SERlYgAiovL5/X54PB4lV1hx3g8RjQIDEBGVzzAM+P1+ZZaZq9AGItISAxARjU42m4XX63V8KCyTySAQCCAWiznaDiLSEgMQEeknk8nA4/HA7/ezF4iIxoIBiIjG7te//jU8Hg8SiYRtx0wkEhBCMPwQUSUYgIhobF555RUIIRAOhyGEQCAQsHQicjabRSAQgBAC1157LcaPH48333zTsuMRUVVjACKi0TMMAxdeeCGuu+46AKeHpPx+P4QQCIVClgWhSCSCbDaLU6dOoaWlBZdccgmOHz9uybGIqKoxABHR6F133XW48MILhwxBpVIpBINBCCEqGp7KZrNIJBLw+XxFJzl/+OGHmDx5MubMmTPm4xBRzWIAIqLRefjhhzFu3Dhs37696Ndks9ncfyeTSfh8PrS2tiKRSKC9vR3d3d3o7u4uCEmJRAKhUAgejwdCCLjdbkQikRFXm23duhX19fVYu3atKT8bEdUMBiAiKp8MHP/2b/9W9vdks1nE43GEw2F4vV4IIXL/8ofKvF4vwuEw4vH4qIbQ7r//fowbNw5vvPHGKH4SIqpxDEBEVJ7Dhw9j8uTJCIfDpryeYRimrOIaGBjAjBkz4PP5cOzYMRNaRkQ1gAGIiEpTPWSYHc6IqOoxABFRacuWLVN+mEkOz/3iF79wuilEpD4GICIamU4TjR966CHlgxoRKYEBiIiK022p+cDAAK677jr4fD7uEk1EI2EAIqLh6brZ4OBNGomIhsEARETDW7p0KcaPH4/du3c73ZRR2759O84++2z8/Oc/d7opRKQmBiAiGuqll15CXV0d1q1b53RTxmzlypU4++yzR9ywkYhqFgMQkQ4GBgaQTCYxbdo0NDc3Y/ny5RgYGLDkWB9++CHOP/98beb9jKTYIzvMtnv3bjQ0NOD999+39DhEZBoGICIdbNiwAUIIPPzww1i6dCmEEFi5cqXpx9F13k8xdswH2rlzJ5qamiCEwN69ey07DhGZigGISAculwv3339/7v+XLVuGhoYG9Pf3m3qcH//4x9rO+ylGzgd65JFHTH/tVCoFIQSmTp3KAESkFwYgItUdPXoUQghs3bo197E//OEPEELgww8/NO04L7zwAurq6vDUU0+Z9pqqSCaTOPvsswt+h2Z47LHHsHnzZvT09EAIgffee8/U1yciyzAAEanuzTffhBACb7/9du5ju3fvhhACPT09phxj//798Hg8+O53v2vK66koHA5j8uTJOHz4sOmvzQBEpB0GICLV7dy5E0IIvPPOO7mP7dmzB0IIU3Y87uvry02uPnHiRMWvp6pjx47B5/NhxowZpk8gZwAi0g4DEJHqPvjgAwghsGPHjtzH/vjHP0IIgSNHjlT8+j/60Y8wYcIEvPvuuxW/lureeOMNjBs3Dg888ICpr8sARKQdBiAi1f3lL3+BEKJgT55HH30UQoiKX/uFF16AEALPPPNMxa+li9WrV6O+vt7U+UAMQETaYQAi0sGdd96JxsZG/O53v8OWLVvQ2NiIe++9t6LXlPN+br31VpNaqQ+z5wMxABFphwGISAeHDx/GNddcAyEEhBCYM2cOPv/88zG/Xm9vL6ZNmwa/31/V836KMXs+EAMQkXYYgIh0cuTIEXz66acVv04sFoPL5UI2m628UZp64403MH78eCQSCaebQkT2YwAiqjVdXV0QQqCrq8vppjjuscceQ319PV566SWnm0JE9mIAIqol2WwWLpcLd9xxh9NNUcacOXNw/vnnm7qpJBEpjwGIqFb09vbC7/fD7/ejt7fX6eYo4/jx47jkkkvQ0tKCU6dOOd0cIrIHAxBRrbj99ttrft5PMbt378b48ePx05/+1OmmEJE9GICIasF//ud/QgiBzs5Op5uirA0bNkAIgf/+7/92uilEZD0GIKJq9+c//xl/8zd/gx/84AdON0V58+bNw9/+7d9i//79TjeFiKzFAERUzTjvZ3Q4H4ioZjAAEVWzRYsWcd7PKMn5QPfcc4/TTSEi6zAAEVUr7vczdk8++STq6uq4PxBR9WIAIqpGcr+fRYsWOd0UbXF/IKKqxgBEVG0478ccnA9EVNUYgIiqzfe//33O+zGJnA/0k5/8xOmmEJG5GICIqgnn/Zhv/fr1nA9EVH0YgIiqBZ/zZR3OByKqOgxARNWA836sxflARFWHAYioGsRiMc77sZicD3Tvvfc63RQiqhwDEJHuOO/HPuvWreN8IKLqwABEpDM57+f22293uik1g/OBiKoCAxCRrvr6+jjvxwGcD0RUFRiAiHTV1tbGeT8OkfOB4vG4000horFhACLS0QsvvMB5Pw57/PHHOR+ISF8MQES62b9/PzweDxYuXOh0U2qenA90+PBhp5tCRKPDAESkk76+PkybNo3zfhQh5wPNmDEDAwMDTjeHiMrHAESkkzvvvJPzfhQj5wMlEgmnm0JE5WMAItIF5/2o67HHHkN9fT22bt3qdFOIqDwMQEQ6kPN+FixY4HRTqIhwOIzJkydzPhCRHhiAiFQn5/00Nzdz3o/Cjh07Bp/Px/lARHpgACJS3eLFizFhwgS8++67TjeFSnjjjTcwbtw43H///U43hYhGxgBEZLZsNovu7m5TJirLeT/PPPNM5Q0jW6xdu9a0+UBm1hIRFWAAIhqrTCaD9vZ2hEIhBAIBCCGK/gsEAgiFQmhvby/7Yibn/dx2223W/iBkutHOB7K6lohoCAYgotFIp9Noa2uDz+eDEAJutxuRSATxeBzxeBzpdHrIP/m5cDgMt9sNIQR8Ph/a2tqKXsDy5/2cOHHC3h+SKlbOfKBKaikSiQyppUwmY/NPSaQ1BiCicmSzWbS2tkIIAb/fj1gshnQ6PabX6uzsRCwWg9frhRAC0Wh0SBD64Q9/yHk/mpPzgR544IGCj2ezWUSjUQgh4PV6K6qldDpdspaIaFgMQEQjMQyj4GKVSqVMff1UKpW7eCUSCRiGwXk/VWT16tW5+UCGYaCtrc3WWiKiohiAiIrJZDLweDxwu92mX6zyGYaBeDwOt9uNv/u7v4PL5eK8nyryz//8z5g0aVKulpLJpKXHk7Xk8Xg4LEZUHAMQ0XBSqRSEEAiHw7bdSRuGAb/fjy984Qvs/akia9euxRe+8AUEg0Hba8nj8Vga3ok0xgBENJgcpojFYo4cPxKJQAiB9vZ2R45P5kkkEhBCIBKJOHJ8WUt8ThnREAxARPnkfB+n75qTyaSjIYwqp1otRaNRR9tBpBgGICJJXig6OzudbgqAM8NwTl9AafRU+9up1h4iBTAAEQGnl6YLISyfoDpasVgMQghOZtVIOp2GEALxeNzpphSQtTTWJfdEVYYBiEiu9nJqnkYpwWAQHo+H+7toQPVaCofDXB1GdBoDEFEgEIDf73e6GUXJFT2hUMjpplAJoVAIfr9f2T14WEtEOQxAVNvk3AjV74jlsAqHL9Qla0n1vxFriQgAAxDVOp/Pp+xwxWDBYBCBQMDpZlARutWSz+dzuhlETmIAotoVj8chhNBmbk0mk+FKHkXJ3h9daimbzbKWqNYxAFHt8ng8yq3UKSUSifDOXUE69f5IrCWqcQxAVJvkPAjV5/4MJpfr69LTUAtkz5xutaRru4lMwgBEtSkWi8Hr9TrdjDGx44GaVL54PM5aItIPAxDVJp/Pp+1jJsLhMILBoNPNoL8KBALaDX9JkUiEE+upVjEAUe2RE0CtfOTFxo0b0dzcbMlrywm3qu41U0usrKXu7m7MnTsXjY2NmD17Nvbu3Wv6MVhLVMMYgKj2yPk/Vtm0aROEEGhoaLDk9eVFl/u4OM+qWvq///s/CCGwYMEC/Nd//ReuueYaNDQ04OTJk6YexzAM1hLVKgYgqj1y+bsV5BPAp06dalkAAsCLliJkD4rZnnzySUydOhW9vb0AgFdffRVCCGzbts30Y6n0AGAiGzEAUe2Jx+OWPfrirrvuwmuvvYY1a9ZYHoB0W8JfjeLxONxut6XH6O3txeLFiyGEwOHDh01/fdYS1SgGIKo9sVjM8knEVgcgv9/Pi5YC4vG4pbW0detWuFwuCCHw2GOPWXKMYDDIWqJaxABEtScYDGofgILBoLar2KqJ1SvyPvjgAzz33HOYM2cOhBB4+eWXTT9GMBjUdhUbUQUYgKj2MACRWezakqC/vx+NjY245ZZbTH9tBiCqUQxAVHuqYQgsEAhw2EIBVg2BPfTQQ7j++usLPtbc3DzkY2bgEBjVKAYgqj3xeNzyzd/smATNHXydF4/H4fF4TH/d7du3QwiBdevW4eDBg3jkkUcghMDTTz9t+rE4CZpqFAMQ1Z5kMmnpPkCAPQGIy+CdZ9UyeOB0nTY1NUEIASEEHnnkEUuOw2XwVKMYgKj2WL0RotXkQywZgJwna8nKnZQ/+OAD9PX1WfLa3AiRahgDENUeOx6FYSU+vkAdMkCwloi0wwBEtcnv92u78iUcDiMcDjvdDPornWspEonwwbpUqxiAqDbFYjH4fD6nmzEmHo+HE6AVYtVEaDuwlqiGMQBRbZLzaDKZjNNNGZXOzk4IIZDNZp1uCv2VrrUk5y/p1m4ikzAAUe1yu93aDV20trZa9hwzGjuv16tdLUUiEXi9XqebQeQUBiCqXXICqC69KfKOXdcJt9VMt1qSvVapVMrpphA5hQGIaptOd+6hUIgTVhXm9XoRCoWcbkZZQqEQexKp1jEAUW2Td+6q74Mie39Ub2ct0+VvpEs7iSzGAEQUDAYRCASU3QvFMAz4fD72/mhAh1oKBAKsJSIGIKLT8yHcbjei0ajTTRlWIBCA2+1W9qJKZ2SzWbjdbrS2tjrdlGGFQiHWEtFpDEBEwJlhAdUeChmNRuF2u7lUWSNygnEsFnO6KQVYS0QFGICIAGDLli2YOnWqUitj5ENbVWkPlU/OLVPlbyfb09zcjO7ubqebQ6QCBiCiDRs2oL6+HjfffDPmzZsHIQTa29sdbVNbW5uSPVJUvlgspkQtJRIJCCFwxx13IBwOY9y4cXj22WcdbRORAhiAqLYtXboUQgj85Cc/yX0sHo9DCOHInCDDMNDa2qpU7wGNnezFc6qWotFoQS0NDAxg4cKFqKurw8qVK21vE5FCGICoNvX39+Pmm29GfX09NmzYMOTzqVQKbrfb1hU92Ww2N+GZS5SrR2dnp+21JFd7FaulFStWoK6uDgsXLsTAwIAtbSJSDAMQ1Z4TJ07g6quvxvjx47Fly5aiX5fJZOD1euHxeJBIJCy7eBmGgUQiAY/HA7/fz0mqVUjFWnr22Wcxbtw4hMNhnDx50pL2ECmMAYhqy5EjR3DllVfC7XZjx44dJb/eMAzE43G43W74fD50dHSY2p729nZ4PB643W7E43EuT65i+bXk8XhMr6WOjo5R11J3dzdcLheuuuoqHDt2zNT2ECmOAYisceTIESxZsgRNTU1oaWlBV1dXweeff/55zJo1C42NjbjlllvwySefWN6m999/HxdffDEaGxuxZ8+eUX1vNptFJBKBEAI+nw/RaHTIz1QOwzDQ1dWFaDQKj8eTWy7N4FM7DMMwvZZ8Ph+EEIhEIqOupV27dmHSpEm4/PLLcfDgwVG3Y6w+/fRTTJs2Db/5zW+GfG7jxo1obm62rS1UkxiAyBrz5s1DU1MTUqkUbrzxRgghsG3bNgCnT7hCCNx666144okn0NDQgJkzrS3DTCZjykk+m80iFovB7/dDCAEhBFpbW5FIJJBIJNDR0YHu7u7cv/b29tznQqFQ7nv8fj/i8bg2D88k8w1XS6FQyJFaquTmYCwOHjyIa6+9FkIIPPXUUwWf27RpE4QQaGhosLwdVNMYgMh8e/bsgRCiYL+RUCiEuXPnAgDmzp1b8NDIl19+GUIIy068L774IiZMmIBgMGhqN382m0UymUQ4HEYwGITX681dlPL/eb1eBINBhMNhpFIphh4aIpvNIpVKOVpL+cPDr7zyimmvO9jrr78Ol8uF5ubmIQFIrlqbOnUqAxBZjQGIzLdlyxYIIdDX15f72IMPPogpU6YAAK644gosX74897m+vj4IIbB582bT27Jx40acddZZmD17Nnp7e01//eG88sorEELgvffes+V4VL3krtK7du2y5XgnTpzAzJkzcc4554xpWK4c3d3dWLVqFT7//HO4XC788pe/zH3urrvuwmuvvYY1a9YwAJHVGIDIfGvXroXL5Sr42OOPP577mMvlwrp16wo+73K5sGbNGlPb8eCDD0IIgR/96Eemvm4pDEBkFrsDEACcOnUK8+fPR11dHdauXWvpsQYHIIkBiGzAAETmSyaTQ05e69evhxACACCEwJNPPlnweZfLhdWrV5tyfDtP4MNhACKzOBGApPvvvx9CCCxZssSyYzAAkYMYgMh8chJjvpUrV2Lq1KkAgKamJqxatSr3uYGBAQgh8Nxzz1V87JMnT1rehV8KAxCZxckABBQOIff395v++gxA5CAGIDLftm3bIITA22+/nfvYnDlzcMMNNwAAZs6ciZtuuin3ubfeegtCCPT09FR03KNHj+Kqq66Cy+WydBJnKQxAZBanAxBwehHB+PHjcfXVV+P48eOmvjYDEDmIAYjMNzAwgObmZoRCIfT09GD16tUQQuDFF18EcPrRAEIIrF27Fj09PZg+fTpaWloqusPct28fLr30UlxwwQWOXiwABiAyjwoBCAB27NiBiRMnIhAI4NChQ6a9LgMQOYgBiKzx+uuvo6mpCUIIuFwuLFu2LPe5/v5+LF68OLe0d/r06RUtgd+1axcuuOACXHrppdi3b58Zza8IAxCZRZUABAB79+6F1+uF1+vF3r17TXlNBiByEAMQWevAgQMFy+HzHT9+HB999FFFr5+/lf/Ro0crei2zMACRWVQKQABw6NAhBAIBTJw4saxHyRApjAGI9KXqwxwZgMgsqgUg4PSNSzkPEyZSHAMQ6elnP/sZ6urqsHDhQgwMDDjdnAIMQGQWFQMQcHoY++abb0Z9fT02bNjgdHOIxoIBiPQyMDCAhQsXoq6uDg8//LDTzRkWAxCZRdUAJN1zzz0QQiAejzvdFKLRYgAiffT29iIcDmPcuHF49tlnnW5OUQxAZBbVAxAAbNiwAXV1dZg/fz5OnTrldHOIysUARHo4duwYgsEgJkyYUPCQVRUxAJFZdAhAANDV1YVzzjkHM2fOxIkTJ5xuDlE5GIBIfQcPHsTll1+OSZMmIZPJON2ckhiAyCy6BCDgdN273W5ceeWVOHLkiNPNISqFAYjUtmfPHjQ2NuLiiy/G+++/73RzysIARGbRKQABer5fqWYxAJG6dL2jZAAis+gWgAD9emypZjEAkZp0nlPAAERm0TEAAYVz9uQjcIgUwwBE6lm7dq3Wq0rKCUDPP/88Zs2ahcbGRtxyyy345JNPhnzN7t270dDQwKGEGqZrAAJOr9qcPXs2zjrrLGzcuNHp5hANxgBEarn77rshhMB9993ndFPGrFQA2rVrF4QQuPXWW/HEE0+goaEBM2cWvg137tyZe5aaWc9dIucsWLAAixYtKvjYkSNHsGTJEjQ1NaGlpQVdXV1Dvk/nACTJ5/499NBDTjeFKB8DEKmhv7+/au4WSwWguXPnIhQK5f7/5ZdfhhAi90DYVCoFIQSmTp3KAKS5kydPYsmSJRBCIBqNFnxu3rx5aGpqQiqVwo033gghBLZt21bwNdUQgIDTvbpCCCV3bqeaxQBEzst/tlA1zBcoFYCuuOIKLF++PPf/fX19EEJg8+bNAIDHHnsMmzdvRk9PD+cSaeyzzz7DlClT4HK50NjYWBCA9uzZAyFEwZ5WoVAIc+fOLXiNaglAgLrP7qOaxQBEzqrGp0uXCkAulwvr1q0b8rE1a9YUfIwBSG8ff/wx2tracODAAcyePRvz58/PfW7Lli0QQqCvry/3sQcffBBTpkwpeI1qCkAA0N3dDZfLhauuugpHjx51ujlU2xiAyDl79+6F1+uF1+utqmGeUgFICIEnn3yy4GMulwurV68u+BgDUPUYHIDWrl0Ll8tV8DWPP/74kI9VWwACTs+Bu+CCC3DppZdi3759TjeHahcDEDnj1VdfxXnnnYcrrrgChw4dcro5pioVgJqamrBq1arc/w8MDEAIgeeee67g6xiAqsfgAJRMJtHQ0FDwNevXr4cQouBj1RiAAGDfvn346le/ismTJ6Onp8fp5lBtYgAi+z3//PMQQuAb3/gGjh8/7nRzTFcqAM2cORM33XRT7v/feustCCGGXAgYgKrH4AC0adOmIWFn5cqVmDp1asHHqjUAAcDRo0fxta99DV/4whfw0ksvOd0cqj0MQGSvDRs2oL6+HjfffDP6+/udbo4lSgWgzs5OCCGwdu1a9PT0YPr06WhpaRny+2AAqh6DA9C2bdsghMDbb7+d+9icOXNwww03FHxfNQcg4PQquXA4jHHjxuHZZ591ujlUWxiAyD733HMPhBC49957nW6KpUoFoP7+/tzeKEIITJ8+PbcEPh8DUPUYHIAGBgbQ3NyMUCiEnp4erF69GkKIIasgqz0AAad/FwsXLkRdXR33CiI7MQCR9fr7+3HzzTejvr4eGzZscLo5liv3URjHjx/HRx99ZFOryEmDAxAAvP7667nNLl0uF5YtWzbk+2ohAEmrVq1CXV0dFi5cqOUO8KQdBiCy1rFjx3D11VdjwoQJ2LJli9PNsQWfBUajceDAgYLl8PlqKQABej8DkLTDAETWqdWnQjMAkVlqLQABp98/brcbV155JY4cOeJ0c6h6MQCRNfbs2YPGxkZcfPHFNfcwTwYgMkstBiCgts8fZBsGIDJfrd/BMQCRWWo1AAG124NMtmEAInNxDJ8BiMxTywEIOD2HMBgMYsKECVXxnEBSCgMQmWft2rWoq6vD/Pnza3oVBwMQmaXWAxAA9Pb2Yvbs2TjrrLOwceNGp5tD1YMBiCo3MDCQ29cm/ynntYoBiMzCAHTG3XffDSEE4vG4002h6sAARJXJ38mVd2enMQCRWRiACtXCTvJkGwYgGrujR4/iqquugsvlQnd3t9PNUQYDEJmFAWioLVu2YPz48bj66qur8lmCZBsGIBqbffv24dJLL8UFF1zAk/MgDEBkFgag4e3YsQMTJ05EIBDAoUOHnG4O6YkBiEZv165duOCCC3DppZdi3759TjdHOQxAZBYGoOL27t0Lr9cLr9eLvXv3Ot0c0g8DEI1Od3c3XC4XrrrqKhw9etTp5iiJAYjMwgA0skOHDiEQCGDixInYsWOH080hvTAAUfmeffZZjBs3DuFwGCdPnnS6OcpiACKzMACVdvz4cVx99dUYP358zTxvkEzBAETlWb58Oerq6nDnnf2Mq2cAACAASURBVHdiYGDA6eYojQGIzMIAVJ7+/n7Mnz8f9fX1WLt2rdPNIT0wANHITp06hfnz56Ouro4nljIxAJFZGIBGJ5FIQAiBu+++2+mmkPoYgKi4EydOYObMmTjnnHPQ1dXldHO0wQBEZmEAGr2NGzfirLPOwuzZs9Hb2+t0c0hdDEA0vCNHjuDKK6+E2+3GK6+84nRztMIARGZhABqbF198ERMmTEAwGMSxY8ecbg6piQGIhnr//fdx8cUXo7GxEXv27HG6OdphACKzMACNXSaTwaRJk3D55Zfj4MGDTjeH1MMARIV40qgcAxCZhQGoMryZoxEwAKksm83a+oiJLVu2sNvYBP/zP/8Dt9uNnp4ep5tCmtu6dSvcbjdeffVVp5uiLaeG87u7u5HNZm07Ho0aA5AKMpkM2traEAqFEAgEIIQY9p/H40EoFEI0GkVHRwcMwzCtDfkPGeTEwfJks1m0t7cjFAohFAoV/bsJIRAKhdDa2or29naeFGkI1pK1Tpw4gXA4jHPOOQfPPvusaa9rGAY6OjoQjUYRCoXg8XiK/t0CgQBCoRDa2tqQyWRMawONGQOQU+SbRr5hvF4vYrEY4vE44vE40ul0wb9UKpX7nN/vLzgZtre3VxSGli5dCiEE7rnnHhN/wuqUzWbR1tYGn88HIQTcbjfC4XDub9PZ2Vnwd+vs7Mx9LhwOF5wM29raeAGrYZXWktvthhACPp+PtVSGgYEBLFy4EHV1dfj5z38+5tcxDAPt7e0FN6vBYDD3t0mlUkPO3/JzkUgEXq83d0MbjUaRTqfN+yFpNBiA7JZOp3N3eH6/H8lkckx3A4ZhIJVK5U6EHo8HiURiVK/R39+Pm2++GfX19diwYcOo21BLstksotFoQVgd64mrs7Oz4EQYjUZ58aohw9VSZ2fnmF6rs7MTsViMtTQKDz/8MOrq6rBw4cJRbepqGAYSiQQ8Hg/cbjcikQhSqdSYbj4zmUzBzWwoFGIQsh8DkF0ymUwu+ASDQVOL3TAMxOPx3N1gR0dHye/h9vHlMQwDbW1tuYtVKpUy9fVTqVRBgDVzWJPUIi+gVtaS1+tlLZVhtI/16ejoyAWfeDxu6u82nU4jGAxCCIHW1lYGWPswANkhlUrlTnpWpvxsNotIJJJ7IxV7k/IBguXJZDK5k14ymbTsODLAut1u+Hw+zg+oQvm1FI/HLTsOa6l85TzY2TCM3I1rJBKxNJx0dnbmevLMDsc0LAYgq8mubitPeoNlMhm43W4EAoEhb9i9e/fC6/XC6/Vi7969trVJN6lUCh6PB8Fg0LY7acMw4Pf74fF4xjwkQuqRteT3+1lLitm1axcuuOACXHrppdi3b1/B5zKZDAKBANxut61BUt7EtrW12XbMGsUAZBV55+B2ux1J89lsNncClG/eV155BRMnTsSVV16JQ4cO2d4mXchhikgkYvuxDcPInQDb29ttPz6Zy8laAsBaKsO+fftw6aWX4oILLsjtt5ROp20PrfnkqMFIPflUMQYgKxiG4cidw3DtkCuPHnjgAZxzzjmYOXMmTpw44VibVCd77JzugpZzuuzsOSRzyVqycvi0HMlkEkIIxGIxR9uhsqNHj+Kqq66Cy+XCsmXLcqHVyfCRTqdzPfkMQZZgALJCa2sr3G63MpPZwuEwJkyYgNbWVpw6dcrp5ihLXiicDj+SvAtUpT1UPtX+dqq1R0UnT57EN77xDUyYMMGxHrvB5HSGaDTqdFOqEQOQ2WKxGIQQSk0+lPMBeCdRXGdnp5I9LpFIpGAYk9SXTqeVrCUVz00qMQwDPp8Pfr/f6aYUUPXcVAUYgMyk8l1WNpuF2+1GKBRyuinKkSt0VLnrGywYDMLj8TC8akDWUjgcdropwwqHw/B4PMr0TqskEAjA6/Uq+T5TrXe6SjAAmSWbzSo/zi4frMg7iUKBQMCxyY7lkD14DK/qC4VCrCUNya0DVO4dk73BqtaWhhiAzCJ39lVdPB7nmyiP7LVT+cQHnBlW4W6x6pJDFar/jVhLhQzDgMfjUf7G0DAMuN1upW+yNcMAZAbZs6JD96R8E6n+ZreLz+dTduhrsGAwyDt3hfl8PmWHvgYLBoPw+XxON0MJkUgEbrdbi5tCORTGIUxTMACZIRQKadH7I8leoFp/E+l2MpF37joE7VojexJ1qSU5ZF/rtaTj78Hr9Wpz06Y4BqBKyd4fnbqTDcPIPYSxlnk8Hu1+B5FIhHfuCtKpJ1FiLekzdSGfbmFbYQxAlYrH49q9gYDTS2Jr+eQne1NUn/szmJxnwpOfOuRNkG61pOt7wEw6zP0ZjtXPJ6wRDECVCgQC2t35ATz5xWIxLYMrwJOfauQKIh3Vci3pGlyB09sZBINBp5uhOwagSsjxY10fNljLJ79AIKDd8JfEk59adL0JAk4PAQUCAaeb4Qidb4LkMJgOE7cVxgBUCVmEVlqwYAEWLVpkyWtHIpGavJBaGVzffPNNzJ8/H42NjfjWt76FP/3pT6Yfgyc/ddhxE7Rx40Y0Nzdb8tq1XEtWBdd3330XS5cuxZQpUzBr1ixs2rQJf/nLX0w9hmEY2k3eVhADUCVisZhlAeLkyZNYsmQJhBCWPQdGroKqNXL4z2zHjx9HU1MTQqEQNm7ciGnTpsHlcuHYsWOmHkdedHWaeF+tZC1ZFSA2bdoEIQQaGhoseX15Ia3FWrIquE6bNg0tLS347W9/i0ceeQRCCNx7772mH8fv92s5f0khDECVCAaDlgSgzz77DFOmTIHL5UJjY6NlAciqIKA6+aR1s61fvx5CCHz66acAgE8//RRCCKxfv970Y9XqRUs1VvYCy6fJT5061bIABFgXBFRmVfD7/e9/DyEEdu3alfvY/PnzMWXKFFOPA5y+/ug69KoIBqBKBINBSxL4xx9/jLa2Nhw4cACzZ8/G/PnzTT8GcCYA1dqKong8bskDD5csWYJrrrmm4GNf//rX8YMf/MD0Y/GRJmqwcgL0XXfdhddeew1r1qyxPADVWi1ZtRt2b28v9u/fX/Cxr3/96/jHf/xHU48DcC6gCRiAKuHz+Sw/cVgZgGp1KMWqocvZs2fjpptuKvjYjTfeiNmzZ5t+LHZ/qyEej1t+EbI6AFl1I6cyu3q/n3vuOQgh8Ktf/cr017aj9qocA1AlhBCWr6KyMgABtTmUYtXQ5axZs4YMV86dOxfXX3+96ccKBoParmKrJnbchdsRgGptKMWOBSy//e1vIYSwbBGL3NGfxowBqBIMQHqyKgAtWLAAs2bNKvjYzJkz8cMf/tD0YzEAqYEBSE9WB6DVq1dbNvlZ0nn/KUUwAFXC6/VyCExDVg2BrVixAg0NDejr6wMA9PX1weVyYfXq1aYfKxAI1NywhYo4BKYnK4fAVqxYASGEJe/7fBwCqxgDUCXsOHFwErT54vG4JZu/HThwINfl/c4772DBggVwuVw4ePCg6ceyo/eRSrNjGIKToM1n1STonTt3QgiB66+/Hr/73e9y/1566SVTjwNwErQJGIAqYdVQSj47AlCtsXL/o6effhpCCAghMGXKFDz33HOWHKcWe+5UZMdcEjsCEJfBm2PRokW593/+P5fLZepxgNocujQZA1AldO+CtGo/HNVZHfz6+vpw4MABy15fPsOIAch5Vm+EaDVuhKhv8OMweMUYgCphx92flfgoDD1PfrX8+ALVsJb05ff7te1BkcFV17pTBANQJXQ/+Xk8npqdR+L3+7VdRRUOhxEOh51uBv2VzhfSSCRiyaagOojFYvD5fE43Y0xqObiaiAGoUrqe/Gp1ArSk88mvloOrinTej6WWa0kOJWcyGaebMmqcAG0KBqBKxeNxLS+ksVgMXq/X6WY4RteTX2dnZ00HVxXpWkvyJki3dpvJ7XZrOY+mloOriRiAKqXjhFTDMODz+bQdAjKL2+3W7ncQiURqOriqyuv1atcTzFo6/TvQ7QZWDn/xJqhiDEBmCAaDWr2J5A6itf4Gksvhdfk9yDv2VCrldFNoEN0uSvLGrdZrSc7j1On34PP5tAvbimIAMoNObyLDMODxeLTs9rWCTnfuoVCI4/4K83q9aG1tdboZZQmFQjXf+yNFIhF4PB4tJhTrdtOmOAYgs+jSlRqLxeB2u7V4s9tB3rmrPoRp1c61ZB45P0v1vxFrqZBhGFrMBZI3r7oN2yuMAcgsshdI5eKU3d6cPFfI7/cjEAgoGwrlnC32/qgvGAwqX0uBQIC1NIhcyafyhPBoNMqbV3MxAJlJ9iaoOBSWzWbh8Xi4f8wwMpkM3G43otGo000ZVigU4olPE9lsFm63W9mhsNbWVs7/K8Lv98Pn8yn5PpNDX7ruOacoBiCzxWIx5ZaWyrs+v9+v5JtbBXJYQLVucHnXp1I90chkLanWG6ziuUklhmHA6/Va8qDkSsihVfbcm44ByArhcFip7lR516dKe1SlWg+eau2h8qn2t1OtPapSrTc4k8nA4/Fos1BDMwxAVjAMA36/3/EQZBgGWltbOeFxFCKRiBIXikQioWSPFJVP1lJ7e7uj7Whvb1eyR0pVssclGo062mOeTqfh8XjYc28dBiCrGIaBYDDo2MU0k8kgEAiw52cM4vF47gRoN8MwEI1GlQhhVDknawlArpY4fDI66XQabrfbsQntsscuHA4z/FiHAchq3/72tyGEQFtbm23HzL9z4GTHsUmlUnC73QiFQradgORcLbfbzR67KiJryc6LaX4tceLs2GQyGUd68mVove2222w7Zo1iALLS4cOH8cUvfhEzZsyAEAI+n8/SC1s2m829eXjnUDk5H8Dj8SCRSFh2HMMwkEgkcqGVPXbVJ5PJwOv15mrJqvdmfi15vV7WUoXye/Kj0ailN5QdHR3w+Xxwu9246qqr4PV6eQ63FgOQVU6dOoUZM2bA5/Ph2LFjyGazuTdSKBQyNQgZhoG2tjYIIeD1ejl0YiLDMHLDGD6fDx0dHaa+fkdHBzweT24jNp7wqpesJbfbbVktyQsoa8lcqVTKsgCbTqcRCoUghEAkEkE2m4VhGLjwwgtx3XXXmXYcGoIByCrxeBzjxo3DG2+8UfDxdDqdC0KBQACJRGJMd2mGYaCjowOtra25CyjH+a2TzWZzk1p9Ph/a2trQ1dU1ptfq6upCNBqFz+fLnfR4saodVtcSh72tkR9gPR4PWltb0dHRMab3biaTQSKRQCAQgBACwWBwyE3x9u3bUV9fj5/97Gcm/QQ0CAOQFV566SXU1dVhzZo1Rb8mnU4jEonA7XbnToTRaBSJRAKJRALd3d0F/9rb23Ofk28aOdSVTCZ5AbXJ9u3b4fF48MUvfhFCiNyJUP5turq6Cv5uHR0duc/JFXlCCFxyySWYOHEi9uzZ4/SPRA7ZuXMnzjvvPHzlK1+pqJa+8pWvYOLEidi1a5fTP1JNMAwDyWQydyObfzObSCTQ3t4+5PwtP5cfVuVzCEcaDXjooYdw9tlnY/v27fb9gLWDAchsH374Ic4///xR7bicyWQQi8UQDAYL3lSD/3m9XgSDQUQiEXR2djL0OGDlypUYP348PvvsM2SzWSSTSYTDYQSDwVyYHfzP7XYjGAwiHA4jlUohm83iwIEDqK+vx1NPPeX0j0QOSSaTGDduHA4dOjSmWkomk8hmszh06BDGjRvHoW8HGIaBVCqFSCSCYDAIr9db9Pwtz+/xeLzsXv+BgQHMmDEDF154Ic/35mMAMtOpU6fQ0tKSm/dTqVgshi9/+csmtIzMctlll+E73/nOiF9jGEZZc7yuvfZazJgxw6SWkW78fn9ZN0rl1JIMTqSO8847Dw888EDFr3P48GFMnjyZ84HMxwBkpnvuuWfYeT9jFY/HcfHFF5vyWlS5HTt2QAiBl156yZTX27RpE+rq6nDgwAFTXo/0IR9MbNYS9c7OTtTV1eHPf/6zKa9HlZs0aRJ+/vOfm/JaW7duRX19PR5++GFTXo8AMACZR877+fd//3fTXpMBSC133HEHvvSlL2FgYMCU1ztx4gQ8Hg/uu+8+U16P9BGLxTBp0iT09vaa8nq9vb2YNGkSdw5XiJkBCAAefPBB1NfXY+vWraa9Zo1jADLD/v37Rz3vpxwMQOro7e2Fx+PB0qVLTX3d2267DRdddJGpr0lqk2HF7EdTxGIxXHTRRaYFdKqM2QFIzgeaPHkyDh8+bNrr1jAGoEr19fVh2rRpps37yccApI7/+I//gBDC9CGGbdu2QQiBl19+2dTXJXXJZ02ZvUmhHFbjLuJqMDsAAWfmA82YMYNBt3IMQJX613/9V1Pn/eRjAFLHN7/5TcsmmV522WX47ne/a8lrk3rC4TD8fr8lr+33+/nkcEVYEYCAM/OBli1bZvpr1xgGoEq88MILEELgF7/4hSWvzwCkhkOHDqG+vt6yZcYPPfQQzj33XJw4ccKS1yd1yCXrVm1amkwmce655+Kzzz6z5PWpfFYFIAC4//77OR+ocgxAY7V//354PB7T5/3kYwBSw4oVK3J7/1iBewLVjvy9f6zAPYHUYWUA4nwgU+gVgI4cOYIlS5agqakJLS0tQ7aPf/755zFr1iw0NjbilltuwSeffFL2946GlfN+8jEAqeGyyy6zfFiBewLVhnL3/qkE9wRSg5UBCDB/PtCnn36KadOm4Te/+c2Qz+3evRsNDQ14//33h3xuwYIFWLRoUcXHd4BeAWjevHloampCKpXCjTfeCCEEtm3bBgDYtWsXhBC49dZb8cQTT6ChoQEzZ84s63tHq62tzbJ5P/kYgJy3fft2WyaWck+g6mf23j/FcE8gNVgdgIAz84Eq3f7g4MGDuPbaayGEGNITvXPnTjQ1NUEIgb179+Y+fvLkSSxZsgRCCESj0YqO7xB9AtCePXsghEB3d3fuY6FQCHPnzgUAzJ07F6FQKPe5l19+GUII7Nmzp+T3jkZXVxeEEGhvb6/gpykPA5Dzbr/9dlP3/imGewJVP7P3/imGewKpwY4ABACJRAJ1dXVj3qD19ddfh8vlQnNz85AAlEqlIITA1KlTCwLQZ599hilTpsDlcqGxsZEByGpbtmyBEAJ9fX25jz344IOYMmUKAOCKK67A8uXLc5/r6+uDEAKbN28u+b3lymazcLlclndhSwxAzpJ7/9h1IeGeQNVLhpIlS5bYcjzuCeQ8uwLQwMAAWlpacP755+PDDz8c9fd3d3dj1apV+Pzzz+FyufDLX/4y97nHHnsMmzdvRk9PD4QQeO+99wAAH3/8Mdra2nDgwAHMnj0b8+fPN+3nsZE+AWjt2rVwuVwFH3v88cdzH3O5XFi3bl3B510uF9asWVPye8vR29sLv9+PCy+80NJ5P/kYgJz1zDPP2DosxT2Bqpfdw1LcE8h5dgUg4MxDuFtaWnDq1Kkxv87gACQNDkD5GIBskEwm0dDQUPCx9evXQwgBABBC4Mknnyz4vMvlwurVq0t+bznuuOMOnH322di+ffsYf4LRYwBy1syZMwuGVe3APYGqkxMTk7knkLPsDEDAmccx/eQnPxnzazAAKWrTpk1DAsvKlSsxdepUAEBTUxNWrVqV+9zAwACEEHjuuedKfm8pct6PVXt3FMMA5By5909HR4etx+WeQNXHqaXp3BPIWXYHIABYunRpRfOBGIAUJYcH3n777dzH5syZgxtuuAHA6bv1m266Kfe5t956C0II9PT0lPzekch5P9ddd52JP015SgWggYEBJJNJTJs2Dc3NzVi+fHnBmH+5S/81XsZomUceecSRIMI9gaqPU0GEewKNrNh5r9iS75G2WRmOEwHo1KlTFc0HYgBS1MDAAJqbmxEKhdDT04PVq1dDCIEXX3wRwJnn66xduxY9PT2YPn06Wlpa0N/fX/J7izlx4kRu3o9hGHb8mAVKBaANGzZACIGHH34YS5cuhRACK1euzH2+1NL/KljGaJnLLrvMsd8J9wSqLk4ORXFPoKFGOu8VW/JdapuV4TgRgIDC+UD5C3/KwQCksNdffz1XnC6Xq+BZKP39/Vi8eDGEEBBCYPr06dizZ09Z31vMrbfeavu8n3ylApDL5cL999+f+/9ly5ahoaEB/f39JZf+V8kyRku8+uqrQ353duKeQNXD6cnI3BOo0EjnvWJLvoGRt1kpxqkABJyZD3TXXXeN6vsYgDRw4MCBosn2+PHj+Oijj8b0vfmeeeYZCCEcK2Bg5AB09OhRCCEKngXzhz/8AUIIfPjhhyWX/lfJMkZLLFiwwNHl6NwTqHo4vRydewIVGum8V2zJNzDyNivFOBmAAOCnP/0phBB44YUXHGuD4vQMQFZ79913MWHCBEfm/eQbKQC9+eabQ+Y17d69OzfvaTRL/xmAzpB7/zgdPrgnkP5UCR9OhzBVFTvvDReARtpmpRinA5CcD+TxeLB//37H2qEwBqDBTpw4gebmZsfm/eQbKQDt3LkTQgi88847uY/JYa833nhjVEv/GYDO+M1vfqPE8BP3BNKfKsNPTg/DqWo0AWikbVaKcToAAWfmA02bNm3U84FqAAPQYN/97ncdnfeTb6QA9MEHH0AIgR07duQ+9sc//hFCCBw5cmRUS/9VDEClVrhJGzduRHNz85i+dzjXXXedMhOQR7snUDmrVKr0oYZlKfawxzfffBPz589HY2MjvvWtb+FPf/pTwedHu/pHUmkC8lgmYleyGmqkB2uqYjQBaKRtVopRIQABZ+YDLV682OmmqIYBKN9TTz01ZCWVk0YKQH/5y18ghCjoln300UdzoWc0S/9VDEClVrgBZ/aGGtzTVc73Dkfu/aPKEvTR7AlUziqVKn6oYUnFHvZ4/PhxNDU1IRQKYePGjZg2bRpcLldut/exrP4B1FuCPtql+JWshhrpwZoqGU0AGmmblWJUCUAA8OMf/5jzgYZiAJL+9Kc/QQiBb37zm043JafUKrA777wTjY2N+N3vfoctW7agsbER9957L4DS2wbkUzEAjbTCDQCi0WhuxcbgAFTqe4tZsWIFzj33XHz++ecm/iRjt3///rIvIqVWqVT5Qw1HNNLDHuWw8KeffgrgdM+FEALr168HMLbVP4B6mxCOJpBVshpqpN+1akYTgEbaZqUYlQIQAHzta1+D2+1GNpt1uimqYAACzsz7aWxsdHzeT75SAejw4cO45pprckv/58yZU3DxLnfpv2oBqNQKNwC466678Nprr2HNmjUFAaic7y3mq1/9qlK/BwD45je/WdYwSqlVKlX+UMMRjfSwxyVLluCaa64p+Pqvf/3r+MEPfgBgbKt/ADUfQxEOh+H3+0t+XSWroUb6XatmNAGo1DYrw1EtAO3fvx8TJ07EP/zDPzjdFFUwAAFqzfvJV+6jMI4cOZK7gx1OuUv/VVFqhVu+wQFoNN+bz+m9f4p59tlnIYQoOZG23FUqVbqfR9kGX5Rnz55dMLQBADfeeCNmz56d+/rRrv5RddKx7MXIZDJlfX2lq6FUD0BjUWqblXyqBSDgzHygWCzmdFNUwAAk9/tZsWKF000ZolafBVZqhVu+wQFoNN+bb+HChUouO5fL8kstpS53lQoDUOFFedasWUOG/ebOnYvrr78ewNhW/6i67Fwuy1+yZElZX1/paqhqDECjoWIAArg/UJ7aDkCq7PdTTK0GoFIr3PINDkCj+V5JhoxEImHyT2KOcsJZuatUGIAKL8oLFizArFmzCr5m5syZ+OEPfwhg9Kt/VNn7p5jRhLNKV0MxAKkZgLg/UE7tBiCV9vspplYDUKkVbvkGB6DRfK/0zDPPKLH3TzHlDM+Vu0qFAajworxixQo0NDTkhoj7+voKejRGu/pHlb1/ihnN8Fylq6EYgNQMQAD3B/qr2g1A8+fPV3LeT75aDUDAyCvc8g0OQKP5XmnmzJkFK1tUVOrhrOWuUmEAKrwoHzhwAEIILFq0CO+88w4WLFgAl8uFgwcPAhj96h+V9v4pptwJ2pWuhmIAUjcAAafnA9XX1+POO+90uilOqc0AJOf9tLe3O92UEdVyACq1wk0aLgCV+73Amb1/Ojo6LPk5zPLII4+MuCdQuatUGICGXpSffvrp3O9typQpBcM5o1n9I5eaP/roo5b+DJUqd4l+pauhGIDUDkAAcN9999XyfKDaC0By3k84HHa6KSXVcgCSSq1wq/R7V6xYgfHjxyuzX0sx5W7SOJpVKnRGX1/fiEOg5fxek8kkxo0bh0OHDpndPFOZsUkj66w0HQLQwMAAZsyYUavzgWorAMl5Pz6fL7fTq8oYgKx32WWXKbdfSzEqPaaDhvL7/VrcWAF6DNXpTocABJzuMZ88eXItzgeqrQB0yy23YNy4cSMuh1YJA5C1tm/fruR+LcWo8qBWGkpOLu7s7HS6KWVRfbJ2NdAlAAHA1q1bUV9fn1v9WCNqJwDJeT8jbWCmGgYga91+++340pe+pNx+LcWcOHEC5557bsFjPkgNsVgMkyZNQm9vr9NNKYvqy/WrgU4BCACWL19ea/OBaiMA6TTvJx8DkHXK3WBQNbfddpuSGzbWMhkmdNtdV9UNG6uFbgFoYGAA1113XS3NB6r+ACTn/VxyySVazPvJxwBknXIfMaGabdu2QQiB3//+9043hf5qtI+YUIWqj+yoFroFIAAwDAMXXnhhrcwHqv4A9C//8i8YP348du/e7XRTRo0ByDrf+ta38E//9E9ON2NMLrroItxyyy1ON4P+qtyHjKpIxYe2VgsdAxBwem7k2WefjR/96EdON8Vq1R2A5LyfwQ/v0wUDkDXkkvLBzzTSxfLly0fcE4jsI5eUJ5NJp5syJuXuCUSjp2sAAoCVK1fWwnyg6g1Act7PnDlznG7KmDEAWWPlypVa7P1TzIEDB1BXV4df/epXTjel5umy908xZuwJRMPTOQABqIX5QNUZgPLn/Rw/ftzp5owZA5A1LrvsMnznO99xuhkVueaaa3D11Vc73Yyap9PeP8VwTyBr6B6AVOpV1AAAFVlJREFUamA+UHUGoO9973uYMGGClvN+8jEAmW/Hjh0QQuCll15yuikV+fWvf809gRym294/xXBPIGvoHoCAM/OB7rrrLqebYoXqC0By3s8zzzzjdFMqxgBkvjvuuEOrvX+KkXsCPfDAA043pWbptvdPMdwTyBrVEIAAoL29vVrnA1VXAJLzfqrlgY4MQOaSe/+M9GR4nXzve9/jnkAO0XXvn2K4J5D5qiUAAaeHSatwPlD1BCA576e5ublqVscwAJnrt7/9rZZ7/xSzdetWCCHwv//7v043pebouvdPMdwTyHzVFICOHTsGn89XbfOBqicA3XbbbZgwYQLeffddp5tiGgYgc33729/G9OnTnW6GqS666CJ873vfc7oZNUfnvX+K4Z5A5qqmAAQAb7zxBsaNG4e7777b6aaYpToCUDXN+8nHAGQeuffPhg0bnG6KqR544AHuCWQz3ff+KYZ7Apmr2gIQAKxZswZ1dXXaLyL5K+cCUCaTgWEYFb+OnPdz2223mdAqtSxZsgRf/vKXnW6G8sqppZ/97Gda7/1TjNwT6Omnnx7x6wzDqJrhGiuVU0u67/1TTLl7ArGWynPeeedV5SKFcDiM888/Hx9++GHFr+VwLVkbgAzDQEdHB1pbWxEKheDz+SCEGPLP4/EgFAohFAqhvb297F9Ib28vmpub4ff7tV6JkclkkEgkcr+D4X5HQggEAgGEQiFEo1F0dXWZEiB1IWspGo2OWEtCiGFr6bLLLsO8efMc/ims8f/+3//DN77xDQDl15LP52MtjbGWqmHvn2Ly9wQaSy11dHTUXC11dXWNqpYSiYTWAfLYsWO45JJL0NLSglOnTpX1PZlMBu3t7arVkvkByDAMtLe3IxAI5H6oYDCIeDyOeDyOZDKJdDqd+9fZ2Zn7XCQSgdvtzv0i2traRpyUt2DBArhcLmSzWTN/BFuk02lEo1F4PB4IIeD1ehGJRHK/i87OzoLfUzKZzH3O7/fnfretra1ob2+vypOOrKX8N8xYaqmxsRFCCKxatcrpH8kS99xzD8466yz83d/9HWupiOFqye/3j7mWHnroIad/JEvcd999EELgy1/+MoQQcLvdY6olGRpZSyNf46LRqJYTz3fv3o3x48fjxz/+cdGvkdc4GQoVrCXzApBhGEgkEvB4PLkfNJVKjanR6XQasVgMXq83d2IeHHK6uroghEBXV5cZzbdNOp3OvXHkm2YsdwPZbBapVArhcDjXi9be3m5Bi+1nRS01Nzfn3kw6Bubh5NfS3//934+5lgzDyNWS2+2Gx+NBIpGwoMX2M7OWMpkMYrEYLr/88lwt6Xwnny+/li6//HLEYjFTa6laglB+LYXD4YprSV7oQ6GQdkHoiSeeGHY+UCaTKbjGVVpLMjRaUEvmBKD29vZcUcTjcVOLvbOzMxeEotEostksstksXC4Xvv/975t2HKtls9lcUQSDQVOL3TAMxGKx3F1FR0eHaa9tt46ODstqKZ1OD6klHWWzWbS2tlpWS/F4vGpqyefzWVZL8uKley1Fo1HWUgmyloQQltRSMBjUspbmzJmTmw+UX0t+v9+SWnK73WbWUmUByDCM3FBXLBazNOWnUil4vV54PB589atfRSAQsOxYZkulUrmhCSu3zc9ms4hEIrleM53uuvJrKRKJ2FZLuj3GgLVUmmEYuZuNSCRi6QVF91ryeDzwer2WPgw1v5ZCoRBrqYj8WtLl4bTHjx/HlClTcOWVV9peS4FAoNJaGnsAymQyuR/Yrm5gwzByP/yKFStsOWal2tracgHRLul0Gm63G4FAQIu7iUwmA5/PZ2stAcjVki5Dh7KW7NyrJZPJaFdLgUAAbrfbkVrSZegwkUg4Wks6DB2ylsqzaNEix2rJ5/NV8rcZWwCSdw5+v9+RNC+7VaPRqO3HLpdhGLlhCifSfCaTgd/vh8fjUfpk09nZ6WgtJZNJ1lIJ2WxWi1pKp9PK1JKqvRyGYeSGKZyoJcMwcrWk8pyX/FpyIvjLnl5dasmJPbHya2mMva+jD0DyD+P0jqGpVAput1vJC5cczrH7zmG4dsixZRUvXKrUUmdnJ9xuN0KhkKPtGE5+LTl5wTAMIzfhXsULV34tOXnBkLWk6hC9KrUkezlUHDaUjzkJh8OO1lJ+T76KQqEQ3G63o3/D/FoaQ6AfXQCSz4tR5QGAqrVHam1tdTz85JMPslNpCEMOoTodfiTZpapaoI5Go0rVUiQSUa4niLVUHtZSaayl8lRJLZUfgLLZLDwej3IbgMk7P1UmjcnVWCrdJcuuQhMmjZnWHo/Hk9twTRWq1ZIc6mUtjdweOVShEtVqSQ7Pqdbj4vf74fP5lKkln8/n2BBqMbJHSpVHr6hW25IcDhvF3668ACS74VUrDEmGDqfTqKqFAZwOsG63G62trY62Q5dacjp0qFxLhmEoMWQoa8nr9SpZS6oEWNUuoPkMw4DX61VimEcOD6pYS6oE2HQ6ndsKQDX5tVTm37C8ACQ3IlJpCGWwcDgMn8/n2PFlD5kqXafDkUOGTp4IY7GYUl2nw5FDhk6dCGWvhuq1JPfXcYrcF0TlWpJd86yl4lhL5WEtlTbKWiodgLLZrLJ3ovlkO516E0UiEWXvRPPFYjHH3kRO/43KJXs4nKwlVe9E88XjcUdryePxsJZKkBd21lJx8sLOWhqZbrVURodN6QDU2toKr9drUtOs5dSbSJeQCDj7JpIhUQespdJUqCXVT8bAqE7IptLlhgM4U0tO9C7IXmldakkI4Ugt6RASgTNDYWXU0sgBSI73OT3uWC6nTsihUEibCzvgzMVdDr/pcGEHztSS3SsMdQqJgDMnZJ1CIjCqE7KpdKslOe/NiVpScX5UMU7Wkg4hESi7lkYOQOFwWLmVOqXIE7Jdfyh5YXd6ouNoOHFxD4fDyq3UKUVOPLS7lnS5sEt2n5B1u7AD9l/cdQuJEmupNNZSecqopeIByDAMLX9ou9sdj8e1ewMBp7t97Zw0rttdFmB/LSWTSbjdbluOZSa7a8nj8WhXSwBYS2VIJpPweDy2HU+XYZ3B3G63be8BGbh0U0YtFQ9Acumkyiu/ivH7/bbdRQQCAaVnxRcjhzft+PvqXEvBYNC2va90rSXZc2XHCho769Zs4XDYtlqy81hmsrOW7DyW2ewcndG1lmTP1QijM8UDUCQS0W7IQrLrLkL+gnWZIzWYXXcRsViMtVSCrj2ukl1z72KxmJY9roB9d9K615LX67VleL4aasmO4Xkde++lErVUPABZ1TV45MgRLFmyBE1NTWhpaUFXV5fpx7BrXo4dRbhgwQIsWrTIkteORCK23EX4fD5LTmh21JJdIdfKWnr++ecxa9YsNDY24pZbbsEnn3xi+jEikYgtm9mxlkqTPa46n5fsqCWre1x3796NhoYGvP/++6a/tgy5dtWSlT2uVtZSieH54QOQ/OVaESDmzZuHpqYmpFIp3HjjjRBCYNu2baYfx47ln7FYzLIAcfLkSSxZssTSJ5XLCeNW072W7OjdiMfjltTSrl27IITArbfeiieeeAINDQ2YOXNUzz8ui129G1ad9O2qJb/fb0stWdXjasd5SV50rWZlgNi5cyeampoghMDevXstOYZdtWRVL5kdtSSHzIsYPgDJbzJ7bHTPnj0QQqC7uzv3sVAohLlz55p6HOD03A2riyMYDFpy0frss88wZcoUuFwuNDY2OlUcph7D7ABUbbVk1Zj+3LlzCx5Z8fLLL0MIgT179ph6HDtqyaqeXbtryerhHat6du0+L1nZg2XlTb68GZg6daqlASgYDFo+Z9CqGzO7a6lIlhk5AJlty5YtEEKgr68v97EHH3wQU6ZMMf1YdhSHVRfGjz/+GG1tbThw4ABmz56N+fPnm34MwJ4JpVadzOyuJasnAVpVr1dccQWWL1+e+/++vj4IIbB582ZTj2NV0B3uGGbXq921ZPWws1X1avd5yY5asuIYjz32GDZv3oyenh4IIfDee++ZfgzAnonQVtWrXbVUYiL08AHIqu7stWvXwuVyFXzs8ccfH/IxM9hRHD6fz/KeAQeLwxRWdWfbWUt2zJWyKky7XC6sW7duyMfWrFlj6nGsvKOWrLoxs7OWrLqjzmdHj6WV5yXAumFzyY4eS6sDkF21ZHWPpYO1NHwAsmrcL5lMoqGhoeBj69evt6QQ7SgOO2bH636isWqeUTXWkhUXLSEEnnzyyYKPuVwurF692pJjWTkps1pqyeo9k+zY28aO85KVq9jsmLNmRwCyeoVqIBCoiloq8jMUD0BWvEk3bdo0pOhWrlyJqVOnmn4sBqDy6BqAqrGWrDjRNDU1YdWqVbn/HxgYgBACzz33nOnH0jUA2V1LVi+9tmPSvh3nJSvPrdUSgKze7NLr9VZFLY0qAFlVHNu2bYMQAm+//XbuY3PmzMENN9xg+rHsGALTvTh0HgKzs5Z0HgKbOXMmbrrpptz/v/XWWxBCoKenx9Tj6DwEZmctcQisPLrWUr5qGQKr4lqydxL0wMAAmpubEQqF0NPTg9WrV0MIgRdffNH0Y+k8CTofJ0EPz+5a0nUStAyga9euRU9PD6ZPn46Wlhb09/ebehydJ0HbXUu6ToLOZ+V5yY593OyoV06CLo9yk6CtWgYPAK+//npufwSXy4Vly5aZfgxA72Xw+ewIQFay8kRTTbVk1cmsv78fixcvhhACQghMnz7d9CXwgN7L4AF7a0nXZfD57Dgv6boMXrI6AOm8DD6fHbU0qmXwdhTHgQMHCpadmk33jRDtIJ92bjXda8mOSaVWn2iOHz+Ojz76yLLXt3MjRJ1ryY5JpfF43JadlK1SDRsh2sGuWrLzQcdmG9NGiIB9z/axgt2PwtCVXc97s+vZPlaohkdh2IG1VBprqTx2PTvQzodmm82u573p/CBroOTz3kZ+GKqudxHJZNLy2fGA/g9D9Xg8tjzkjrVUmu4PsLSjlwwo+WwfpdkVTHSvJaue9zYYa6k8VVxLxQOQHQ/Us4rVD7nLp+tdhJXzvAbT+S4iHA5bPqFU0rWWZI8ra2lkdtaSHROhrWBnLdl5LLPZMQE6/1g61lIZHRTFA5CudxF2t1vXu4gSXYOms2PPJLPZXUvJZNLyjc2sYHctud1u7WoJsPc9oGst2dXjKulaS3b13gP2zRU1Wxm1VDwAAaeTX/6DFHUgN0uzq+fKrvlGZjIMw7ZuZknHWpLdzHb1Nsha0m1I1efz2dpzFQ6HtbvpsLuW5N2vbjewdtdSJBJhLZWgcy2V6LkaOQDJYRJdTsiGYdg2FyFfMBjUao6L3EHUzmEEWUu6vIlkLdk9JKXbxV3eHdpZSzqekO2+sAP6XdztvrADrKVyyVrSZUpMmbU0cgAC9Dohywu73X8keeeuw5vIqZAI6HVCdqqWdDohy1pyYlWWbrXkxLwlWUs6DPE4dcMBnK4lj8ejxcXdiRsO4Ewt6bIyvMyQWDoA6XJCzmazjl3YAX1OyE5d2AF9TshOhkRAn7stFWpJ9ROy07UUi8W0uLg7WUuGYWix7YuTNxzAmYev6lBLZYbE0gEIOJOQVV550draCq/X69gfR56QVd6jRPZUOflG16GWotGoYydj4HQtud1uRKNRR45fjkwm4+iFHThzQlZ5FY/TtSQv7qylkbGWSqvCWiovABmGAb/fj0AgoGT6i8ViSkxEluOOKvaWybsHp3euVr2W5N0Da6k4WUt2bFZXqh0q15IcrnB6DqXqteTz+eD3+x3/G/r9fmV7XlX5G8ptKFTsxTcMA4FAYDS1VF4AAk4nKxXTnyqFIckwptKdxBgKw1Kyh6O1tdXpphRQtZacDmODBQIBR3tb88m7UtVWGKp2oVAl2A8WCAQc7dXIZxgGvF6vcgta5AISVYboVAn2g4VCodHWUvkBCFDvDyGHdFTbPC4cDis1zCO7TlUKZfJvp8qQoew6VbWWVPnbqVpLKt2cqVpLcvhZlb8da6k01lJ5xlhLowtAwJm7ZKcLpLOzU4khneHIrnmnC8QwDLS2tip55wewlsqhUi1Fo1El7/wAdWopnU4rMTw4HBVrSZXe1nz5teRkz5QMP6r03A8ma8npa0sFtTT6AAScKZBQKOTIH6a9vV3Jnp98hmEgGAzC4/E48ibPZrO57mVVUvpwUqlUbgjD6VpS8SQDnKklpy4YcgjV7XY7frIbSWdnJ9xut2NzguR5UfVaCofDStSSikFaUqWWwuGw0rUUiUR0rqWxBSDgTFdhIBCw9QIr054qY+ulyAJJJBK2HTP/zkGVYbiRyFry+XyO1JIqQ7qlyFpqa2uz7Zj5taRykJYymQy8Xi9rqQQ5v8zOHjNZS16vV6tasrvHrK2tTanpAaXI+WV215LP56u0lsYegIDTvQx+vz93gbcyqXZ0dMDn8yl/5zAcmeYDgYCld9DZbDZ3Ilb5zmE4snteXuDtqiUVu+BHImvJ5/PZVkvBYJC1VES11JKV59T8IS9Vh3OKya8lq4fEOjs74fP5lB0aHInsyff5fOjo6LDsOIZh5AKiCbVUWQCS5CZWHo/H9J6OdDqNQCCQ61rWoUdjOJlMJjeMEQqFTL14GYaBRCIBIQS8Xq92b558g2vJzBNOOp1GKBTSvpay2azltSTv1HWuJfkwRKtrKRwOa11LckjMylrSMSDmkxd41lJx2Ww210ttdS2ZNAJkTgACTjdQdoV5PB5Eo1F0dXWNqVAymQza2tpywScYDGrRZVqOdDqdu3gFAgG0t7eP6WczDAMdHR2IRqO5ovj/7drRkYIwEMZxO0gpFnAPsQPoIHSAHbAdQAdJCXQQO6CElJAS9p7CSJQjjnBK+H4zPPkk8w+zrO5l/b4ktBQeOO+2RESTlr75fyyv2LqlPb2pz0FLaeKWiAgtRZ61ZIxBS5E1W+r7fsuW1huAAuccN00zrg1PpxOXZclExETEfd/z7XabXOGz8EXDJkMplU0UMa01K6VYCDGuoa/XKxMRd133cI+MMeN9CocmHJy2bbN4wMTebSmsk4/cEhH92VJ48wwr5Vxb8t5z27aTli6Xy3gfjDFJLQkhsm7JWvvQUlVVaOkOWkqzZksbDdHrD0D3nHOsteaiKMaJcO46n88speSmabLZ9qSy1nJd1yylnByq+BJCsJSSlVKstc7y4TInbikcKrQ0NQwDWlrgvX+5pbqu0dJCS0VRoCW09NSXtrTtADTHe8/W2t3+1vlfhmHI9u1gLWgpDVpKg5aWOefQUgK0tOzDLX1mAAIAAAD4IAxAAAAAcDgYgAAAAOBwMAABAADA4fz8Ah4X/3ALLsC7AAAAAElFTkSuQmCC)\n",
    "\n",
    "which can be stored in a list starting at the first two nodes under the root at indices 0 and 1, the 2 left hand-side nodes at the next level (representing lines that start with `0`) in indices 2 and 3, then 4 and 5 contain the counts for everything starting with `1`, and so on:\n",
    "\n",
    "```python\n",
    "btree = [1, 3, 1, 0, 1, 2, 0, 1, 0, 0, 0, 1, 1, 1]\n",
    "#        0  1  0  0  1  1  0  0  0  0  1  1  1  1\n",
    "#        .  .  0  1  0  1  0  0  1  1  0  0  1  1\n",
    "#        .  .  .  .  .  .  0  1  0  1  0  1  0  1\n",
    "```\n",
    "\n",
    "I've dropped the `- 2` subtractions to simplify the code, and just live with two extra unused positions in my btree list.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from operator import ge, lt\n",
    "\n",
    "\n",
    "def life_support_rating_btree(report: list[str]) -> int:\n",
    "    # build a btree in a list (first two elements are left untouched)\n",
    "    # with each node representing the number of lines that have the same\n",
    "    # bit prefix. e.g. `0` and `1` give the btree [0, 0, 0, 1], while\n",
    "    # `01`, `10` and `11` produces `[0, 0, 1, 2, 0, 1, 1, 1]`.\n",
    "    depth = len(report[0])\n",
    "    btree = [0] * (2 << depth)\n",
    "    for line in report:\n",
    "        v, offset = 0, 1\n",
    "        for c in line:\n",
    "            offset <<= 1\n",
    "            v = (v << 1) | (c == \"1\")\n",
    "            btree[offset + v] += 1\n",
    "\n",
    "    def rating(op=ge):\n",
    "        # Walk the btree to reduce the line count down to 1 by choosing either\n",
    "        # the left (0) or right (1) child node for the given comparison operator\n",
    "        # comparing between the line counts.\n",
    "        v, offset = 0, 1\n",
    "        for _ in range(depth):\n",
    "            offset <<= 1\n",
    "            v <<= 1\n",
    "            idx = offset + v\n",
    "            bit = op(btree[idx + 1], btree[idx])  # #(1) >= #(0) or #(1) < #(0)\n",
    "            if op is lt and btree[idx + bit] == 1:\n",
    "                # We've reduced the tree to a single line, reconstruct the\n",
    "                # remainder by always using >= (instead of < for the co2\n",
    "                # scrubber rating)\n",
    "                op = ge\n",
    "            v += bit\n",
    "\n",
    "        return v\n",
    "\n",
    "    oxygen_generator_rating = rating()\n",
    "    co2_scrubber_rating = rating(lt)\n",
    "    return oxygen_generator_rating * co2_scrubber_rating\n",
    "\n",
    "\n",
    "assert life_support_rating_btree(test_report) == 230"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 2: 4636702\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 2:\", life_support_rating(diagnostic_report))"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "8bb5fd587ebf4d90f905285c44a569046664a8863ee065ff2dd968491b671e06"
  },
  "kernelspec": {
   "display_name": "Python 3.10.0 64-bit ('adventofcode-mOkh6lsX': pipenv)",
   "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.12.0"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}