RandomForest/Intro_DecisionTree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  Desicion Trees from Scratch\n",
    "\n",
    "The decision tree algorithm is a supervised learning algorithm -- we first construct the tree with historical data, and then use it to predict an outcome. One of the major advantages of decision trees is that they can pick up nonlinear interactions between variables in the data that linear regression can't.\n",
    "\n",
    "\n",
    "The data is income data from the 1994 census, and contains information on an individual's marital status, age, type of work, and more. The target column, or what we want to predict, is whether individuals make less than or equal to 50k a year, or more than 50k a year.\n",
    "\n",
    "Download the data from the [University of California, Irvine's website](http://archive.ics.uci.edu/ml/datasets/Adult)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   age          workclass  fnlwgt   education  education_num  \\\n",
      "0   39          State-gov   77516   Bachelors             13   \n",
      "1   50   Self-emp-not-inc   83311   Bachelors             13   \n",
      "\n",
      "        marital_status        occupation    relationship    race    sex  \\\n",
      "0        Never-married      Adm-clerical   Not-in-family   White   Male   \n",
      "1   Married-civ-spouse   Exec-managerial         Husband   White   Male   \n",
      "\n",
      "   capital_gain  capital_loss  hours_per_week  native_country high_income  \n",
      "0          2174             0              40   United-States       <=50K  \n",
      "1             0             0              13   United-States       <=50K  \n"
     ]
    }
   ],
   "source": [
    "## Loading dataset ##\n",
    "\n",
    "import pandas as pd\n",
    "\n",
    "# Set index_col to False to avoid pandas thinking that the first column is row indexes (it's age).\n",
    "income = pd.read_csv(\"income.csv\", index_col=False)\n",
    "print(income.head(2))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before we get started with decision trees, we need to convert the categorical variables in our data set to numeric variables. This involves assigning a number to each category label, then converting all of the labels in a column to the corresponding numbers.\n",
    "\n",
    "One strategy is to convert the columns to a categorical type. Under this approach, pandas will display the labels as strings, but internally store them as numbers so we can do computations with them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0    7\n",
      "1    6\n",
      "2    4\n",
      "3    4\n",
      "4    4\n",
      "Name: workclass, dtype: int8\n",
      "   age  workclass  fnlwgt  education  education_num  marital_status  \\\n",
      "0   39          7   77516          9             13               4   \n",
      "1   50          6   83311          9             13               2   \n",
      "\n",
      "   occupation  relationship  race  sex  capital_gain  capital_loss  \\\n",
      "0           1             1     4    1          2174             0   \n",
      "1           4             0     4    1             0             0   \n",
      "\n",
      "   hours_per_week  native_country  high_income  \n",
      "0              40              39            0  \n",
      "1              13              39            0  \n"
     ]
    }
   ],
   "source": [
    "## Converting categorical variables ##\n",
    "\n",
    "# Convert a single column from text categories into numbers.\n",
    "col = pd.Categorical(income[\"workclass\"])\n",
    "income[\"workclass\"] = col.codes\n",
    "print(income[\"workclass\"].head(5))\n",
    "\n",
    "cols = ['education', 'marital_status', 'occupation', 'relationship', 'race', 'sex', 'native_country', 'high_income']\n",
    "for c in cols:\n",
    "    income[c] = pd.Categorical(income[c]).codes\n",
    "\n",
    "print(income.head(2))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating Splits\n",
    "\n",
    "We can split the data set into two portions based on whether the individual works in the private sector or not based on the value of the 'workclass' column.\n",
    "\n",
    "- private_incomes should contain all rows where workclass is 4.\n",
    "- public_incomes should contain all rows where workclass is not 4.\n",
    "\n",
    "\n",
    "When we performed the split, 9865 rows went to the left, where workclass does not equal 4, and 22696 rows went to the right, where workclass equals 4.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(22696, 15) (9865, 15)\n"
     ]
    }
   ],
   "source": [
    "private_incomes = income[income['workclass'] == 4]\n",
    "public_incomes = income[income['workclass'] != 4]\n",
    "print(private_incomes.shape, public_incomes.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Information Entropy\n",
    "\n",
    "Entropy refers to disorder. The more \"mixed together\" 1s and 0s are, the higher the entropy. A data set consisting entirely of 1s in the high_income column would have low entropy.\n",
    "\n",
    "The formula for entropy looks like this:\n",
    "\n",
    "$$-\\sum_{i=1}^{c} {\\mathrm{P}(x_i) \\log_b \\mathrm{P}(x_i)}$$\n",
    "\n",
    "We iterate through each unique value in a single column (in this case, high_income), and assign it to i. We then compute the probability of that value occurring in the data (P(xi)). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.796383955202\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "length = income.shape[0]\n",
    "prob_high = sum(income['high_income'] == 1) / length\n",
    "prob_low = sum(income['high_income'] == 0) / length\n",
    "income_entropy = -(prob_high * math.log(prob_high, 2) + prob_low * math.log(prob_low, 2))\n",
    "print(income_entropy)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# General Function to get entropy\n",
    "import numpy as np\n",
    "def calc_entropy(column):\n",
    "    \"\"\"\n",
    "    Calculate entropy given a pandas Series, list, or numpy array.\n",
    "    \"\"\"\n",
    "    # Compute the counts of each unique value in the column.\n",
    "    counts = np.bincount(column)\n",
    "    # Divide by the total column length to get a probability.\n",
    "    probabilities = counts / len(column)\n",
    "    \n",
    "    # Initialize the entropy to 0.\n",
    "    entropy = 0\n",
    "    # Loop through the probabilities, and add each one to the total entropy.\n",
    "    for prob in probabilities:\n",
    "        if prob > 0:\n",
    "            entropy += prob * math.log(prob, 2)\n",
    "    \n",
    "    return -entropy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.79638395520221317"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calc_entropy(income['high_income'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Information Gain\n",
    "\n",
    "We'll need a way to go from computing entropy to figuring out which variable to split on. We can do this using information gain, which tells us which split will reduce entropy the most.\n",
    "\n",
    "Here's the formula for information gain:\n",
    "\n",
    "$$IG(T,A) = Entropy(T)-\\sum_{v\\in A}\\frac{|T_{v}|}{|T|} \\cdot Entropy(T_{v})$$\n",
    "\n",
    "We're computing information gain (IG) for a given target variable (T), as well as a given variable we want to split on (A).\n",
    "\n",
    "To compute it, we first calculate the entropy for T. Then, for each unique value v in the variable A, we compute the number of rows in which A takes on the value v, and divide it by the total number of rows. Next, we multiply the results by the entropy of the rows where A is v. We add all of these subset entropies together, then subtract from the overall entropy to get information gain.\n",
    "\n",
    "We first compute the information gain for splitting on the age column of income.\n",
    "\n",
    "- First, compute the median of age.\n",
    "- Then, assign anything less than or equal to the median to the left branch, and anything greater than the median to the right branch.\n",
    "- Compute the information gain and assign it to age_information_gain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0470286613047\n"
     ]
    }
   ],
   "source": [
    "# Get the median\n",
    "age_median = income['age'].median()\n",
    "\n",
    "# left and right split\n",
    "left_split = income[income['age'] <= age_median]['high_income']\n",
    "right_split = income[income['age'] > age_median]['high_income']\n",
    "\n",
    "# obtain the entropy\n",
    "income_entropy = calc_entropy(income['high_income'])\n",
    "\n",
    "# Information gain\n",
    "age_information_gain = income_entropy - (left_split.shape[0] / income.shape[0] * calc_entropy(left_split) + right_split.shape[0] / income.shape[0] * calc_entropy(right_split))\n",
    "print(age_information_gain)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0470286613047\n"
     ]
    }
   ],
   "source": [
    "# General function to get information gain\n",
    "def calc_information_gain(data, split_name, target_name):\n",
    "    \"\"\"\n",
    "    Calculate information gain given a dataset, column to split on, and target.\n",
    "    \"\"\"\n",
    "    # Calculate original entropy.\n",
    "    original_entropy = calc_entropy(data[target_name])\n",
    "    \n",
    "    # Find the median of the column we're splitting.\n",
    "    column = data[split_name]\n",
    "    median = column.median()\n",
    "    \n",
    "    # Make two subsets of the data based on the median.\n",
    "    left_split = data[column <= median]\n",
    "    right_split = data[column > median]\n",
    "    \n",
    "    # Loop through the splits, and calculate the subset entropy.\n",
    "    to_subtract = 0\n",
    "    for subset in [left_split, right_split]:\n",
    "        prob = (subset.shape[0] / data.shape[0]) \n",
    "        to_subtract += prob * calc_entropy(subset[target_name])\n",
    "    \n",
    "    # Return information gain.\n",
    "    return original_entropy - to_subtract\n",
    "\n",
    "print(calc_information_gain(income, \"age\", \"high_income\"))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Finding The Best Split\n",
    "\n",
    "Now that we know how to compute information gain, we can determine the best variable to split a node on. When we start our tree, we want to make an initial split. We'll find the variable to split on by calculating which split would have the highest information gain.\n",
    "\n",
    "Now we need a function that returns the name of the column we should use to split a data set. The function should take the name of the data set, the target column, and a list of columns we might want to split on as input.\n",
    "\n",
    "- Write a function named find_best_column() that returns the name of a column to split the data on. \n",
    "- Use find_best_column() to find the best column on which to split income.\n",
    "- The target is the high_income column, and the potential columns to split with are in the list columns below.\n",
    "- Assign the result to income_split."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAABcEAAAE2CAYAAACp9VrLAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzs3Xt4VfWdL/53YgwaEAIGRhGpIuViEfSM83ijomOQXsAb\nFq03kPZpq9DxdNozU3qOCvUMaDttT0U5ox0qTIWK14HyaLl4qpYyWDtHhSOiIloaRQQhgDI0Qvj9\n4UN+g4BuQkJg+3r9o3ut79r7s5LPXit558t3l2zfvn17AAAAAACgCJW2dAEAAAAAANBchOAAAAAA\nABQtITgAAAAAAEVLCA4AAAAAQNESggMAAAAAULSE4AAAAAAAFC0hOAAAAAAARUsIDgAAAABA0RKC\nAwAAAABQtITgAAAAAAAUrbKWLuBA8+abb7Z0CTSBqqqqrF27tqXLoIXpA/QAiT5AD/ABfYAeQA+Q\n6AP0QDHp3LlzwWPNBAcAAAAAoGgJwQEAAAAAKFpCcAAAAAAAipYQHAAAAACAoiUEBwAAAACgaAnB\nAQAAAAAoWkJwAAAAAACKlhAcAAAAAICiJQQHAAAAAKBoCcEBAAAAAChaQnAAAAAAAIpWWUsXAAAc\nWOpnTW/pEprUuxUVqd+8uaXLaBKlF1zR0iUAAAAcdMwEBwAAAACgaAnBAQAAAAAoWkJwAAAAAACK\nlhAcAAAAAICiJQQHAAAAAKBoCcEBAAAAAChaQnAAAAAAAIqWEBwAAAAAgKIlBAcAAAAAoGgJwQEA\nAAAAKFpCcAAAAAAAipYQHAAAAACAoiUEBwAAAACgaAnBAQAAAAAoWkJwAAAAAACKlhAcAAAAAICi\nJQQHAAAAAKBoCcEBAAAAAChaQnAAAAAAAIqWEBwAAAAAgKIlBAcAAAAAoGgJwQEAAAAAKFplLV3A\nnDlzMmvWrNTW1qZLly4ZMWJEevfuvduxdXV1+dnPfpbXXnstb7zxRnr27JmxY8fuMm7p0qWZOnVq\nampq0r59+1xwwQU5//zzm/lMAAAAAAA40LToTPCFCxdmypQpufjii3PbbbelZ8+eGT9+fNauXbvb\n8fX19Tn00EPzuc99Lqeccspux7z99tuZMGFCevbsmdtuuy0XXXRR7rnnnixatKg5TwUAAAAAgANQ\ni4bgs2fPzoABA1JdXZ0uXbpk5MiRad++febOnbvb8Ycddli+9rWvpbq6OkceeeRux8ydOzft27fP\nyJEj06VLl1RXV2fAgAH51a9+1ZynAgAAAADAAajFlkPZunVrVqxYkSFDhuy0vW/fvnnppZca/byv\nvPJK+vbtu9O2fv365cknn8zWrVtTVrbzKc+fPz/z589Pktx6662pqqpq9Gtz4CgrK/O9RB+gBxrp\n3YqKli6hSZWWlqaiSM6pjX5uFNcCEn2AHkAP8AF9gB74ZGqxEHzjxo2pr69Pu3btdtpeWVmZJUuW\nNPp5a2trc9JJJ+20rV27dtm2bVs2bdqU9u3b77Svuro61dXVDY/3tBQLB5eqqirfS/QBeqCR6jdv\nbukSmlRFRUU2F8k5bdHPjeJaQKIP0APoAT6gD9ADxaNz584Fj23R5VAAAAAAAKA5tVgI3rZt25SW\nlmbDhg07ba+trU1lZWWjn7eysjK1tbU7bduwYUMOOeSQHHHEEY1+XgAAAAAADj4tFoKXlZWlW7du\nWbx48U7blyxZkp49ezb6eT/96U/vspzK4sWL061bt13WAwcAAAAAoLi16HIogwcPzhNPPJHHH388\nNTU1ueeee7Ju3boMHDgwSTJ9+vR8//vf3+mYmpqavP7669m0aVO2bNmS119/Pa+//nrD/vPPPz/r\n1q3LlClTUlNTk8cffzxPPPHELh/ACQAAAABA8WvRqdFnnnlmNm3alIcffjjr16/PsccemzFjxqRj\nx45JkvXr12f16tU7HTNhwoSsWbOm4fHf/d3fJUnuv//+JEmnTp0yZsyYTJ06NXPnzk379u1z7bXX\n5vTTT99PZwUAAAAAwIGixdcHGTRoUAYNGrTbfaNGjdpl25133vmxz3niiSfmtttu2+faAAAAAAA4\nuLXocigAAAAAANCchOAAAAAAABQtITgAAAAAAEVLCA4AAAAAQNESggMAAAAAULSE4AAAAAAAFC0h\nOAAAAAAARUsIDgAAAABA0RKCAwAAAABQtITgAAAAAAAULSE4AAAAAABFSwgOAAAAAEDREoIDAAAA\nAFC0hOAAAAAAABQtITgAAAAAAEVLCA4AAAAAQNESggMAAAAAULT2OQTfvn17/vznPzdFLQAAAAAA\n0KTKCh34+9//PsuXL88VV1zRsG3WrFl54IEHUldXl7/8y7/MDTfckFatWjVLoQAAAAAAsLcKngk+\nc+bM1NbWNjxesWJFpk2blu7du6e6ujrPPvtsZs6c2SxFAgAAAABAYxQ8E3zVqlU566yzGh4vWLAg\nRxxxRL73ve/l0EMPzSGHHJKFCxdm2LBhzVIoAAAAAADsrYJngtfV1eWwww5rePz888/n5JNPzqGH\nHpokOe644/LOO+80fYUAAAAAANBIBYfgRx55ZJYvX57kg1nhNTU16du3b8P+TZs2pby8vOkrBAAA\nAACARip4OZSzzz47999/f9avX5+ampq0adMmp556asP+V199NUcffXSzFAkAAAAAAI1RcAh+8cUX\n5/3338+zzz6bqqqqDBs2LBUVFUmSd999Ny+++GK++MUvNluhAAAAAACwtwoOwUtLS3P55Zfn8ssv\n32VfmzZt8rOf/axJCwMAAAAAgH1V8JrgAAAAAABwsCl4JniS1NTU5Iknnsjq1avz3nvvZfv27Tvt\nLykpyU033dSkBQIAAAAAQGMVHII/9dRTmTRpUg455JB07tw5bdq02WXMh0NxAAAAAABoSQWH4A88\n8ECOP/74jBkzJm3btm3OmgAAAAAAoEkUvCb4unXrcu655wrAAQAAAAA4aBQcgn/qU5/KunXrmrMW\nAAAAAABoUgWH4Ndcc01+85vfZNmyZc1ZDwAAAAAANJmC1wR/5JFHcvjhh+fmm29O586dU1VVldLS\nXTP0MWPGNGmBAAAAAADQWAWH4DU1NUmSqqqq1NXV5c0339xlTElJSdNVBgAAAAAA+6jgEPzOO+9s\nlgLmzJmTWbNmpba2Nl26dMmIESPSu3fvPY5fuXJlJk+enOXLl6dNmzYZOHBghg4dulMAv2DBgsyc\nOTOrVq3K4YcfnpNOOinXXHNNKisrm+UcAAAAAAA4MBW8JnhzWLhwYaZMmZKLL744t912W3r27Jnx\n48dn7dq1ux2/efPm3HLLLWnXrl0mTJiQa6+9NrNmzcrs2bMbxixbtiwTJ07MgAED8uMf/zj/7b/9\nt7zxxhu5/fbb99dpAQAAAABwgGjREHz27NkZMGBAqqur06VLl4wcOTLt27fP3Llzdzt+wYIFqaur\ny+jRo9O1a9ecfvrpufDCCzN79uxs3749SfLyyy/nyCOPzODBg9OpU6f06NEjn/vc5/LKK6/sz1MD\nAAAAAOAAsMflUC677LKUlJTk3nvvTVlZWS677LKPfbKSkpLcd999Bb3w1q1bs2LFigwZMmSn7X37\n9s1LL72022Nefvnl9OrVK+Xl5Q3b+vXrlxkzZmTNmjXp1KlTevXqlV/+8pf5wx/+kL/8y7/Mpk2b\nsnDhwpxyyikF1QUAAAAAQPHYYwi+Y53t0tLSnR43lY0bN6a+vj7t2rXbaXtlZWWWLFmy22Nqa2vT\noUOHXcbv2Ldj5vd//a//NRMnTkxdXV22bduWvn37ZvTo0bt9zvnz52f+/PlJkltvvTVVVVX7emoc\nAMrKynwv0QfogUZ6t6KipUtoUqWlpakoknNqo58bxbWARB+gB9ADfEAfoAc+mfYYgg8bNuwjHx+o\nampq8vOf/zxDhw5Nv379sn79+tx77725++67dxuEV1dXp7q6uuHxntYj5+BSVVXle4k+QA80Uv3m\nzS1dQpOqqKjI5iI5py36uVFcC0j0AXoAPcAH9AF6oHh07ty54LEttiZ427ZtU1pamg0bNuy0vba2\ntmF294dVVlbudvyOfUnyyCOPpHv37rngggvyqU99KieffHK++tWv5qmnnso777zTDGcCAAAAAMCB\nao8zwfdk3bp1WbFiRTZv3tzwYZT/2YABAwp74bKydOvWLYsXL84ZZ5zRsH3JkiU57bTTdntMjx49\nMm3atNTV1TWsC7548eK0b98+HTt2TJL8+c9/bljCZYcdj3dXLwAAAAAAxavgEPz999/PpEmT8m//\n9m8fGSYXGoInyeDBgzNx4sR07949PXv2zLx587Ju3boMHDgwSTJ9+vQsX748N910U5Kkf//+eeCB\nBzJp0qRccsklWbVqVWbOnJlLL720Yb3yU089NXfddVfmzp3bsBzK1KlTc/zxx1vvBwAAAADgE6bg\nEHzGjBlZtGhRLrvssvTs2TPjxo3LqFGjUllZmdmzZ2fDhg17/PDJPTnzzDOzadOmPPzww1m/fn2O\nPfbYjBkzpmFW9/r167N69eqG8RUVFbnxxhszefLkjBkzJq1bt87gwYMzePDghjHnnHNO/uM//iO/\n/vWv8y//8i9p3bp1PvOZz+TKK6/cq9oAAAAAADj4FRyC/9u//VvOPvvsXHzxxdm0aVOSpEOHDunT\np09OOumkjB07NvPmzcvIkSP3qoBBgwZl0KBBu903atSoXbZ17do148aN+8jn/PznP5/Pf/7ze1UH\nAAAAAADFp+APxqytrc2nP/3pJMkhhxySJKmrq0uSlJSU5LTTTsuiRYuaoUQAAAAAAGicgkPwtm3b\nZvPmzUmSww8/POXl5Xnrrbca9m/bti1btmxp+goBAAAAAKCRCl4O5bjjjsvy5cuTfDDz+8QTT8yj\njz6abt26pb6+Pr/+9a9z/PHHN1uhAAAAAACwtwqeCX7eeeelvr6+YQmUq666Kv/xH/+Rm2++OePG\njcuWLVty9dVXN1uhAAAAAACwtwqeCX7qqafm1FNPbXh87LHHZuLEiXnhhRdSWlqanj17pk2bNs1S\nJAAAAAAANEbBIfjuVFRU5K/+6q+aqhYAAAAAAGhSBYfga9eu/dgx5eXlOeKII1JSUrJPRQEAAAAA\nQFMoOAQfNWpUQePKy8vTq1evDB06NL169Wp0YQAAAAAAsK8KDsG//vWv57HHHsu6devSv3//HHXU\nUUmSVatW5Xe/+12qqqpyzjnnZPXq1fntb3+b73//+/ne976XPn36NFvxAAAAAADwUQoOwWtra7Nt\n27bcfvvtad269U77hg0blhtvvDFbtmzJiBEjMnTo0Hz3u9/Ngw8+KAQHAAAAAKDFlBY6cN68efnr\nv/7rXQLwJGnTpk3OO++8zJ07N0lyxBFH5Nxzz82KFSuarlIAAAAAANhLBYfgmzZtyp///Oc97t+y\nZUs2bdrU8LiysjLbt2/ft+oAAAAAAGAfFByCn3DCCXn00Ufz2muv7bJvxYoVeeyxx9K9e/eGbTU1\nNTnyyCObpkoAAAAAAGiEgtcEHzlyZMaNG5fvfve76d69e8MHY7711ltZvnx5Kioqcu211yZJ6urq\nsnTp0px++unNUzUAAAAAABSg4BD8U5/6VP7xH/8x//qv/5rnn38+ixYtSpJUVVVl0KBBufDCCxtm\nfpeXl+cHP/hB81QMAAAAAAAFKjgET5IOHTpk5MiRzVULAAAAAAA0qYLXBAcAAAAAgIONEBwAAAAA\ngKIlBAcAAAAAoGgJwQEAAAAAKFpCcAAAAAAAipYQHAAAAACAolW2twfU1NRk9erVee+997J9+/Zd\n9g8YMKBJCgMAAAAAgH1VcAj+1ltvZeLEiVm+fPlHjhOCAwAAAABwoCg4BP/Zz36WlStXZsSIEend\nu3dat27dnHUBAAAAAMA+KzgEX7ZsWS6++OJ8/vOfb856AAAAAACgyRT8wZht27ZNRUVFc9YCAAAA\nAABNquAQfODAgfntb3+b+vr65qwHAAAAAACaTMHLofzFX/xF6uvr853vfCcDBgzIkUcemdLSXTP0\nM888s0kLBGD/qp81vaVLaDLvVlSkfvPmli6jyZRecEVLlwAAAAAHnYJD8Ntvv73h/6dP33NAIgQH\nAAAAAOBAUXAIfvPNNzdnHQAAAAAA0OQKDsFPPPHE5qwDAAAAAACaXMEh+A719fVZsWJF1qxZkyTp\n2LFjunXrttv1wQEAAAAAoCXtVQi+cOHCTJ06NbW1tTttr6yszPDhw60HDgAAAADAAaXgEPyZZ57J\nT3/60xxzzDG5+OKL06VLlyRJTU1N5s2bl9tvvz3l5eU59dRTm61YAAAAAADYGwWH4A8//HC6deuW\ncePGpby8vGF7nz59ct555+Wmm27KQw89JAQHAAAAAOCAUXAI/qc//SlXXHHFTgH4Doceemg++9nP\nZvr06XtdwJw5czJr1qzU1tamS5cuGTFiRHr37r3H8StXrszkyZOzfPnytGnTJgMHDszQoUNTUlLS\nMGbr1q156KGH8tRTT2X9+vVp165dhgwZki984Qt7XR8AAAAAAAevgkPwVq1aZdOmTXvcv3HjxrRq\n1WqvXnzhwoWZMmVKvvKVr6RXr16ZO3duxo8fn5/85CepqqraZfzmzZtzyy23pHfv3pkwYULefPPN\nTJo0Ka1atcqQIUMaxv2v//W/8s477+TrX/96jjrqqGzYsCF1dXV7VRsAAAAAAAe/gkPwPn365NFH\nH03fvn13mam9bNmyPPbYYznllFP26sVnz56dAQMGpLq6OkkycuTIPPfcc5k7d26uuOKKXcYvWLAg\ndXV1GT16dMrLy9O1a9e88cYbmT17dgYPHpySkpI8//zzWbJkSSZOnJi2bdsmSTp16rRXdQEAAAAA\nUBwKDsGvuuqqLFu2LGPHjk23bt1y9NFHJ0lWrVqVFStWpLKyMldeeWXBL7x169asWLFipxncSdK3\nb9+89NJLuz3m5ZdfTq9evXZakqVfv36ZMWNG1qxZk06dOuWZZ55J9+7dM3v27Dz11FMpLy/PySef\nnCuuuCKHHXbYLs85f/78zJ8/P0ly66237nYGOgefsrIy30v0QSO9W1HR0iU0mdLS0lQU0fm02U/9\nXEw9kBRXH+yvHig27gck+gA9gB7gA/oAPfDJVHAI3rFjx/zwhz/MI488kmeffTZPP/10w/YvfvGL\nueiiixpmXhdi48aNqa+vT7t27XbaXllZmSVLluz2mNra2nTo0GGX8Tv2derUKatXr86yZctSVlaW\nb3/723nvvfdyzz33ZP369fn2t7+9y3NWV1c3zERPkrVr1xZ8Dhy4qqqqfC/RB41Uv3lzS5fQZCoq\nKrK5iM5ny37q52LqgaS4+mB/9UCxcT8g0QfoAfQAH9AH6IHi0blz54LHFhyCJ0nbtm0zfPjwDB8+\nfK+L2l+2b9+eJLnhhhsaZn2NHDky//AP/5Da2tqG0BwAAAAAgOJX2lIv3LZt25SWlmbDhg07bf+o\noLqysnK343fs2/HfDh067PTPno855pgkZnkDAAAAAHzS7HEm+IMPPpgkueSSS1JaWtrw+ONceuml\nhb1wWVm6deuWxYsX54wzzmjYvmTJkpx22mm7PaZHjx6ZNm1a6urqGtYFX7x4cdq3b5+OHTsmSXr1\n6pVFixZly5YtDWuAr1q1KkkaxgAAAAAA8MmwxxD8gQceSJJcdNFFKS0tbXj8cQoNwZNk8ODBmThx\nYrp3756ePXtm3rx5WbduXQYOHJgkmT59epYvX56bbropSdK/f/888MADmTRpUi655JKsWrUqM2fO\nzKWXXpqSkpKGMQ899FAmTZqUL33pS3nvvfcyZcqUnH766busPw4AAAAAQHHbYwg+Y8aMj3zcFM48\n88xs2rQpDz/8cNavX59jjz02Y8aMaZixvX79+qxevbphfEVFRW688cZMnjw5Y8aMSevWrTN48OAM\nHjy4Ycxhhx2WG2+8MT//+c8bxvzVX/1VrrzyyiavHwAAAACAA9tefTBmcxg0aFAGDRq0232jRo3a\nZVvXrl0zbty4j3zOzp0753/8j//RJPUBAAAAAHDwKviDMS+77LIsWLBgj/sXLlyYyy67rEmKAgAA\nAACAplBwCP5x6uvrG9blBgAAAACAA0GTheDLly9P69atm+rpAAAAAABgn33kmuCPPvpoHn300YbH\nU6dOzX333bfLuPfeey+bN2/OgAEDmr5CAAAAAABopI8Mwdu2bZsuXbokSdasWZMOHTqkffv2O40p\nKSlJq1atcsIJJ+zxAy4BAAAAAKAlfGQI3r9///Tv3z9JMm7cuFxyySU56aST9kthAAAAAACwrz4y\nBP/Pbr755uasAwAAAAAAmlzBIfgOW7duzZtvvpnNmzenvr5+l/0nnnhikxQGAAAAAAD7quAQfPv2\n7fnlL3+ZOXPmZMuWLXscN2PGjCYpDAAAAAAA9lXBIfjMmTMzc+bMnHfeeendu3fuuOOOXHnllamo\nqMicOXNSWlqaq666qjlrBQAAAACAvVJa6MDf/OY3Oe200/K1r30tJ598cpKkW7duqa6uzvjx41Nf\nX5+lS5c2W6EAAAAAALC3Cg7B165dmz59+nxwUOkHh9XV1SVJDj300Hz2s5/Nk08+2QwlAgAAAABA\n4xQcgrdu3Trvv/9+kuTwww9PWVlZ3nnnnYb95eXl2bRpU9NXCAAAAAAAjVRwCH7sscfm9ddf/+Cg\n0tJ07949c+fOzTvvvJO1a9dm3rx56dy5c3PVCQAAAAAAe63gEPyzn/1sampqGpZA+fKXv5w333wz\n119/fUaNGpW33norX/7yl5utUAAAAAAA2FtlhQ4855xzcs455zQ87tWrV37yk5/kD3/4Q0pLS9Ov\nX78cffTRzVEjAAAAAAA0SsEh+O506tQpX/jCF5qqFgAAAAAAaFKNCsG3bt2azZs3Z/v27bvsa9eu\n3T4XBQAAAAAATaHgEPz999/PI488kt/85jdZv379bgPwJJkxY0aTFQcAAAAAAPui4BD87rvvzlNP\nPZUePXrk9NNPT0VFRXPWBQAAAAAA+6zgEPzpp5/OgAEDcv311zdnPQAAAAAA0GRKCx3YqlWrdO/e\nvTlrAQAAAACAJlXwTPD+/fvn3//933P++ec3Zz20oPpZ01u6hCbzbkVF6jdvbukymkzpBVe0dAkA\nwCdMMf1smBTXz4d+NgQA2DsFh+BXXnll7rrrrowfPz7nnntujjzyyJSW7jqR3GxxAAAAAAAOFAWH\n4HV1dfnzn/+c559/Ps8///wex82YMaNJCgMAAAAAgH1VcAg+adKk/OEPf8hZZ52V7t27p6Kiojnr\nAgAAAACAfVZwCL548eJ87nOfy4gRI5qxHAAAAAAAaDq7Luq9BxUVFTnqqKOasxYAAAAAAGhSBYfg\n5513XhYsWJBt27Y1Zz0AAAAAANBkCl4O5eijj84zzzyTv/u7v8vZZ5+dI488MqWlu2boZ555ZpMW\nCAAAAAAAjVVwCD5x4sSG/58+ffoexwnBAQAAAAA4UBQcgt98883NWQcAAAAAADS5gkLw+vr6dOrU\nKYcddljatGnT3DUBAAAAAECTKOiDMevr6/PNb34zTzzxRDOXAwAAAAAATaegELysrCzt27dv7loA\nAAAAAKBJFbwm+DnnnJMnn3wy559/fsrLy5usgDlz5mTWrFmpra1Nly5dMmLEiPTu3XuP41euXJnJ\nkydn+fLladOmTQYOHJihQ4empKRkl7HLli3L2LFjc8wxx+RHP/pRk9UMAAAAAMDBoeAQvHPnzqmv\nr8+3vvWtDBgwIJ06ddptGH7mmWcW/OILFy7MlClT8pWvfCW9evXK3LlzM378+PzkJz9JVVXVLuM3\nb96cW265Jb17986ECRPy5ptvZtKkSWnVqlWGDBmy09h33303d9xxR0466aSsW7eu4JoAAAAAACge\nBYfgEydObPj/hx56aI/j9iYEnz17dgYMGJDq6uokyciRI/Pcc89l7ty5ueKKK3YZv2DBgtTV1WX0\n6NEpLy9P165d88Ybb2T27NkZPHjwTrPB/+mf/ikDBgzI9u3b8/TTTxdcEwAAAAAfqJ81vaVLaFLv\nVlSkfvPmli6jyZResGt+Buyq4BD85ptvbtIX3rp1a1asWLHLDO6+ffvmpZde2u0xL7/8cnr16rXT\nDPR+/fplxowZWbNmTTp16pTkgyVWNmzYkKFDh+bBBx9s0roBAAAAADh4FByCn3jiiU36whs3bkx9\nfX3atWu30/bKysosWbJkt8fU1tamQ4cOu4zfsa9Tp05ZuXJlHnzwwfzDP/xDSks//nM/58+fn/nz\n5ydJbr311t0uw/JJ8W5FRUuX0GRKS0tTUUTn0+YT3Jf7oqys7BP9nm4s14ID1/66FhRTDyTF1Qfu\nB43jftA4rgUHLteCxnEtQA80jvvBgc09Ye+5FnwyFRyC71BfX58VK1ZkzZo1SZKOHTumW7duBQXO\nze3999/PT37yk1x99dUNs8I/TnV1dcNyLEmydu3a5irvgFdM/xyooqIim4vofLZ8gvtyX1RVVX2i\n39ON5Vpw4Npf14Ji6oGkuPrA/aBx3A8ax7XgwOVa0DiuBeiBxnE/OLC5J+w914Li0blz54LH7lUI\nvnDhwkydOjW1tbU7ba+srMzw4cP3aj3wtm3bprS0NBs2bNhpe21tbcPs7g+rrKzc7fgd+9avX583\n3ngjkyZNyqRJk5Ik27dvz/bt23P55ZdnzJgx6devX8E1AgAAAABwcCs4BH/mmWfy05/+NMccc0wu\nvvjidOnSJUlSU1OTefPm5fbbb095eXlOPfXUwl64rCzdunXL4sWLc8YZZzRsX7JkSU477bTdHtOj\nR49MmzYtdXV1DeuCL168OO3bt0/Hjh2zbdu2/OM//uNOx8ydOzeLFy/Od77znYJnhwMAAAAAUBwK\nDsEffvjhdOvWLePGjdvpgyn79OmT8847LzfddFMeeuihgkPwJBk8eHAmTpyY7t27p2fPnpk3b17W\nrVuXgQMHJkmmT5+e5cuX56abbkqS9O/fPw888EAmTZqUSy65JKtWrcrMmTNz6aWXpqSkJGVlZena\ntetOr9ES1IiiAAAgAElEQVS2bdsceuihu2wHAAAAAKD4FRyC/+lPf8oVV1yxUwC+w6GHHprPfvaz\nmT59+l69+JlnnplNmzbl4Ycfzvr163PsscdmzJgx6dixY5Jk/fr1Wb16dcP4ioqK3HjjjZk8eXLG\njBmT1q1bZ/DgwRk8ePBevS4AAAAAAJ8MBYfgrVq1yqZNm/a4f+PGjWnVqtVeFzBo0KAMGjRot/tG\njRq1y7auXbtm3LhxBT//sGHDMmzYsL2uCwAAAACAg19poQP79OmTRx99NC+++OIu+5YtW5bHHnss\nJ510UpMWBwAAAAAA+6LgmeBXXXVVli1blrFjx6Zbt245+uijkySrVq3KihUrUllZmSuvvLLZCgUA\nAAAAgL1VcAjesWPH/PCHP8wjjzySZ599Nk8//XTD9i9+8Yu56KKL0rZt22YrFAAAAAAA9tYeQ/BH\nH300J598cjp37tywrW3bthk+fHiGDx++X4oDAAAAAIB9scc1wadOnZoVK1Y0PL7sssuyYMGC/VIU\nAAAAAAA0hT2G4G3atMm6dev2Zy0AAAAAANCk9rgcSp8+ffLAAw/k5ZdfTkVFRZJk/vz5Wbx48R6f\nrKSkJNddd13TVwkAAAAAAI2wxxD8q1/9aqZNm5alS5dmw4YNSZJXXnllpyVSPkwIDgAAAADAgWSP\nIfgRRxyRb3zjGw2PL7vsslx33XXp37//fikMAAAAAAD21R7XBP+w6667Lj169GjOWgAAAAAAoEnt\ncSb4h51zzjnNWAYAAAAAADS9gkPwJHnuuefyf/7P/8nbb7+d9957L9u3b99pf0lJSSZOnNikBQIA\nAAAAQGMVHILPmjUr06ZNS2VlZU444YR07dq1OesCAAAAAIB9VnAI/uijj6ZPnz4ZM2ZMysr2agI5\nAAAAAAC0iII/GPO9997L6aefLgAHAAAAAOCgUXAI3r1797z55pvNWQsAAAAAADSpgkPwr3zlK/n9\n73+f3/72t81ZDwAAAAAANJmC1zb50Y9+lK1bt+aOO+7I3XffnQ4dOqS0dOcMvaSkJD/+8Y+bvEgA\nAAAAAGiMgkPwdu3apbKyMp07d27OegAAAAAAoMkUHIKPHTu2GcsAAAAAAICmV/Ca4AAAAAAAcLDZ\n40zwtWvXJkmqqqp2evxxdowHAAAAAICWtscQfNSoUUmSadOmpaysrOHxx5kxY0bTVAYAAAAAAPto\njyH4ddddlyQ55JBDdnoMAAAAAAAHiz2G4Oecc85HPgYAAAAAgAOdD8YEAAAAAKBoCcEBAAAAACha\nQnAAAAAAAIqWEBwAAAAAgKIlBAcAAAAAoGgJwQEAAAAAKFpCcAAAAAAAipYQHAAAAACAoiUEBwAA\nAACgaAnBAQAAAAAoWkJwAAAAAACKVllLFzBnzpzMmjUrtbW16dKlS0aMGJHevXvvcfzKlSszefLk\nLF++PG3atMnAgQMzdOjQlJSUJEmefvrpzJs3L6+99lref//9dOnSJZdccklOPfXU/XVKAAAAAAAc\nIFp0JvjChQszZcqUXHzxxbntttvSs2fPjB8/PmvXrt3t+M2bN+eWW25Ju3btMmHChFx77bWZNWtW\nZs+e3TBm6dKl6dOnT8aMGZMf/OAHOeWUU/LDH/4wL7744v46LQAAAAAADhAtOhN89uzZGTBgQKqr\nq5MkI0eOzHPPPZe5c+fmiiuu2GX8ggULUldXl9GjR6e8vDxdu3bNG2+8kdmzZ2fw4MEpKSnJtdde\nu9MxX/rSl/J//+//zTPPPPORM8wBAAAAACg+LRaCb926NStWrMiQIUN22t63b9+89NJLuz3m5Zdf\nTq9evVJeXt6wrV+/fpkxY0bWrFmTTp067fa4LVu2pHXr1rvdN3/+/MyfPz9Jcuutt6aqqqoxp1MU\n3q2oaOkSmkxpaWkqiuh82nyC+3JflJWVfaLf043lWnDg2l/XgmLqgaS4+sD9oHHcDxrHteDA5VrQ\nOK4F6IHGcT84sLkn7D3Xgk+mFgvBN27cmPr6+rRr126n7ZWVlVmyZMluj6mtrU2HDh12Gb9j3+5C\n8F//+td55513cvbZZ+/2OaurqxtmoifZ41IsnwT1mze3dAlNpqKiIpuL6Hy2fIL7cl9UVVV9ot/T\njeVacODaX9eCYuqBpLj6wP2gcdwPGse14MDlWtA4rgXogcZxPziwuSfsPdeC4tG5c+eCx7bomuDN\nbdGiRbn33nvzN3/zN+nYsWNLlwMAAAAAwH7WYiF427ZtU1pamg0bNuy0vba2tmF294dVVlbudvyO\nff/ZokWLcscdd2T06NE59dRTm7ByAAAAAAAOFi0WgpeVlaVbt25ZvHjxTtuXLFmSnj177vaYHj16\nZNmyZamrq2vYtnjx4rRv336nmd4LFy7MxIkTc/311+f0009vnhMAAAAAAOCA16LLoQwePDhPPPFE\nHn/88dTU1OSee+7JunXrMnDgwCTJ9OnT8/3vf79hfP/+/VNeXp5JkyZl5cqVefrppzNz5swMHjw4\nJSUlSZLf/e53mThxYq688sqceOKJqa2tTW1tbd59990WOUcAAAAAAFpOi30wZpKceeaZ2bRpUx5+\n+OGsX78+xx57bMaMGdMwq3v9+vVZvXp1w/iKiorceOONmTx5csaMGZPWrVtn8ODBGTx4cMOYefPm\nZdu2bZkyZUqmTJnSsP3EE0/M2LFj99epAQAAAABwAGjREDxJBg0alEGDBu1236hRo3bZ1rVr14wb\nN26PzyfoBgAAAABghxZdDgUAAAAAAJqTEBwAAAAAgKIlBAcAAAAAoGgJwQEAAAAAKFpCcAAAAAAA\nipYQHAAAAACAoiUEBwAAAACgaAnBAQAAAAAoWkJwAAAAAACKlhAcAAAAAICiJQQHAAAAAKBoCcEB\nAAAAAChaQnAAAAAAAIqWEBwAAAAAgKIlBAcAAAAAoGgJwQEAAAAAKFpCcAAAAAAAipYQHAAAAACA\noiUEBwAAAACgaAnBAQAAAAAoWkJwAAAAAACKlhAcAAAAAICiJQQHAAAAAKBolbV0AcCBo37W9JYu\noUm9W1GR+s2bW7qMJlN6wRUtXQIAAADAQcdMcAAAAAAAipYQHAAAAACAoiUEBwAAAACgaAnBAQAA\nAAAoWkJwAAAAAACKlhAcAAAAAICiJQQHAAAAAKBoCcEBAAAAAChaQnAAAAAAAIqWEBwAAAAAgKIl\nBAcAAAAAoGiVtXQBc+bMyaxZs1JbW5suXbpkxIgR6d279x7Hr1y5MpMnT87y5cvTpk2bDBw4MEOH\nDk1JSUnDmKVLl2bq1KmpqalJ+/btc8EFF+T888/fH6cDAHDQq581vaVLaFLvVlSkfvPmli6jyZRe\ncEVLlwAAAAeVFp0JvnDhwkyZMiUXX3xxbrvttvTs2TPjx4/P2rVrdzt+8+bNueWWW9KuXbtMmDAh\n1157bWbNmpXZs2c3jHn77bczYcKE9OzZM7fddlsuuuii3HPPPVm0aNH+Oi0AAAAAAA4QLRqCz549\nOwMGDEh1dXW6dOmSkSNHpn379pk7d+5uxy9YsCB1dXUZPXp0unbtmtNPPz0XXnhhZs+ene3btydJ\n5s6dm/bt22fkyJHp0qVLqqurM2DAgPzqV7/an6cGAAAAAMABoMWWQ9m6dWtWrFiRIUOG7LS9b9++\neemll3Z7zMsvv5xevXqlvLy8YVu/fv0yY8aMrFmzJp06dcorr7ySvn377nRcv3798uSTT2br1q0p\nK2vxFWAAAAAA4KBgqbwDm6XyCtNiifDGjRtTX1+fdu3a7bS9srIyS5Ys2e0xtbW16dChwy7jd+zr\n1KlTamtrc9JJJ+00pl27dtm2bVs2bdqU9u3b77Rv/vz5mT9/fpLk1ltvTefOnffpvA5q3/hOS1fQ\npDp8/BA+rMh6INEHjVJkfaAHGqHIeiDRB3tND5DoA4rSJ/r3PZLogUZxP0APUARadDmUA0F1dXVu\nvfXW3HrrrS1dCk3ou9/9bkuXwAFAH6AHSPQBeoAP6AP0AHqARB+gBz6pWiwEb9u2bUpLS7Nhw4ad\nttfW1jbM7v6wysrK3Y7fsW/Hf3ds22HDhg055JBDcsQRRzRV+QAAAAAAHARaLAQvKytLt27dsnjx\n4p22L1myJD179tztMT169MiyZctSV1fXsG3x4sVp3759OnbsmCT59Kc/vctyKosXL063bt2sBw4A\nAAAA8AlzyNixY8e21Isffvjhuf/++9O+ffuUl5fnoYceytKlS3P99dendevWmT59eh555JEMGDAg\nSXL00Udn3rx5+eMf/5jOnTtn2bJluffee3PRRRc1BOdHHXVUZs6cmY0bN6aqqirPPPNMHn744Vxz\nzTXp0qVLS50qLaBbt24tXQIHAH2AHiDRB+gBPqAP0APoARJ9gB74JCrZvn379pYsYM6cOZk1a1bW\nr1+fY489NsOHD8+JJ56YJLnzzjuzdOnS3HnnnQ3jV65cmcmTJ2f58uVp3bp1Bg4cmEsvvTQlJSUN\nY5YuXZqpU6fmT3/6U9q3b58LL7ww559//n4/NwAAAAAAWlaLh+AAAAAAANBcWmxNcIB9NWzYsCxa\ntKhRx7799tsZNmxYXn311SauCgAAAIADiRAcgEbbuHFjhg0blhdeeKGlS8kTTzyRq6++uqXLYB/c\neeedufXWW/f5ee6///58+9vfboKKYGejRo3KrFmzWrqMovHCCy9k2LBh2bhx4z49T0v8YbuQ64xr\nEXCwGjt2bCZPntzSZbAHTXX/PFA01e8A8HGE4MBBZ+vWrS1dAi1sd/8K4Mwzz8wdd9zRQhXRFK69\n9tp885vfbHjc0r+ANfYXDP/S5OC3p/BywoQJGTRoUAtUxA67uy5UVVXl7rvvznHHHdcyRe3BBRdc\nkLFjx7Z0GZ8IfjYEOPDt6WfrD/8O8ElhcsX+V9bSBQDF57nnnsuPf/zj3HPPPTnkkEPy1ltv5W/+\n5m9SXV2dr33ta0mS++67L6+88kpuvPHGLF26NPfee2/++Mc/pqKiImeddVauuuqqlJV9cIkaO3Zs\njjnmmLRq1SpPPvlkOnXqlAkTJuzyuv/6r/+aX/3qV/n7v//79OjRI1u3bs3999+fBQsWpLa2Nh06\ndMgXvvCFfOELX9jl2Pr6+tx11135f//v/6W2tjZHHnlkzjvvvAwZMiSlpR/8vXDlypWZMmVKXn31\n1dTX1+eoo47K8OHD06dPn2zdujX/8i//kqeffjqbNm1Ku3bt0r9//1x55ZXN+JXmPysvL095eXlL\nl0EjbNu2LaWlpamoqGjpUuAjtW3btqVLOGhs3bq14T7e3EpLS1NZWblfXmtvHHbYYTnssMNauoyi\ntLufDc8666w88cQTWb16dSoqKnLKKafk6quvTuvWrRuOe/nll/PLX/4yy5cvT2lpabp165ZvfvOb\n6dChQ7Zv355Zs2Zl/vz5WbduXY466qhceOGFOfvss1vwTCnU0qVLM23atKxcuTKlpaXp3Llzrrvu\nunTt2jUvvfRSpk+fnldffTWtW7fOqaeemiuvvDIVFRXZuHFjvvOd72TgwIH50pe+lCT54x//mO99\n73sZPXp0zjjjjBY+s0+O+vr6JGn43etAsT/vZ59UfgfYswP1fXGw8k7moPHcc8/l4Ycfzp/+9Kck\nSffu3TN8+PB06dIlSfLKK6/kn//5n1NTU5MuXbrky1/+csaPH5+bb745n/nMZ5IkNTU1+cUvfpEX\nX3wx5eXl6dOnT0aMGHFA/uJ0MOvVq1fef//9vPrqq+nRo0deeOGFHHHEEVm6dGnDmBdeeCEnn3xy\n1q1blwkTJuSzn/1srr/++qxevTr/9E//lNLS0lxzzTUN43/729+muro63//+9/Phz/Pdvn17fvGL\nX2ThwoUZO3Zsjj322CTJHXfckWXLlmXEiBE5/vjjs27duqxZs2a3NdfX16dDhw751re+lbZt22b5\n8uW5++67c8QRR+Sv//qvkyQ//elP86lPfSrjx4/PIYcckpUrVzaEro899lieeeaZ3HDDDenUqVPe\neeedvPnmm036dd0fPu4XwOXLl+dnP/tZampqcswxx+Tyyy/f6fgXXngh48aNyz//8z83hEVvv/12\nRo8enQkTJuSEE05Ikrzxxhu59957s3Tp0tTX16dr1675+te/nq5du2b58uW577778tprr2Xr1q3p\n2rVrrr766vTo0SPJB38xT5If//jHSZKOHTvmzjvvzBNPPJHJkyfnF7/4RUM98+bNy6xZs7J27dpU\nVVXlwgsvTHV1dcP+YcOG5Wtf+1oWL16cZ599Nu3atcuwYcMK+oV3x3n97d/+bebNm5eXXnopHTt2\nzLXXXpu+ffsW/PXYMWbMmDG57777UlNTkxNOOCE33HBDVq9enXvuuSdvvfVWPvOZz2TUqFE54ogj\n9v4buw/+c9Dwm9/8JqWlpRk6dGgGDhyYqVOnZsGCBTn88MPz5S9/ueHrNm3atPz+97/P2rVrU1lZ\nmTPOOCPDhg1reL/cf//9efrppzNkyJA89NBDefvttzN16tRMnjw5mzZtyne/+93ceeedWbp0aZYu\nXZo5c+Yk+eA9XVVV9bF/sNobe/rjVqdOnTJu3LgkyVe/+tUkyYABAzJq1KiPvR+NHj06STJmzJgk\nyYknnpixY8fmzjvvbDi/HXZ8LX70ox99ZD19+vTZ63NrKe+//36mTZuW3/3ud9m8eXOOO+64XH31\n1enVq1eSj37/Jx8sbfSrX/0qq1atSuvWrdOvX7+Gr+mwYcPyt3/7tzn99NMbXm/UqFEZNGhQLrjg\ngoYxI0eOzLPPPpsXXnghbdu2zeWXX77T+/qjevSJJ57Igw8+2PBcSXL99dfnnHPO2eW11q5dm3vu\nuSdLlixJkvTt2zfXXnttjjzyyCT///f3kksuyX333ZcNGzakT58++cY3vlF0gfruQskbb7wxv/jF\nL/LMM8+krq4uxx9/fK655pqGe8GHbdq0KZMnT86yZcuyadOm/MVf/EWGDBmSc889N0n2eF1Isst9\nppA/sHfp0iUVFRV5/PHHU1JSkrPPPjtXXXVVw7Xk6aefzgMPPJBVq1alvLw8Xbt2zbe+9a2dfm78\n3e9+t8fv7Yff3zuuAZ/+9Kfz61//Olu2bMkZZ5yRr371q/6I2wgf/tnw+eefz4gRI9KpU6esXbs2\nP//5z/Pzn/+8YXbh66+/nnHjxuXss8/O8OHDc+ihh+bFF19sCBjuu+++LFq0KF/5ylfSuXPnvPzy\ny7nrrrvSpk2b/Jf/8l9a8lT5GNu2bcsPf/jDnHvuufnmN7+Zbdu25bXXXktpaWlWrlyZ//k//2eG\nDRuWb3zjG3n33XczZcqU/O///b/z7W9/O23bts3111+f2267Lf369ctxxx2Xn/70pznrrLM+8QH4\n9u3bM3369N1eI3d8Hf/93/89dXV16dWrV0aMGNHwe9jufi7/8M/FO8Z861vfyrRp0/LGG2/kBz/4\nQZI06mehHc//93//97nvvvvy5ptvpkuXLvn617+ebt26NYz7qD+KJIVPwNph2rRpef311/Pf//t/\nT5I8/vjjueuuu3LDDTfkrLPOSpLceOONOfnkkzN06NAkyR/+8Ic88MADqampSWVlZfr3758vfelL\nDfeorVu35r777suCBQvy7rvv5thjj81l/197Zx5WZbU18N+BAyIi4BFQBAVJEo9hhl7lpnidNczM\n0riC5pBWqFlqTqSFmmBWXsQQFcfEWbNES800xbFQQkEhEEgBmWTQRGQ4fH/wnPfjwAEOOGL79zw+\nj7zDftfZ77v3Xnuttdf28KBz585aZSguLiYgIIDs7Gx8fHwwMzOrsa7qS21j58mTJ/npp59ITU3F\n0NAQpVLJuHHjUCgUZGZmVqtbV9SRjx49ys6dO1mzZo2Gbr9ixQoKCwuZM2eOTnVYE7UFy+miQ7Ru\n3Zp33nlHKrOynl9bXfn6+pKVlUVoaCihoaFAud6grV18+umnLF68mODgYA0dZPv27Vy4cIGvvvqq\n3u/0n4YwggsaDIWFhbi7u2NnZ0dRURF79+7liy++4H//+x8lJSUsXbqUTp06MXXqVHJzc9m8ebPG\n/bm5uXz22Wf06dOHMWPGUFpayvbt21m2bBmff/658Kw9RIyMjHBwcCAmJkYygg8ePJjvv/+e3Nxc\njI2NuXbtGl5eXhw+fJhmzZoxceJE9PT0sLW1xcvLi7Vr1+Lh4UGjRo0AsLKy0jCKq1GpVAQHBxMX\nF8fixYuxtLQE4ObNm5w5cwYfHx9JWWjRogUdOnTQKrNcLsfDw0P628rKiqSkJE6fPi0ZwbOzsxk6\ndCg2NjYAtGzZUro+KysLa2trOnTogEwmw8LCgvbt2z+E2ny81DQBVCqVLF26FKVSyZQpU8jJyanS\nznQhJyeHTz/9lPbt27NgwQJMTExISEiQJqGFhYX06tWLcePGIZPJOHToEP7+/gQGBtK0aVP8/f2Z\nOHEi7733Hl26dKm27f72229s2LCBsWPH0qlTJ6Kioli/fj3m5uZ07dpVum7Pnj14enri6enJsWPH\nCA4ORqlUYmFhoXOdjR49mokTJ7J3714CAgJYtWpVnaP/du3axbhx4zA2NiYwMJCAgAAMDAx49913\n0dPTY/ny5ezevZsJEybUqdyHwalTpxgyZAh+fn5ERESwadMm/vjjDzp37szSpUv59ddfWb16Nc7O\nzjRr1oxGjRrh7e2NQqEgJSWFkJAQ5HK5htMkMzOTU6dOMX36dORyOQYGBhrPHD9+PDdv3qRVq1Z4\nenoC5VG4ujis6kJ1zi0LCwtmzpzJ119/zfLlyzExMZGMVDWNR3K5HD8/P3x8fPDx8cHe3r5O0UM1\nOdsaCqGhoZw9exZvb2+srKw4cOAAS5YsITAwkLKyshrb/88//8ymTZsYNWoULi4u3L9/n+jo6DrL\nsGvXLkaNGsXYsWM5d+4cQUFB2NjYSAbSmr7Rl19+mevXr3Px4kUplYW2CCWVSsWyZcswNDTks88+\nA2DDhg18+eWX+Pv7I5PJgPJv/cyZM3z88cfcv3+fgIAAduzYIa2MepaobJT09/fH2NiYuXPnYmJi\nwq+//sqiRYsICAigWbNmVe4vLi7GwcGB119/ncaNG3P58mXWrl2LhYUFzs7O1fYL2dnZGuXUxcHu\n7u7O4sWLSU5OJjAwEAcHB3r27EleXh4BAQF4enrSvXt3CgsLiY+P13hOfd7tlStXMDQ0ZMGCBeTk\n5BAcHExoaOgT6dsbOpV1Q7UjUn1u9OjRLFu2jClTpqCnp8f+/fuxt7fnvffek65T63SFhYUcOHCA\n+fPnS7qilZUVCQkJHD58WBjBn3Lu3bvH3bt36dq1q6Sfq9/tN998w8svv8zQoUOl6ydNmsTs2bPJ\nz8/HzMyMzp07M2jQIAIDA1EqlRQXF4s2Sc195KpVq0hLS2PWrFmYmJiwfft2/Pz8WLFiRZ30luLi\nYvbu3cukSZMwNTWlWbNmzJ8//4F0oS1btkiG1z179rB06VJWrlxJo0aNanWKVPzt1QVgVaZjx44c\nPnyY0tJS9PX1pQCwmJgYevTowf3796W5L5QH961cuZJx48bRoUMHsrOzCQkJobi4WOrTVq1aRUZG\nBtOmTaN58+ZERkbyxRdf4O/vXyX1V0FBAV9++SUqlYrPPvvskUdV1/RdlJSUMHLkSGxsbLhz5w5b\nt25lxYoVLFy4sEbduiKurq5s3LiRS5cuSfP4wsJCIiIi8Pb21rkOa6KmYDlddYgHrauPP/6YWbNm\n0adPHwYOHKhxn7Z20aJFC06cOMGwYcOAcj305MmTGn2boHaEEVzQYKgY9QXlUVljx44lISGBGzdu\noFKp8Pb2xtDQkNatWzN8+HACAwOl648cOYKdnR2jR4+Wjk2dOpUJEyaQmJhIu3btHttv+SegVCq5\ncuUKw4cP5+rVq7i7uxMTEyNF5enr69OuXTsOHDiAo6OjhiHTycmJkpIS0tPTsbOzA9Dw3ldky5Yt\n6Onp4efnp+HxTkpKQiaTSasAdOHIkSMcO3aMrKwsioqKKC0tlYzqAEOGDGHNmjWcOHECZ2dnunfv\nLinYvXv35vPPP+fDDz+kU6dOuLi40Llz5wblXKltApiTk0NJSQmTJ0/GyMiINm3acPv27Trn4T58\n+DCNGjVixowZknGwokOhcpTHhAkTOH/+PJGRkfTq1UuKsGvSpEmNqzjCwsJwc3Nj8ODBALRq1YrE\nxER++OEHDSN4r169pAhRDw8PfvzxR65cuaLz8uchQ4ZI5Xl6enLy5EmSk5OlqFdd8fDwkOp9wIAB\nbNiwgaVLl0rf/n/+8x/Onz9fpzIfFra2tlJE7Kuvvsr333+Pvr6+FC0xYsQIfvjhB+Li4nB1dWXE\niBHSvVZWVgwfPpywsDANI3hJSQlTp06t9h0aGxsjl8tp1KiRxjV6enq1OqzqQk3OLRMTE6DcyFYx\narem8cjJyUm6tmnTpnVeaVSTPA2BwsJCjhw5wvvvvy8Zjd59911iYmI4fPgwZWVlNbb/vXv34u7u\nzquvvioda9u2bZ3l6NatGwMGDADgjTfeICYmhoMHDzJt2jSAGr9RQ0NDjIyM0NfXr/H9RUdH89df\nf7Fy5UqsrKwAmDZtGtOmTePy5cvSihCVSsWUKVOkSWn//v05fvx4nX9TQ6CiUTI6Oprk5GTWr18v\nTXL/+9//cuHCBU6ePClN4iqiUCikKHsod15HR0dz+vRpnJ2dq+0XKqOrg93W1lbqT1q1asUvv/xC\ndHQ0PXv2JCcnh9LSUlxdXSVdQL1aQU193q2enp7GOOrl5cXq1avx9PQUqVPqSGXdMDo6mn379pGa\nmkpBQQEqlYqSkhIpyi8pKYlu3bppLSslJYXi4mL8/Pw0jlfWBQVPJyYmJvTu3ZslS5bwwgsv4Ozs\njKurKxYWFiQmJpKens6ZM2eq3JeRkSHNH7y8vPjjjz84ceIEn3/+uWiPVN9HPvfcc0RERODr64tS\nqU+MNt0AABVRSURBVATggw8+wNvbm/DwcPr166fzM1QqFe+8845Ge35QXejNN9+UjKeTJ0/m/fff\n59SpU/Tr14/9+/fX6hSB6gOwtFF5FfTVq1cZOnSoNB7ExcVJc1+Affv2aaxyatmyJV5eXqxcuZIx\nY8aQkZHB6dOnCQoKkoJyBg8ezKVLlzh69KgURQ1w+/ZtVq5cKQWIPI7AiZrGzoq6eIsWLZg4cSLT\np0/n1q1bNG/evFrduiImJia89NJLhIeHS+/xt99+Q09PT5pz1VaH6kAEbdQWLKerDvGgdWViYoKe\nnh5GRkZVdBpt7aJv374cP35c0p+ioqLIz8/Hzc1NZ3kEwgguaECkp6ezc+dOEhISuH37NiqVirKy\nMrKzs0lNTaVNmzYanX5lo3ZiYiJXr15lzJgxWssWRvCHS8eOHTl06BApKSkUFBTg4OCAUqkkJiYG\nMzMznn/++VqjIysOXtUNNs7Ozpw+fZrIyEh69+5db3nPnDnD5s2bpbQbxsbGHDp0iN9//1265q23\n3sLNzY3IyEiioqLYvXs3kyZNom/fvjg4OBAUFERUVBSXL18mKCgIOzs75s+f32AM4bVNAFNSUrCz\ns9OYFKhTlNQFtYG4uvefn5/Pzp07iYmJIS8vD5VKRVFRUZVIP11+j1oxUuPk5ERERITGsYpGDX19\nfUxNTeu0EaLaUQNIkY35+fl1krVyOWoFvKJs5ubm9Sr3YVBRNplMhpmZmYZscrkcExMTSb5z585x\n8OBB0tPTKSwsRKVSSZG+ahQKRb1TUdXmsKoLNTm3qqOm8ehBqY88TxMZGRmUlpZqrITR09PD0dFR\n6mOqa//5+fnk5OTg7Oz8wHJU7pscHR2JjIyU/tblG62NlJQUFAqFZACH8klUs2bNSElJkYzgFhYW\nGlFZzZo1q/Nmqw2FipO1xMREioqKNJYKQ3l0U0ZGhtb7VSoV33//PWfOnCEnJ4fi4mJKSkrq5NCG\n8pQ7ujjYK/ZtUP5u1P2Yvb09zs7OzJw5k06dOtGpUydcXV01Ju31ebfaxtGSkhIyMjKqyCOomYq6\nYVZWFv7+/vTr1w8PDw9MTExISkpixYoVOm2aqY70nDNnTpWVYPr6+g9XcMEjYfLkybi7u/PHH38Q\nERHB9u3bmTVrFmVlZfTt21fDuapGoVBI/8/KyuLWrVvIZDIyMjJwdHR8nOI/lVTXR6ampiKTyTTG\nWmNjY9q0aUNKSkqdnqGvr18lsvlBdaGKcqkdjmq5dHWKVBeApY2Kq6BNTU0pKChg8ODB7N69m9zc\nXK5cuaIx901MTCQhIYEffvhBKqOsrIyioiLy8vJISkqirKyM6dOnazynpKSkSrDQkiVLaNu2LTNn\nznxsfVVNY2diYiJ79uwhOTmZv//+W+pbs7OzpVRxuuDm5kZQUBD379+nUaNGnDp1iu7du0v2ntrq\nUNtqMzW1BcvpqkPoQk11VRPa2kXv3r3ZsWMHcXFxtG/fnuPHj/Ovf/3rsafKbOgII7igwfDFF1+g\nUCiYNGkSCoUCfX19ZsyYofNu8GVlZbz00ktaPbqPKmfWPxn1QLF//36cnJzQ09OjY8eOrFmzRlp2\nCOVLFc+ePYtKpZIGmtjYWORyOS1atKj1OS4uLnTv3l3KD602hNvb21NWViblHq+N2NhY2rVrJ0UN\nA1on6dbW1lhbW+Pu7k5ISAjHjh2TPN6NGzfG1dUVV1dXevfuzSeffEJ6ejqtWrWq9flPA7VNAA8e\nPFhrGdq87qWlpXWSIygoiPz8fMaOHYulpSUGBgYsWrRI57ZeVxkrG+NkMlmdjGEVFU512eq6rEt9\naCunsmy1Lcd8VFRWqmUymVZFu6ysjD///JOAgABGjBjB2LFjadKkCRERERo5IYF6R1jp4rCqCzU5\nt6qjvuORTCar8g4rfw/1keefhLY6rGvfoOs3+qByqnnQPqYhUdEoqVKpMDMzY9GiRVWua9y4sdb7\n9+/fT1hYGOPHj6dNmzYYGRmxbdu2h+o0qPhutPVt6u9LT0+P+fPnEx8fT1RUFMeOHWPbtm34+vpK\nE9N/0rt92rl27RolJSWMGzdO0icvXryocU3btm2rTa9ka2uLgYEBWVlZDWoPBoEm9vb22Nvb8/rr\nr+Pn58eJEydo27YtKSkpNUYTl5SUsGLFCrp06YKjoyPr16/HyclJ59R4zyo19ZHVoe5jddWB5XJ5\nlYChR6kL6eoUqUu0LyAFe5mamuLk5ISRkRGOjo7SSuiK81GVSsWIESO05pw3NTWlrKwMmUyGv79/\nlXGmcqS3i4sLZ8+e5caNG1WMpo+K6r6LwsJClixZgrOzM1OnTsXMzIw7d+7w6aef1llXc3FxQV9f\nn99//x1nZ2cuX74s5VyH2uvwUVHx+65Np4f6tSHQ3i5MTU3p2rUrx48fp1WrVkREREj50QW60zDC\nEwX/eO7cuUNqairDhw+nU6dO2Nracu/ePamjsbGx4fr16xQVFUn3JCQkaJShVoAsLCxo2bKlxr/q\nJmOC+qP2iIeHh0teVkdHR27dukV8fLx0bNCgQeTm5kqbml68eJGtW7cyePBgnZWPLl26MGPGDEJC\nQjhx4gRQvtzo3//+N6tXr+bcuXNkZmZy9epVTp48qbUMa2trkpKSiIyM5ObNm+zZs0djI8+ioiLW\nrVtHTEwMmZmZxMfHExsbK+WfPHDgAKdOnSIlJYX09HRps8C6eLyfNBUngJXbiKWlJba2tly/fp3C\nwkLpnsr5UdVKR25urnQsOTlZ4xp7e3tiY2OrVYZiY2MZPHgwLi4utG7dGiMjI43yoFyhqM3QYGtr\nS2xsbJWyK+YMfdToUh/PGnFxcSgUCkaMGEG7du2wtraudkPa2pDL5VXec0WHlYODAy1btqw2qlRX\n1I6tefPm0bdvX44dOyY9H9CQobbxqLr7oPx7yMvL0zim7XuoTp6GQIsWLZDL5cTFxUnHVCoV8fHx\n2Nra1tj+zczMUCgU0iaT2jA1NdVoT3l5eVXqFKr2TfHx8VIUmS7fqLZvrzK2trbk5OSQmZkpHcvI\nyCA3N/ex9jNPKw4ODuTn5yOTyaqMKdUFH8TGxtKlSxd69eqFvb09LVq04ObNmxrX6PJubGxsiI+P\n17iuLg52NepIx5EjR+Lv70+zZs20Rg/WBW3jaF3lElTF2tqasrIyDh48KO05Udl5/9prr5GcnMya\nNWtITk4mLS2NX375hezsbBo3bszQoUPZsmULx44dIz09neTkZI4cOcLRo0ef0K8S6EpmZiZbt24l\nLi6OrKwsKV2Vra0tw4YNk/YPSUpKIj09nQsXLrB27Vrp/p07d3L79m0mTZqEu7s77dq145tvvhFO\nrWqwsbGRAh/UFBQUcP36dWn8MzU15f79+xQUFEjX1EUHfhBdqKIOUFhYyI0bNyQdoKJTpPK/B0kl\n0rFjR+Li4rh06ZI0z1UqlVy8eJFr165pRB07ODiQmpqqVQZ1BHBZWRl5eXlVzlc01EN5OsUBAwaw\naNGiJz7HSEtL486dO3h6eqJUKrGxsakS9VydjlwZAwMDXF1dOXXqFGfOnMHc3FxKvQO112FNVAyW\n04YuOoQ2nf6vv/6q8bna0EWnqUi/fv04e/YsP//8M+bm5g9l9eQ/DWEEFzQImjRpQtOmTfnll19I\nT0/nypUrhISESB1cz5490dPTY/Xq1aSkpHDp0iX27dsH/L+3btCgQRQUFBAQEEB8fDwZGRlcunSJ\nNWvWcO/evSf2255llEolpaWl0qBvaGiIo6MjBgYGUvoZhULBvHnzSE5OZvbs2QQHB9OjRw9GjRpV\np2d16dKF6dOns3btWskQPnXqVHr27MnGjRv56KOPWLVqlYYiVpEBAwbw73//m8DAQObNm0dWVpZG\nrjg9PT3u3r3LqlWr+Oijj/jqq694/vnnpZUFRkZGhIWF4ePjw5w5c0hOTsbHx6fOUQRPktomgOp2\nFhwczI0bN7h06RLfffedRhktW7akefPm7N69m7S0NKKioqpcM2jQIAoLC1m+fDkJCQmS00CtuFlb\nWxMeHk5KSgoJCQmsWLGiShSElZUVly9fJi8vj7///lvr7xk6dCjh4eEcOnSImzdv8tNPP3Hq1CmN\nfLOPGl3q41nD2tqanJwcwsPDycjI4MiRI5w+fbpeZVlaWpKQkEBmZqaUdqQ2h1VdqM25ZWlpiUwm\n4+LFi9y+fZvCwsJaxyMoN+YaGhoSFRVFXl6e1O+88MILJCUlSe1LnUddV3kaAkZGRgwcOJCtW7dy\n8eJFadPJvLw8Bg0aVGv7f+ONN/jxxx85cOAAaWlpJCcnExYWJpWv3nzq2rVrJCUlsWrVqiqbqkJ5\n7sijR49y8+ZN9u3bR3R0tJTDXpdv1MrKiqysLBITE7l9+zbFxcVVnuHs7IydnR0rV67k2rVrXLt2\njcDAQNq2bSsiSSmvn/bt27Ns2TIiIyPJzMzkzz//ZNeuXVy9elXrPa1atSI6OprY2FhSU1NZv369\nhpMBtPcLlXkYDvY///yTvXv3kpCQQHZ2NhEREdy6deuB22NpaanGOLpt2zb69esn8g8/IHZ2dowb\nN44DBw4wffp0jh07ViUFor29PQsWLCAtLY1PPvkEHx8fzpw5I/XfHh4ejBw5krCwMGbMmMHixYs5\nf/68RsojwdOJoaEhN2/eZPny5Xz44YcEBQXh5ubGsGHDsLOzY+HChWRlZeHr68usWbPYtm2b5Iy7\ncuUKBw4cYOrUqTRp0gSZTMaUKVNISUnRSLUg+H+sra3p2rUrISEhXL16levXr7Ny5UqMjY3p2bMn\nUB781KhRI7Zt20Z6ejrnzp3j8OHDtZb9MHShvXv3cunSJW7cuEFwcDByuVySSxenSH1Qr4L+7bff\npLlvx44dOXv2rEY+cCjPWX769Gl27tzJ9evXSU1N5dy5c4SGhgLlY6F689Fz586RkZHBtWvX2L9/\nv9b9gUaNGkX//v2lzRefFBYWFhgYGHDo0CEyMjK4ePEiO3fu1LhGm25dHW5ubkRFRfHzzz/To0cP\njcjo2uqwJmoLltNFh3jhhReIjIwkIiKCtLQ0Nm/eXK+0iJaWlsTGxpKTk6PTqrdOnTphYmLCnj17\n6N27d4NJu/o0IdKhCBoEenp6TJ8+nY0bNzJz5kxatmzJmDFj+Prrr4Fy492cOXNYt24ds2fPxtbW\nlpEjR7J8+XJpcqxQKFi8eDHbtm3Dz8+PoqIiLCwsePHFF7VOoAUPjpeXl7QLthpfX98q1ymVyip5\nqGu7B2DXrl0af3ft2pWtW7dKfxsYGDB69GiNzVDVWFlZadwvl8vx9vaWdpxWo948TS6X8+GHH1Yr\nY//+/enfv3+15xsKHh4emJmZERYWxrp162jcuDH29vYMGzYMIyMj5s6dy7p165gzZw42NjZ4eXmx\nbNky6X65XM5HH33EunXrmDVrFvb29owaNYqlS5dK1ygUChYuXEhoaCgLFy5EJpPRpk0b3n33XQC8\nvb1Zu3Ytc+bMQaFQMHLkyCpKwZgxY/j222/x9vZGoVAQFBRU5bd069aN8ePHExYWxubNm7GwsOCd\nd97R2BTzUaNLfTxrdO3alddee41NmzZRVFTEiy++iIeHB+vWratzWUOHDiUoKIgZM2ZQVFTEN998\nw4ABA6Td1cvKyujevbvG5kN1oaJzKzc3l6ZNm+Li4iIZTtTf344dO1izZg29evViypQpNY5HUL5S\nYfz48ezZs4fdu3fToUMHfH196dy5MyNGjGDHjh3cv38fNzc3Bg4cyIULF3SSp6Gg7veDg4O5e/cu\nbdu25ZNPPpHyM9bU/gcOHIhcLicsLIytW7dKmyOpefvtt1m9ejW+vr6Ym5vj5eVFampqFRlGjhzJ\n+fPn2bhxI6ampnh7e0sTUF2+0e7du3P+/HkWL17M3bt3mTx5cpV9J2QyGbNnz2bDhg0sXLgQKDf8\nTpgwocYNmf4pyGQy5s2bJ7Wf/Px8zM3Nad++fbUbD7/xxhtkZmbi5+eHoaEhvXv3xs3NTSPHrLZ+\noTJqB3toaCizZ8+mSZMmdXawGxsbExcXx6FDh7h79y7NmzfnzTff1HnT5OpQKpW0bt2ahQsXcv/+\nfbp3765VTxHUjDbd0N3dXXJ2qXn55Zc1/nZycpLaa2VkMhmvvPIKr7zyykOTU/B4MDc35+OPP672\n/HPPPaeRSqEiSqWS7du3VymvPnrLP4nJkyezadMmli1bRlFREU5OTvj4+EjR1CYmJkybNo3Q0FCO\nHz+OUqnEw8NDa59dkYehC3l5efHtt9+SlpZG69atmTNnjuRoVDtFduzYga+vLyqVCisrq2o3zdUV\n9Sro1NRUaUNvdV7pynthde7cmblz57J3717CwsLQ19fH2tpaQ8+YPHky3333HaGhody6dQsTExPa\ntWtXrZPd09MTgMWLF7NgwYLHlhqlIqampkyZMoXt27dz+PBh2rRpw9tvv60xz69Ot9ZGhw4dUCgU\npKSkVJmH61KHNTF16lR27tzJxo0buXPnDs2bN2fIkCGSjLXpEH369OGvv/4iODgYKDecd+vWjTt3\n7tSlynjrrbcICQnhgw8+oLi4uIp9ozIymYw+ffqwe/fuB9oP7Z+MrOxJJRgVCB4xv//+O1999RUh\nISGPNC+UQCAQCASCp4e33nqLGTNm4Orq+qRFEQg0CAoK4s6dO8ydO/dJiyIQCATPHDExMSxcuJB1\n69aJ+b/gmSUkJIT09HQWLFjwpEVpkIhIcMEzw6+//kqLFi1o3rw5N27cYNOmTXTp0kUMgAKBQCAQ\nCAQCgUAgEAgEggZJQUEBKSkpnDx5kunTpz9pcRoswggueGbIz89n9+7d5ObmYm5ujouLS5VUHAKB\nQKAr3333nbS3QGU6dOiAj4/PY5ZIUB9qWj7r4+NDhw4dHqM0AoFAIBAIBIL6sHbtWsLDw7Wec3Nz\no0ePHo/kueHh4dXmDLe0tGT58uWP5LmC+nH16tUaU61u2bLlMUrz8Fi2bBkJCQn07dsXFxeXJy1O\ng0WkQxEIBAKBQAt///13tZtuGhoaVtmdXfB0kp6eXu05hUIh5a4UCAQCgUAgEDy95Ofnc+/ePa3n\nGjduLG12+rC5d+8e+fn5Ws/p6+tjaWn5SJ4rqB9FRUXk5ORUe75ly5aPURrB04YwggsEAoFAIBAI\nBAKBQCAQCAQCgeCZRe9JCyAQCAQCgUAgEAgEAoFAIBAIBALBo0IYwQUCgUAgEAgEAoFAIBAIBAKB\nQPDMIozgAoFAIBAIBAKBQCAQCAQCgUAgeGYRRnCBQCAQCAQCgUAgEAgEAoFAIBA8s/wfMO8o+glg\nc90AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x116f27cf8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "marital_status has highest gain\n"
     ]
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline \n",
    "import re\n",
    "plt.style.use('ggplot')\n",
    "plt.rcParams.update({'font.size': 14})\n",
    "\n",
    "\n",
    "# Function to find the column in columns to split on\n",
    "def find_best_column(data, target_name, columns, iplot=0):\n",
    "    # data is a dataframe\n",
    "    # target_name is the name of the target variable\n",
    "    # columns is a list of potential columns to split on\n",
    "    information_gains = [calc_information_gain(data, c, target_name) for c in columns]\n",
    "    \n",
    "    # plot data optional\n",
    "    if iplot==1:\n",
    "        plt.figure(figsize=(25,5))\n",
    "        x_pos = np.arange(len(columns))\n",
    "        plt.bar(x_pos, information_gains,align='center', alpha=0.5)\n",
    "        plt.xticks(x_pos, columns)\n",
    "        plt.ylabel('information gains')\n",
    "        plt.show()\n",
    "    \n",
    "    # return column name with highest gain\n",
    "    highest_gain = columns[information_gains.index(max(information_gains))] \n",
    "    return highest_gain\n",
    "\n",
    "# A list of columns to potentially split income with\n",
    "columns = [\"age\", \"workclass\", \"education_num\", \"marital_status\", \"occupation\", \"relationship\", \"race\", \"sex\", \"hours_per_week\", \"native_country\"]\n",
    "\n",
    "income_split = find_best_column(income, 'high_income', columns, iplot=1)\n",
    "print(income_split, \"has highest gain\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Storing the Trees (ID3) \n",
    "\n",
    "Let's build up to making the full id3() function by creating a recursive algorithm.We'll use nested dictionaries to do this. We can represent the root node with a dictionary, and branches with the keys left and right. We'll store the column we're splitting on as the key column, and the median value as the key median. Finally, we can store the label for a leaf as the key label. We'll also number each node as we go along using the number key.\n",
    "\n",
    "Here's what that algorithm looks like in pseudocode:\n",
    "```python\n",
    "def id3(data, target, columns, tree)\n",
    "    1 Create a node for the tree\n",
    "    2 Number the node\n",
    "    3 If all of the values of the target attribute are 1, assign 1 to the label key in tree\n",
    "    4 If all of the values of the target attribute are 0, assign 0 to the label key in tree\n",
    "    5 Using information gain, find A, the column that splits the data best\n",
    "    6 Find the median value in column A\n",
    "    7 Assign the column and median keys in tree\n",
    "    8 Split A into values less than or equal to the median (0), and values above the median (1)\n",
    "    9 For each possible value (0 or 1), vi, of A,\n",
    "    10 Add a new tree branch below Root that corresponds to rows of data where A = vi\n",
    "    11 Let Examples(vi) be the subset of examples that have the value vi for A\n",
    "    12 Create a new key with the name corresponding to the side of the split (0=left, 1=right).  The value of this key should be an empty dictionary.\n",
    "    13 Below this new branch, add the subtree id3(data[A==vi], target, columns, tree[split_side])\n",
    "    14 Return Root\n",
    "```\n",
    "\n",
    "Under this approach, we're now passing the tree dictionary into our id3 function and setting some keys on it. One complexity is in how we're creating the nested dictionary. For the left split, we're adding a key to the tree dictionary that looks like this:\n",
    "\n",
    "tree[\"left\"] = {}\n",
    "\n",
    "For the right side, we're adding:\n",
    "\n",
    "tree[\"right\"] = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Create a dictionary to hold the tree  \n",
    "# It has to be outside of the function so we can access it later\n",
    "tree = {}\n",
    "\n",
    "# This list will let us number the nodes  \n",
    "# It has to be a list so we can access it inside the function\n",
    "nodes = []\n",
    "\n",
    "def id3(data, target, columns, tree):\n",
    "    unique_targets = pd.unique(data[target])\n",
    "    \n",
    "    # Assign the number key to the node dictionary\n",
    "    nodes.append(len(nodes) + 1)\n",
    "    tree[\"number\"] = nodes[-1]\n",
    "\n",
    "    if len(unique_targets) == 1:\n",
    "        # assign \"label\" field to  node dictionary\n",
    "        if unique_targets[0]==1:\n",
    "            tree[\"label\"] = 1\n",
    "        else: \n",
    "            tree[\"label\"] = 0\n",
    "        return\n",
    "    \n",
    "    best_column = find_best_column(data, target, columns)\n",
    "    column_median = data[best_column].median()\n",
    "    \n",
    "    # assign \"column\", \"median\" to node dictionary\n",
    "    tree[\"column\"] = best_column\n",
    "    tree[\"median\"] = column_median\n",
    "    \n",
    "    left_split = data[data[best_column] <= column_median]\n",
    "    right_split = data[data[best_column] > column_median]\n",
    "    split_dict = [[\"left\", left_split], [\"right\", right_split]]\n",
    "    \n",
    "    for name, split in split_dict:\n",
    "        tree[name] = {}\n",
    "        id3(split, target, columns, tree[name])\n",
    "\n",
    "# Create the data set that we used in the example on the last screen\n",
    "data = pd.DataFrame([\n",
    "    [0,20,0],\n",
    "    [0,60,2],\n",
    "    [0,40,1],\n",
    "    [1,25,1],\n",
    "    [1,35,2],\n",
    "    [1,55,1]\n",
    "    ])\n",
    "# Assign column names to the data\n",
    "data.columns = [\"high_income\", \"age\", \"marital_status\"]\n",
    "\n",
    "# Call the function on our data to set the counters properly\n",
    "id3(data, \"high_income\", [\"age\", \"marital_status\"], tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'number': 1, 'column': 'age', 'median': 37.5, 'left': {'number': 2, 'column': 'age', 'median': 25.0, 'left': {'number': 3, 'column': 'age', 'median': 22.5, 'left': {'number': 4, 'label': 0}, 'right': {'number': 5, 'label': 1}}, 'right': {'number': 6, 'label': 1}}, 'right': {'number': 7, 'column': 'age', 'median': 55.0, 'left': {'number': 8, 'column': 'age', 'median': 47.5, 'left': {'number': 9, 'label': 0}, 'right': {'number': 10, 'label': 1}}, 'right': {'number': 11, 'label': 0}}}\n"
     ]
    }
   ],
   "source": [
    "print(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "age > 37.5\n",
      "    age > 25.0\n",
      "        age > 22.5\n",
      "            Leaf: Label 0\n",
      "            Leaf: Label 1\n",
      "        Leaf: Label 1\n",
      "    age > 55.0\n",
      "        age > 47.5\n",
      "            Leaf: Label 0\n",
      "            Leaf: Label 1\n",
      "        Leaf: Label 0\n"
     ]
    }
   ],
   "source": [
    "def print_with_depth(string, depth):\n",
    "    # Add space before a string\n",
    "    prefix = \"    \" * depth\n",
    "    # Print a string, and indent it appropriately\n",
    "    print(\"{0}{1}\".format(prefix, string))\n",
    "    \n",
    "    \n",
    "def print_node(tree, depth):\n",
    "    # Check for the presence of \"label\" in the tree\n",
    "    if \"label\" in tree:\n",
    "        # If found, then this is a leaf, so print it and return\n",
    "        print_with_depth(\"Leaf: Label {0}\".format(tree[\"label\"]), depth)\n",
    "        # This is critical\n",
    "        return\n",
    "    # Print information about what the node is splitting on\n",
    "    print_with_depth(\"{0} > {1}\".format(tree[\"column\"], tree[\"median\"]), depth)\n",
    "    \n",
    "    # Create a list of tree branches\n",
    "    branches = [tree[\"left\"], tree[\"right\"]]\n",
    "        \n",
    "    # recursively call print_node on each branch, increment depth\n",
    "    print_node(branches[0], depth+1)\n",
    "    print_node(branches[1], depth+1)\n",
    "print_node(tree, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The left branch prints out first, then the right branch. Each node prints the criteria on which it was split. \n",
    "\n",
    "Let's say we want to predict the following row:\n",
    "\n",
    "1. Example 1\n",
    "\n",
    "```python \n",
    "age    marital_status\n",
    "50     1\n",
    "```\n",
    "\n",
    "    First, we'd split on age > 37.5 and go to the right. Then, we'd split on age > 55.0 and go to the left. Then, we'd split on age > 47.5 and go to the right. We'd end up predicting a 1 for high_income.\n",
    "    \n",
    "\n",
    "2. Example 2\n",
    "```python \n",
    "age    marital_status\n",
    "20     1\n",
    "```\n",
    "    \n",
    "    First, we'd split on age > 37.5 and go to the left. Then, we'd split on age > 25.0 and go to the left again. Then, we'd split on age > 22.5 and got to left and predict a 0 for high_income.\n",
    "    \n",
    "\n",
    "Making predictions with such a small tree is fairly straightforward, but what if we want to use the entire income dataframe? We wouldn't be able to eyeball predictions; we'd want an automated way to do this instead.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Making Predictions Automatically\n",
    "\n",
    "Let's write a function that makes predictions automatically. All we need to do is follow the split points we've already defined with a new row.\n",
    "\n",
    "Here's the pseudocode:\n",
    "\n",
    "```python\n",
    "def predict(tree, row):\n",
    "    1 Check for the presence of \"label\" in the tree dictionary\n",
    "    2    If found, return tree[\"label\"]\n",
    "    3 Extract tree[\"column\"] and tree[\"median\"]\n",
    "    4 Check whether row[tree[\"column\"]] is less than or equal to tree[\"median\"]\n",
    "    5    If it's less than or equal, call predict(tree[\"left\"], row) and return the result\n",
    "    6    If it's greater, call predict(tree[\"right\"], row) and return the result\n",
    "```\n",
    "\n",
    "The major difference here is that we're returning values. Because we're only calling the function recursively once in each iteration (we only go \"down\" a single branch), we can return a single value up the chain of recursion. This will let us get a value back when we call the function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "def predict(tree, row):\n",
    "    if \"label\" in tree:\n",
    "        return tree[\"label\"]\n",
    "    \n",
    "    column = tree[\"column\"]\n",
    "    median = tree[\"median\"]\n",
    "    # If row[column] is <= median,\n",
    "    # return the result of prediction on left branch of tree\n",
    "    # else right\n",
    "    \n",
    "    if row[column] <= median:\n",
    "        return predict(tree[\"left\"], row)\n",
    "    else:\n",
    "        return predict(tree[\"right\"], row)\n",
    "\n",
    "print(predict(tree, data.iloc[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0    0\n",
      "1    0\n",
      "2    0\n",
      "3    0\n",
      "4    1\n",
      "5    0\n",
      "dtype: int64\n"
     ]
    }
   ],
   "source": [
    "# Making Multiple Predictions using pandas apply method\n",
    "# df.apply(func, axis=0, broadcast=False, raw=False, reduce=None, args=(), **kwds)\n",
    "\n",
    "new_data = pd.DataFrame([\n",
    "    [40,0],\n",
    "    [20,2],\n",
    "    [80,1],\n",
    "    [15,1],\n",
    "    [27,2],\n",
    "    [38,1]\n",
    "    ])\n",
    "# Assign column names to the data\n",
    "new_data.columns = [\"age\", \"marital_status\"]\n",
    "\n",
    "def batch_predict(tree, df):\n",
    "    # Insert your code here\n",
    "    return df.apply(lambda x: predict(tree, x), axis=1)\n",
    "    \n",
    "\n",
    "predictions = batch_predict(tree, new_data)\n",
    "print(predictions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this mission, we learned how to create a full decision tree model, print the results, and use the tree to make predictions. We applied a modified version of the ID3 algorithm on a small data set for clarity.\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}