{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Les tris sur des listes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Mise en place du contexte, objectifs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Listes d'éléments totalement ordonnés"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $L$ une liste comportant donc un nombre fini d'éléments que l'on note $L=[a_0,a_1,\\cdots,a_{n-1}]$ de façon que la liste $L$ comporte exactement $n$ éléments (ou occurrences).\n",
    "\n",
    "On dit que la liste $L$ **a ses éléments totalement ordonnés**, ou bien que la liste $L$ est **totalement ordonnée** si les occurrences $a_k$ de la liste $L$ appartiennent à un ensemble sur lequel on dispose d'une relation d'ordre totale.\n",
    "\n",
    "Par conséquent, tous les éléments de la liste $L$ sont comparables les uns aux autres."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Deux contextes différents de listes totalement ordonnées"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On considèrera par la suite essentiellement deux types de listes totalement ordonnées :\n",
    "    \n",
    "$\\quad$  $\\rhd$ les <u>listes numériques</u> comportant des occurrences de type flottant (**float**) ou entier (**int**). A noter que les listes comportant des complexes sont à exclure. La relation d'ordre totales sur ces occurrences numériques sont la relation habituelle $\\leq$ sur l'ensemble $\\mathbb{R}$ des réels.\n",
    "    \n",
    "$\\quad$    $\\rhd$ les listes comportant des <u>chaînes de caractères</u> (de type **str**). L'ordre total habituel sur ces chaînes est l'ordre lexicographique. A noter que les majuscules sont ordonnées avant les minuscules. Cette relation d'ordre est associée au code ASCII permettant de coder sur un octet 256 symboles alpha-numériques."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objectifs "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'objectif sous-jacent à ce chapitre est double :\n",
    "\n",
    "$\\quad$ $\\longrightarrow$ élaborer des scripts *Python* qui permettent de trier des listes totalement ordonnées -- c'est-à-dire à partir d'une liste $L=[a_0,\\cdots,a_{n-1}]$ d'occurrences totalement ordonnées, de fournire la liste $M=[b_0,\\cdots,b_{n-1}]$ de telle sorte que les occurrences de $L$ et de $M$ sont globalement identiques à ordre près et les occurrences de la liste $M$ sont rangées dans l'ordre croissant : $\\forall k\\in\\lbrace 0,\\cdots,n-2\\rbrace$, $b_k\\leq b_{k+1}$\n",
    "\n",
    "$\\quad$ $\\longrightarrow$ comparer différentes méthodes de tris par le biais de la complexité des algorithmes rencontrés."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Différents tris ... première partie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Le tri par sélection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Principe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A partir d'une liste $L=[a_0,\\cdots,a_{n-1}]$ totalement ordonnée :\n",
    "\n",
    "$\\quad$ $\\bullet$ on sélectionne le plus petit élément de la liste $L$ que l'on place dans une liste temporaire\n",
    "\n",
    "$\\quad$ $\\bullet$ on sélectionne ensuite le plus petit élément de la sous-liste de $L$ dans $a_0$ que l'on place en deuxième position dans la liste temporaire\n",
    "\n",
    "$\\quad$ $\\bullet$ ainsi de suite ...\n",
    "\n",
    "$\\quad$ $\\bullet$ au bout de $(n-1)$ étapes, la liste temporaire est la liste triée."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implémentation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici un script relativement à cet algorithme. Plutôt que d'échanger des éléments de la liste $L$, on choisit de sélectionner les éléments minimaux puis de les stocker dans une liste à part et de les enlever progressivement de la liste de départ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Liste de départ : \n",
      "[4, 0, 7, 10, 9, 10, 7, 10, 9, 6, 8, 5, 10, 7, 10, 3, 1, 7, 4, 10, 8, 1, 6, 9, 10, 9, 4, 1, 0, 5]\n",
      "Liste triée :\n",
      "[0, 0, 1, 1, 1, 3, 4, 4, 4, 5, 5, 6, 6, 7, 7, 7, 7, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10]\n"
     ]
    }
   ],
   "source": [
    "def Tri_Par_Selection(L) :\n",
    "    \"\"\" trie par la méthode de sélection \"\"\"\n",
    "    Liste_Temp=L.copy()\n",
    "    Liste_A_Remplir=[]\n",
    "    while Liste_Temp!=[] :\n",
    "        Minimum=Liste_Temp[0]\n",
    "        for x in Liste_Temp[1:] :\n",
    "            if x<Minimum :\n",
    "                Minimum=x\n",
    "        Liste_A_Remplir.append(Minimum)\n",
    "        Liste_Temp.remove(Minimum)\n",
    "    return Liste_A_Remplir\n",
    "\n",
    "### Tests ###\n",
    "\n",
    "from pylab import *\n",
    "from random import *\n",
    "\n",
    "L=[randint(0,10) for k in range(30)]\n",
    "print(\"Liste de départ : \")\n",
    "print(L)\n",
    "print(\"Liste triée :\")\n",
    "print(Tri_Par_Selection(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Complexité"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La complexité se calcule en fonction de la taille de l'entrée, c'est-à-dire ici l'entier $n$ donnant la longueur de la liste $L$ à trier.\n",
    "\n",
    "Dans le script, à chaque étape dans la boucle **while**, la liste $Liste$_$Temp$ perd toujours un élément, étant partie de la liste $L$ de départ. Ainsi, la boucle **while** est traversée $n$ fois. Ensuite, à chaque exécution à l'intérieur de la boucle **while**, il y a ${\\cal O}(p)$ opérations, avec $p$ la longueur de la liste $Liste$_$Temp$.\n",
    "\n",
    "On en déduit que la complexité est en : $\\displaystyle \\sum_{p=1}^n {\\cal O}(p)={\\cal O}\\left(\\sum_{p=1}^n p\\right)={\\cal O}\\left(\\frac{n(n+1)}{2}\\right)={\\cal O}(n^2)$.\n",
    "\n",
    "On a une complexité quadratique !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Le tri par insertion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Principe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A partir d'une liste $L=[a_0,\\cdots,a_{n-1}]$ totalement ordonnée :\n",
    "\n",
    "$\\quad$ $\\bullet$ on parcourt la liste du début vers la fin\n",
    "\n",
    "$\\quad$ $\\bullet$ à chaque élément rencontré, on l'ordre parmi les éléments déjà rencontrés\n",
    "\n",
    "$\\quad$ $\\bullet$ ainsi de suite ...\n",
    "\n",
    "$\\quad$ $\\bullet$ une fois la liste $L$ totalement parcourue, la liste temporaire est la liste $L$ triée."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implémentation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici un script Python possible par itérations :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Liste de départ : \n",
      "[1, 5, 9, 3, 6, 10, 1, 8, 10, 8, 3, 2, 1, 1, 0, 2, 1, 2, 0, 0, 8, 10, 9, 8, 3, 5, 10, 7, 8, 7]\n",
      "Liste triée :\n",
      "[0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 5, 5, 6, 7, 7, 8, 8, 8, 8, 8, 9, 9, 10, 10, 10, 10]\n"
     ]
    }
   ],
   "source": [
    "def Tri_Par_Insertion(L) :\n",
    "    Liste_A_Remplir=[]\n",
    "    for x in L :\n",
    "        bonne_place=0\n",
    "        while bonne_place<len(Liste_A_Remplir) and Liste_A_Remplir[bonne_place]<x :\n",
    "            bonne_place+=1\n",
    "        # ici, bonne_place indique l'endroit oiù placer x dans Liste_A_Remplir\n",
    "        Liste_A_Remplir=Liste_A_Remplir[:bonne_place]+[x]+Liste_A_Remplir[bonne_place:]\n",
    "    return Liste_A_Remplir\n",
    "\n",
    "\n",
    "from random import *\n",
    "\n",
    "L=[randint(0,10) for k in range(30)]\n",
    "print(\"Liste de départ : \")\n",
    "print(L)\n",
    "print(\"Liste triée :\")\n",
    "print(Tri_Par_Insertion(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Complexité"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le pire des cas est lorsqu'il faut parcourir toute la liste $L$ (ce qui se produit à chaque fois) et qu'en plus, à chaque fois, il faut parcourir toute la liste en cours de traitement (c'est le cas lorsque la liste $L$ est déjà triée...) On a donc une complexité en $\\displaystyle {\\cal O}\\left(\\sum_{k=1}^n k\\right)={\\cal O}(n^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Le tri à bulles "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Principe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans un verre d'eau, les bulles ont tendance à remonter à la surface. Pour le tri à bulles, c'est pareil ! Ce sont non pas des bulles, mais des éléments les plus petits (ou *légers*) qui remonteront si l'on décrit les occurrences verticalement.\n",
    "\n",
    "Etant donnée une liste $L$ totalement ordonnée, \n",
    "\n",
    "$\\quad$ $\\rhd$ tant qu'il existe dans la liste $L$ deux éléments consécutifs $L[k]$ et $L[k+1]$ tels que $L[k]>L[k+1]$, alors on échange les termes $L[k]$ et $L[k+1]$ ;\n",
    "\n",
    "$\\quad$ $\\rhd$ lorsqu'il n'y a plus de changements à produire sur la liste, c'est que celle-ci est triée comme il faut."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implémentation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Liste de départ : \n",
      "[7, 8, 7, 9, 7, 8, 0, 2, 2, 4, 8, 5, 10, 6, 5, 4, 4, 7, 1, 6, 4, 10, 6, 5, 0, 8, 10, 1, 3, 10]\n",
      "Liste triée :\n",
      "[0, 0, 1, 1, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 10, 10, 10, 10]\n"
     ]
    }
   ],
   "source": [
    "def Tri_A_Bulles(L) :\n",
    "    \"\"\" trie la liste L par le tri à bulles \"\"\"\n",
    "    Test_Echange=True\n",
    "    Liste_Temp=L.copy()  \n",
    "    while Test_Echange :  \n",
    "        Test_Echange=False\n",
    "        for k in range(len(L)-1) :\n",
    "            if Liste_Temp[k]>Liste_Temp[k+1] :\n",
    "                Liste_Temp[k],Liste_Temp[k+1]=Liste_Temp[k+1],Liste_Temp[k]\n",
    "                Test_Echange=True\n",
    "    return Liste_Temp\n",
    "\n",
    "from random import *\n",
    "\n",
    "L=[randint(0,10) for k in range(30)]\n",
    "print(\"Liste de départ : \")\n",
    "print(L)\n",
    "print(\"Liste triée :\")\n",
    "print(Tri_A_Bulles(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Complexité"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculons maintenant la complexité de cet algorithme, en fonction de la longueur $n$ de la liste d'entrée $L$.\n",
    "\n",
    "Pour estimer un ordre de grandeur du nombre d'opérations élémentaires à e\u001bffectuer, il faut envisager tous les\n",
    "cas, en particulier les cas les plus défavorables pour l'algorithme.\n",
    "\n",
    "- dans le cas général, après $n$ évaluations de la condition $Test$_$Echange$ dans la boucle **while**, on est sûr que la liste sera bien\n",
    "ordonnée. Après la première exécution de la boucle **for**, la liste $Liste$_$Temp$ présente son terme maximal en dernière position. Après la deuxième exécution de la boucle **for**, la liste $Liste$_$Temp$ présente ses deux termes maximaux en dernières positions et placés dans le bon ordre. En réitérant le raisonnement, au bout de $n$ exécutions de la boucle **for**, la liste $Liste$_$Temp$ est bien ordonnée.\n",
    "    \n",
    "- chaque boucle **for** met en jeu ${\\cal O}(n)$ opérations élémentaires car on parcourt à chaque fois toute la liste $Liste$_$Temp$.\n",
    "    \n",
    "La complextié de l'algorithme du tri à bulles est quadratique en ${\\cal O}(n^2)$ et ceci se produit effectivement lors du cas le plus défavorable où les $n-1$ premiers termes de liste $L$ sont bien ordonnés et que le dernier terme est strictement inférieur au premier. Dans ce cas, à chaque boucle **for**, il y a un seul échange et il faut effectuer $n-1$ fois la boucle **for** pour ramener le dernier terme de $L$ au début de $Liste$_$Temp$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Arbres binaires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Définitions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On rappelle qu'un **graphe orienté** est la donnée d'un couple $(S,{\\cal A})$, où $S$ est un ensemble et ${\\cal A}$ est une partie de l'ensemble couples $(r,s)\\in S^2$, avec $r\\neq s$. \n",
    "\n",
    "Les éléments $s$ de l'ensemble $S$ sont appelés **sommets** et les éléments $(r,s)$ de ${\\cal A}$ sont appelés **arètes orientées**.\n",
    "\n",
    "Un graphe $G=(S,{\\cal A})$ peut donc se représenter en identifiant chaque sommet à un point et en reliant deux sommets différents par une ligne ou une courbe orientée de la première composant du couple vers la seconde.\n",
    "\n",
    "Dans la suite, on dit que le sommet $r$ est relié au sommet $s$ si $(r,s)\\in {\\cal A}$. On remarquera que $r$ peut être relié à $s$ mais que $s$ peut ne pas être relié à $r$.\n",
    "\n",
    "Un **arbre** est un graphe ne possédant aucun **cycle**, c'est-à-dire que l'on ne peut trouver d'éléments $s_1,\\cdots,s_n$ tous différents avec $n\\geq 3$ tels que pour tout $k$ entre $1$ et $n-1$, le sommet $s_k$ est relié au sommet $s_{k+1}$ et le sommet $s_n$ est relié au sommet $s_1$.\n",
    "\n",
    "On dit qu'un arbre est **binaire** si chaque sommet est relié à soit aucun soit deux autres sommets. Les sommets reliés à aucun autre sont appelés les **feuilles**, alors que les sommets $s$ pour lesquels il n'existe pas de sommets $r$ reliés à $s$ sont appelées les **racines**.\n",
    "\n",
    "On dit qu'un arbre est **connexe**, si on peut passer de n'importe quel sommet $r$ à n'importe quel autre sommet $s$ en transitant par une chaîne $(t_0,\\cdots,t_p)$ avec $t_0=r$, $t_p=s$ et pour tout $k\\in \\lbrace 0,\\cdots,p-1\\rbrace$, $(t_k,t_{k+1})\\in {\\cal A}$ ou $(t_{k+1},t_{k})\\in {\\cal A}$.\n",
    "\n",
    "Un arbre binaire connexe possède donc une seule racine (sinon, il serait impossible de relier deux racines par une chaîne de sommets). De chaque sommet $s$ qui n'est pas une feuille descendent deux arêtes vers deux sommets $s_1$ et $s_2$  : les sommets $s_1$ et $s_2$ sont appelés **fils de $s$**, alors que le sommet $s$ est appelé **père des sommets $s_1$ et $s_2$**.\n",
    "\n",
    "On dit qu'un arbre binaire connexe est **complet** si toutes les feuilles appartiennent à au maximum deux générations différentes, c'est-à-dire que la profondeur de chaque feuille (distance ou nombre d'arètes séparant la racine de l'arbre binaire connexe de la feuille considérée ne diffère d'une autre profondeur que d'une unité au maximum.\n",
    "\n",
    "Voici une petite application graphique demandant de rentrer le nombre $n$ de sommets et l'interface dessine un arbre binaire connexe complet comportant $n$ sommets où les feuilles de la dernière génération sont placées à gauche :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from tkinter import *\n",
    "\n",
    "absc_centre=400  # recadrage du noeud initial en abscisse\n",
    "\n",
    "ord_depart=40  # recadrage du noeud initial en ordonnée\n",
    "\n",
    "unite_larg=150\n",
    "\n",
    "Temps_Attente=50 \n",
    "\n",
    "def Generation(k) : \n",
    "    \"\"\"création de la liste des noeuds de la génération k \"\"\"\n",
    "    if k==0 :\n",
    "        return [absc_centre]\n",
    "    else :\n",
    "        return Tri_A_Bulles([x-unite_larg/2**(k-1) for x in Generation(k-1)] + [x+unite_larg/2**(k-1) for x in Generation(k-1)])\n",
    "\n",
    "def Numero_Gen(n) :\n",
    "    \"\"\" renvoie le numéro de la génération à laquelle appartient n \"\"\"\n",
    "    k=0\n",
    "    while 2**(k+1)<=n :\n",
    "        k+=1\n",
    "    return k\n",
    "\n",
    "def Place(n) :\n",
    "    global unite_haut\n",
    "    k=Numero_Gen(n)\n",
    "    \n",
    "    return [Generation(k)[n-2**k],ord_depart+k*unite_haut]\n",
    "    \n",
    "\n",
    "    \n",
    "def dessin_arbre() :\n",
    "    \"\"\" dessine l'arbre binaire complet à n sommets \"\"\"\n",
    "    global n,unite_haut\n",
    "    canevas.delete(ALL)\n",
    "    n=Nbre.get() # n est une chaîne de caractères\n",
    "    n=int(eval(n)) # n est maintenant un entier\n",
    "    unite_haut=350/(Numero_Gen(n)+1)\n",
    "    Liste_Noeuds=list(range(1,n+1))\n",
    "    while len(Liste_Noeuds)>0 :\n",
    "        Noeud=Liste_Noeuds[0]\n",
    "        if 2*Noeud+1<=n :\n",
    "            fenetre.after(Temps_Attente)\n",
    "            canevas.create_line(Place(Noeud)[0],Place(Noeud)[1],Place(2*Noeud)[0],Place(2*Noeud)[1],fill=\"magenta\")\n",
    "            canevas.create_line(Place(Noeud)[0],Place(Noeud)[1],Place(2*Noeud+1)[0],Place(2*Noeud+1)[1],fill=\"magenta\")\n",
    "            fenetre.update()\n",
    "        if 2*Noeud==n :\n",
    "            fenetre.after(Temps_Attente)\n",
    "            canevas.create_line(Place(Noeud)[0],Place(Noeud)[1],Place(2*Noeud)[0],Place(2*Noeud)[1],fill=\"magenta\")\n",
    "            fenetre.update()\n",
    "        fenetre.after(Temps_Attente)\n",
    "        canevas.create_text(Place(Noeud)[0],Place(Noeud)[1],text=str(Noeud),font=\"Arial 12\")\n",
    "        fenetre.update()\n",
    "        Liste_Noeuds.remove(Noeud)    \n",
    "################# Gestion de l'interface graphique ###################\n",
    "fenetre=Tk()\n",
    "\n",
    "\n",
    "titre=Label(fenetre,text=\"Construction d'un arbre binaire connexe complet\",\n",
    "font='Arial 25',fg='red')\n",
    "titre.pack() # mise en place du titre\n",
    "\n",
    "\n",
    "canevas=Canvas(fenetre,width=800,height=400,bg=\"#FFFFCC\") # code couleur en hexadécimal\n",
    "canevas.pack() \n",
    "\n",
    "\n",
    "\n",
    "Texte=Label(fenetre,text=\"Nombre de sommets de l'arbre :\",font='Arial 12',fg=\"blue\")\n",
    "Texte.pack(side=LEFT)\n",
    "\n",
    "Nbre=Entry(fenetre)\n",
    "Nbre.pack(side=LEFT)\n",
    "\n",
    "bouton_quitter = Button(fenetre, text=\"Quitter\", command=fenetre.quit)\n",
    "bouton_quitter.pack(side=RIGHT) # mise en place du bouton \"Quitter\"\n",
    "\n",
    "\n",
    "bouton_tracer_arbre = Button(fenetre, text=\"Tracer l'arbre binaire\", command=dessin_arbre)\n",
    "bouton_tracer_arbre.pack(side=RIGHT) # mise en place du bouton \"traçage \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "fenetre.mainloop() # affichage \n",
    "fenetre.destroy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour accéder maintenant à des tris plus élaborés et surtout plus efficaces, nous avons besoin de quelques rudiments sur les graphes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Le tri fusion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Principe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Etant donnée une liste $L$ totalement ordonnée, on va créer un arbre binaire qui va ensuite se refermer sur lui-même pour aboutir à la liste triée :\n",
    "\n",
    "$\\quad$ $\\rhd$ la racine de l'arbre binaire est la liste $L$\n",
    "\n",
    "$\\quad$ $\\rhd$ si $M$ est un noeud de cet arbre, le noeud $M$ admet deux fils qui sont obtenus en scindant la liste $M$ en deux morceaux en son milieu\n",
    "\n",
    "$\\quad$ $\\rhd$ on poursuit le processus de scission, jusqu'à obtenir des noeuds égaux à des listes ne comportant au maximum qu'un seul élément (ou bien on a des listes vides)\n",
    "\n",
    "$\\quad$ $\\rhd$ on dispose donc d'un arbre binaire, après ces scissions\n",
    "\n",
    "On referme alors l'arbre de la façon suivante :\n",
    "\n",
    "$\\quad$ $\\bullet$ à partir de deux fils adjacents $M$ et $N$, on crée le parent $P$ en fusionnant la liste $M$ dans la liste $N$ par un procédé d'insertion : \n",
    "\n",
    " $\\qquad$ $\\longrightarrow$  on parcourt les éléments de $M$ et on l'insère à la bonne place dans $N$ de telle sorte d'avoir des termes croissants\n",
    "\n",
    " $\\qquad$ $\\longrightarrow$ on obtient alors à partir de deux sous-listes $M$ et $N$ convenablement triées, une liste $P$ encore correctement triée\n",
    "\n",
    "$\\quad$  $\\bullet$ on recommence le processus de fusion autant de fois que nécessaire pour obtenir une génération à un seul élément $L'$\n",
    "\n",
    "$\\quad$ $\\rhd$ la liste $L'$ est la liste triée à partir de la liste $L$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici une petite animation formalisant le tri par fusion en terme de graphes binaires montant et descendant :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from tkinter import *\n",
    "\n",
    "######### Programme pour calculer les tracés sur le canevas ##########\n",
    "\n",
    "def play_S(): \n",
    "    \"\"\"dessine la génération suivante pour les scissions\"\"\"\n",
    "    global n,bouton_tracer_F,absc_centre,ord_depart,unite_larg,unite_haut\n",
    "    Nombre=7 # nombre de générations de scissions à tracer \n",
    "\n",
    "    \n",
    "    \n",
    "    absc_centre=250  # recadrage du noeud initial en abscisse\n",
    "    \n",
    "    ord_depart=30  # recadrage du noeud initial en ordonnée\n",
    "    \n",
    "    unite_larg=100\n",
    "    \n",
    "    \n",
    "\n",
    "    n=saisie.get()\n",
    "    n=int(n)\n",
    "    unite_haut=200/n\n",
    "    bouton_tracer_S.destroy()\n",
    "    bouton_tracer_F = Button(fenetre, text=\"Tracer les fusions\", command= play_F)\n",
    "    bouton_tracer_F.pack(side=RIGHT) # mise en place du bouton \"traçage de la seconde partie\n",
    "    \n",
    "    for Numero_Gen in range(n) :\n",
    "        fenetre.update()\n",
    "        tracer_S(Numero_Gen)\n",
    "        canevas.after(500)\n",
    "        \n",
    "def play_F(): \n",
    "    \"\"\"dessine la génération suivante pour les scissions\"\"\"\n",
    "    global n\n",
    "    bouton_tracer_F.destroy()\n",
    "    for Numero_Gen in range(n) :\n",
    "        fenetre.update()\n",
    "        tracer_F(Numero_Gen)\n",
    "        canevas.after(500)\n",
    "        \n",
    "def Liste_S(k) : \n",
    "    \"\"\"création de la liste des noeuds de la génération k pour les scissions\"\"\"\n",
    "    if k==0 :\n",
    "        return [absc_centre]\n",
    "    else :\n",
    "        return [x-unite_larg/2**(k-1) for x in Liste_S(k-1)] + [x+unite_larg/2**(k-1) for x in Liste_S(k-1)]\n",
    "\n",
    "\n",
    "#print(Liste_S(2))  # teste ok\n",
    "\n",
    "\n",
    "\n",
    "def tracer_S(k):\n",
    "    for x in Liste_S(k) :\n",
    "        x1=x-unite_larg/2**k\n",
    "        x2=x+unite_larg/2**k\n",
    "        y1=ord_depart+k*unite_haut\n",
    "        y2=ord_depart+(k+1)*unite_haut\n",
    "        \n",
    "        canevas.create_line(x,y1,x1,y2,fill=\"red\")\n",
    "        canevas.create_line(x,y1,x2,y2,fill=\"magenta\")\n",
    "\n",
    "\n",
    "def tracer_F(k):\n",
    "    Liste=Liste_S(n-k)\n",
    "    Liste.sort() # on réordonne les éléments \n",
    "    for i in range(len(Liste)//2) :\n",
    "        x1=Liste[2*i]\n",
    "        x2=Liste[2*i+1]\n",
    "        x=(x1+x2)/2  # le milieu\n",
    "        decalage=ord_depart+n*unite_haut\n",
    "        y1=decalage+k*unite_haut\n",
    "        y2=decalage+(k+1)*unite_haut\n",
    "        canevas.create_line(x1,y1,x,y2,fill=\"#9966FF\")\n",
    "        canevas.create_line(x2,y1,x,y2,fill=\"#99CC33\")\n",
    "\n",
    "\n",
    "  \n",
    "\n",
    "################# Gestion de l'interface graphique ###################\n",
    "fenetre=Tk()\n",
    "#fenetre.geometry(\"400x400\") # définition de la fenêtre\n",
    "\n",
    "titre=Label(fenetre,text=\"Animation du graphe lié au tri par fusion\",font=\"Arial 16 bold\",fg=\"red\")\n",
    "titre.pack() # mise en place du titre\n",
    "\n",
    "\n",
    "canevas=Canvas(fenetre,width=500,height=450,bg=\"#FFFFCC\") # code couleur en hexadécimal\n",
    "canevas.pack() # mise en place du canevas où va se calculer le tracé du graphe\n",
    "\n",
    "\n",
    "\n",
    "saisie=Entry()\n",
    "saisie.pack(side=RIGHT)\n",
    "\n",
    "\n",
    "\n",
    "zone_De_Texte=Label(fenetre,text=\"Rentrer le nombre de scissions à effectuer : \")\n",
    "zone_De_Texte.pack(side=RIGHT)\n",
    "\n",
    "\n",
    "bouton_quitter = Button(fenetre, text=\"Quitter\", command=fenetre.quit)\n",
    "bouton_quitter.pack(side=LEFT) # mise en place du bouton \"Quitter\"\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "bouton_tracer_S = Button(fenetre, text=\"Tracer les scissions\", command= play_S)\n",
    "bouton_tracer_S.pack(side=RIGHT) # mise en place du bouton \"traçage de la première partie\n",
    "\n",
    "fenetre.mainloop() # affichage de la fenêtre graphique\n",
    "fenetre.destroy()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implémentation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Liste de départ : \n",
      "[5, 3, 3, 2, 0, 0, 1, 2, 5, 2, 2, 2, 7, 0, 9, 9, 3, 0, 1, 1, 6, 8, 9, 9, 8, 6, 6, 7, 5, 1]\n",
      "Liste triée :\n",
      "[0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 5, 5, 5, 6, 6, 6, 7, 7, 8, 8, 9, 9, 9, 9]\n"
     ]
    }
   ],
   "source": [
    "def scission_Liste(L) :  \n",
    "    \"\"\"définit la liste comportant les deux fils de L dans l'arbre binaire initial\"\"\"\n",
    "    p=(len(L)+1)//2\n",
    "    return [L[:p],L[p:]]\n",
    "\n",
    "def fusion_Listes(M,N) :  \n",
    "    \"\"\"définit la liste fils des deux listes M et N dans l'arbre binaire rétrécissant final\"\"\"\n",
    "    i,liste_A_Remplir=0,[]\n",
    "    \n",
    "    if N==[] :\n",
    "        return M\n",
    "    else :\n",
    "        if M==[] : \n",
    "            return N\n",
    "        else :\n",
    "            fin_M=False  # lors de la fusion, on n'est pas encore à la fin de la liste M\n",
    "        \n",
    "            for y in N :\n",
    "                if not(fin_M) :\n",
    "                    while M[i]<y :\n",
    "                        liste_A_Remplir.append(M[i]) # on commence la fusion de M dans N\n",
    "                        i=i+1\n",
    "                        if i==len(M) :\n",
    "                            fin_M=True\n",
    "                            break\n",
    "                liste_A_Remplir.append(y) # on insère maintenant l'élément de N\n",
    "            if not(fin_M) :  # on est arrivé au bout de la liste N mais pas de la liste M\n",
    "                liste_A_Remplir.extend(M[i:])  # on insère finalement les derniers éléments de M\n",
    "            return liste_A_Remplir\n",
    "\n",
    "\n",
    "def successeur_Scission(liste_De_Listes) :  \n",
    "    \"\"\"calcule la liste des noeuds de la génération suivante, dans la première partie de l'arbre\"\"\"\n",
    "    arbre_A_Remplir=[]\n",
    "    for L in liste_De_Listes :\n",
    "        arbre_A_Remplir.append(scission_Liste(L)[0])\n",
    "        arbre_A_Remplir.append(scission_Liste(L)[1])\n",
    "    return arbre_A_Remplir\n",
    "\n",
    "\n",
    "def successeur_Fusion(liste_De_Listes) :  \n",
    "    \"\"\"calcule la liste des noeuds de la génération suivante, dans la seconde partie de l'arbre\"\"\"\n",
    "    arbre_A_Remplir,p=[],len(liste_De_Listes)//2\n",
    "    for i in range(p) :\n",
    "        arbre_A_Remplir.append(fusion_Listes(liste_De_Listes[2*i],liste_De_Listes[2*i+1]))\n",
    "    return arbre_A_Remplir\n",
    "\n",
    "\n",
    "\n",
    "def nombre_De_Scissions(L) :   \n",
    "    \"\"\"calcule le nombre de générations de la première partie de l'arbre (et donc de la seconde partie de l'arbre\"\"\"\n",
    "    n,k=len(L),0\n",
    "    while 2**k<n :\n",
    "        k+=1\n",
    "    return k\n",
    "\n",
    "\n",
    "def Tri_Fusion(L) :\n",
    "    noeud_Arbre,k=[L],nombre_De_Scissions(L)\n",
    "    for j in range(k) :\n",
    "        noeud_Arbre=successeur_Scission(noeud_Arbre)  \n",
    "        # parcours dans la première partie du graphe\n",
    "    for j in range(k) :\n",
    "        noeud_Arbre=successeur_Fusion(noeud_Arbre)  \n",
    "        # parcours dans la seconde partie du graphe\n",
    "    return  noeud_Arbre[0]\n",
    "\n",
    "\n",
    "L=[randint(0,10) for k in range(30)]\n",
    "print(\"Liste de départ : \")\n",
    "print(L)\n",
    "print(\"Liste triée :\")\n",
    "print(Tri_Fusion(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut également formuler un script de tri fusion de manière récursive, sûrement plus facile à lire :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\n",
    "def Fusion(A,B) :\n",
    "    if A==[] :\n",
    "        return B\n",
    "    elif B==[] :\n",
    "        return A\n",
    "    else :\n",
    "        a,b=A[-1],B[-1]\n",
    "        if a<b :\n",
    "            return Fusion(A,B[:-1])+[b]\n",
    "        else :\n",
    "            return Fusion(A[:-1],B)+[a]\n",
    "    \n",
    "\n",
    "    \n",
    "def Tri_Fusion_Rec(L) :\n",
    "    if len(L)<=1 :\n",
    "        return L\n",
    "    else :\n",
    "        p=len(L)//2\n",
    "        return Fusion(Tri_Fusion_Rec(L[:p]),Tri_Fusion_Rec(L[p:]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Liste de départ : \n",
      "[9, 2, 5, 9, 9, 7, 2, 4, 5, 10, 3, 5, 7, 7, 10, 2, 3, 9, 0, 7, 3, 6, 0, 10, 1, 2, 1, 2, 7, 9]\n",
      "Liste triée :\n",
      "[0, 0, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 7, 7, 7, 7, 9, 9, 9, 9, 9, 10, 10, 10]\n"
     ]
    }
   ],
   "source": [
    "L=[randint(0,10) for k in range(30)]\n",
    "print(\"Liste de départ : \")\n",
    "print(L)\n",
    "print(\"Liste triée :\")\n",
    "print(Tri_Fusion_Rec(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Complexité"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La première remarque importante est que dans un arbre binaire connexe complet possédant $N$ sommets, il y a moins de $\\log_2(N)$ générations différentes, car le nombre de générations est égal au plus grand entier $k$ tel que $2^k\\leq N$, puis $\\displaystyle k=\\left[\\frac{\\ln N}{\\ln 2}\\right]$, avec $[~\\cdot ~]$ la partie entière. \n",
    "\n",
    "Calculons maintenant la complexité de cet algorithme de tri par fusion.\n",
    "\n",
    "L'appel de la procédure **scission_Liste(L)** coûte ${\\cal O}(longueur(L))$ opérations élémentaires.\n",
    "\n",
    "L'appel de la procédure **fusion_Liste(M,L)** coûte ${\\cal O}(longueur(M)+longueur(N))$ opérations élémentaires, car les listes $M$ et $N$ sont parcourues une seule fois globalement, faisant intervenir un nombre fini et borné d'opérations élémentaires à chaque fois.\n",
    "\n",
    "La première partie du graphe fait intervenir $k={\\cal O}(\\log(n))$ opérations de scissions. \n",
    "\n",
    "La seconde partie du graphe fera également intervenir $k={\\cal O}(\\log(n))$ fusions.\n",
    "\n",
    "Le nombre d'opérations élémentaires pour aboutir à la génération de sous-listes de longueurs inférieures ou égales à 1 est en ${\\cal O}(\\log(n))\\cdot {\\cal O}(n)={\\cal O}(n\\cdot \\log(n))$.\n",
    "Le nombre d'opérations élémentaires pour effectuer toutes les fusions sont en ${\\cal O}(n\\cdot \\log(n))$.\n",
    "\n",
    "Le coût en ${\\cal O}(\\log(n))$ dans le calcul du nombre de générations dans le graphe ne change pas le calcul global en terme de complexité.\n",
    "\n",
    "Au final, l'algorithme de tri par fusion est en ${\\cal O}(n\\cdot \\log(n))$. : il est meilleur que le tri à bulles."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Le tri Maximier ou le tri par tas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Définition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il y a les pommiers qui produisent des pommes, il y a des cerisiers qui produisent des cerises, il y a des bananiers qui produisent des bananes, et puis il y a des **maximiers** qui produisent des maximums.\n",
    "\n",
    "On appelle **maximier**, un arbre binaire connexe et complet tel que la valeur associée à chaque noeud est toujours supérieure ou égale à la valeur de ses fils. On en déduit que dans n'importe quel maximier, la valeur maximale se trouve à la racine de l'arbre.\n",
    "\n",
    "On peut remarquer que n'importe quel sous-arbre d'un maximier est encore un maximier. Au lieu de maximier, on parle aussi de **tas**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Principe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Etant donnée une liste $L$, le tri par maximier se déroule en deux étapes :\n",
    "    \n",
    "$\\quad$ $\\rhd$ <u>la **plantation du maximier**</u> : on crée à partir des occurrences de la liste $L$, une liste associée à un arbre maximier. Pour cela, on insère successivement les occurrences de la liste $L$, puis on met au bon endroit cet élément dans l'arbre naissant [principe de **percolation**]\n",
    "\n",
    "$\\quad$ $\\rhd$ une fois le maximier $M$ construit à partir de $L$, on procède à la **cueillette** :\n",
    "\n",
    "$\\qquad$ $\\longrightarrow$ on met dans une liste  $L'$ le fruit du maximier (c'est-à-dire sa valeur maximale), en remplissant $L'$ par la gauche\n",
    "\n",
    "$\\qquad$ $\\longrightarrow$ une fois le fruit prélevé (on enlève la racine de $M$), la racine est remplacée par le fils le plus grand, lequel est remplacé par son fils le plus grand, ainsi de suite\n",
    "\n",
    "$\\qquad$ $\\longrightarrow$ la dernière feuille (la feuille la plus à droite de la dernière génération de l'arbre maximier $M$) prend alors la dernière place occupée par les permutations de l'étape précédente, puis on remet à jour le maximier pour faire éventuellement graviter cette dernière feuille au bon endroit dans l'arbre (principe de **percolation**)\n",
    "\n",
    "$\\quad$ $\\rhd$ on poursuit le processus jusqu'à vider le maximier de tous ses fruits\n",
    "\n",
    "$\\rhd$ la liste $L'$ ainsi construite est la liste triée à partir de $L$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implémentation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Liste de départ : \n",
      "[6, 9, 9, 6, 0, 0, 0, 10, 2, 9, 0, 10, 8, 5, 5, 9, 10, 6, 8, 7, 4, 3, 9, 3, 4, 1, 2, 8, 2, 7]\n",
      "Liste triée :\n",
      "[0, 0, 0, 0, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10]\n"
     ]
    }
   ],
   "source": [
    "def Pousse_Maximier(Arbre,Feuille,Place) :\n",
    "    \"\"\" met à jour un maximier Arbre en insérant Feuille à l'index [Place] \"\"\"\n",
    "    Arbre_Temp=Arbre.copy()\n",
    "    n=len(Arbre)\n",
    "    if Place==n :\n",
    "        Arbre_Temp.append(Feuille) # ajout de la nouvelle feuille\n",
    "    else :\n",
    "        Arbre_Temp[Place]=Feuille # écrasement le l'ancienne feuille avec la nouvelle \n",
    "    Test_Modif=True\n",
    "    while Test_Modif and Place>0 :\n",
    "        Test_Modif=False\n",
    "        Noeud_Pere=(Place-1)//2 # index du noeud parent dans le graphe associé\n",
    "        if Arbre_Temp[Noeud_Pere]<Arbre_Temp[Place] :\n",
    "            Arbre_Temp[Noeud_Pere],Arbre_Temp[Place]=Arbre_Temp[Place],Arbre_Temp[Noeud_Pere]\n",
    "            Place=Noeud_Pere\n",
    "            Test_Modif=True # met en mémoire une modification de l'arbre\n",
    "    return Arbre_Temp\n",
    "\n",
    "\n",
    "def Plantation_Maximier(L) :\n",
    "    \"\"\" on plante le maximier avec les \"fruits\" de la liste L \"\"\"\n",
    "    Arbre_Temp=[]\n",
    "    for k in range(len(L)) :\n",
    "        Arbre_Temp=Pousse_Maximier(Arbre_Temp,L[k],k)\n",
    "    return Arbre_Temp\n",
    "\n",
    "def Cueillette(Arbre) :\n",
    "    \"\"\" renvoie le nouvel Arbre maximier une fois la racine cueillie \"\"\"\n",
    "    k=len(Arbre)-1\n",
    "    if k==0 :\n",
    "        return []\n",
    "    else :\n",
    "        Arbre_Temp=Arbre.copy()\n",
    "        Place=0 # index du noeud à remplir\n",
    "        while 2*Place+2 <= k  : # tant que le noeud-fils droit de l'index [Place] est strictement avant l'index [k]\n",
    "            Noeud_Fils=2*Place+1\n",
    "            if Arbre_Temp[Noeud_Fils]>Arbre_Temp[Noeud_Fils+1] : # noeud-fils gauche meilleur que noeud-fils droit\n",
    "                Place_Fils=Noeud_Fils\n",
    "            else :\n",
    "                Place_Fils=Noeud_Fils+1\n",
    "            Arbre_Temp[Place]=Arbre_Temp[Place_Fils] # le meilleur noeud-fils est transféré dans le noeud à remplir\n",
    "            Place=Place_Fils\n",
    "        # Place est l'index du dernier transfert de noeud\n",
    "        if Place==k :\n",
    "            return Arbre_Temp[:-1]\n",
    "        else :\n",
    "            return Pousse_Maximier(Arbre_Temp[:-1],Arbre_Temp[-1],Place)\n",
    " \n",
    "\n",
    "    \n",
    "def Tri_Par_Tas(L) :\n",
    "    \"\"\" trie la liste L par le maximier \"\"\"\n",
    "    Arbre=Plantation_Maximier(L) # confection du maximier\n",
    "    Liste_Temp=[]\n",
    "    while Arbre!=[] :\n",
    "        Liste_Temp=[Arbre[0]]+Liste_Temp # on récolte le fruit du maximier et on le met par la gauche\n",
    "        Arbre=Cueillette(Arbre)\n",
    "    return Liste_Temp\n",
    "\n",
    "L=[randint(0,10) for k in range(30)]\n",
    "print(\"Liste de départ : \")\n",
    "print(L)\n",
    "print(\"Liste triée :\")\n",
    "print(Tri_Par_Tas(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Complexité"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction **Pousse_Maximier** met en jeu ${\\cal O}(\\log_2(Longueur(Arbre)))$ opérations, car dans un arbre binaire à $n$ sommets, il y a ${\\cal O}(\\log n)$ générations.\n",
    "\n",
    "Ensuite, planter la maximier à partir d'une liste de taille $n$ donne un coût en ${\\cal O}(n\\cdot \\log n)$.\n",
    "\n",
    "La Cueillette donne encore un coût en ${\\cal O}(n)$ opérations et le tri en lui-même conduit à $n$ appels de la fonction **Cueillette**.\n",
    "\n",
    "La complexité du tri par tas est donc en ${\\cal O}(n\\cdot \\log n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Le tri rapide"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Principe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Etant donnée une liste $L$ totalement ordonnée, le **tri rapide** prend un élément $x$ de la liste $L$, cet élément étant appelé **pivot**. On modife alors la liste $L$ pour ranger dans le désordre les termes inférieurs strictement à $x$ à la gauche de l'occurrence $x$, puis les autres à la droite de $x$. Ainsi, suite à cette opération, l'occurrence $x$ est immédiatement bien placée dans la future liste triée.\n",
    "\n",
    "On renouvelle cette opération autant de fois que nécessaire pour avoir à trier des sous-listes de longueur $2$ au maximum."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implémentation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On choisit ici une implémentation récursive, en choisissant toujours comme pivot, le premier terme de la liste considérée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Liste de départ : \n",
      "[3, 3, 9, 2, 8, 10, 9, 9, 7, 7, 6, 1, 4, 1, 9, 7, 0, 5, 6, 6, 7, 8, 9, 4, 7, 9, 9, 7, 3, 4]\n",
      "Liste triée :\n",
      "[0, 1, 1, 2, 3, 3, 3, 4, 4, 4, 5, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 9, 9, 9, 9, 9, 9, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "def Tri_Rapide(L):\n",
    "    if L == []: \n",
    "        return []\n",
    "    else :\n",
    "        return Tri_Rapide([x for x in L[1:] if x < L[0]])+ [L[0]] + Tri_Rapide([x for x in L[1:] if x >= L[0]])\n",
    "\n",
    "L=[randint(0,10) for k in range(30)]\n",
    "print(\"Liste de départ : \")\n",
    "print(L)\n",
    "print(\"Liste triée :\")\n",
    "print(Tri_Rapide(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Complexité"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sans rentrer dans le détail du calcul de la complexité, ce tri rapide est de complexité en ${\\cal O}(n^2)$ dans les cas les plus défavorables car il se peut que l'on doive effectuer ${\\cal O}(n)$ fois la récursivité, impliquant à chaque fois un nombre d'opérations en ${\\cal O}(n)$.\n",
    "En moyenne (lorsque le pivot partage les valeurs de la liste en deux moitiés de taille équivalente), la complexité est en ${\\cal O}(n\\cdot \\log(n))$.\n",
    "\n",
    "Il existe des méthodes pour pallier aux cas défavorables, l'idée est d'implémenter un autre algorithme de tri dès que le nombre d'appels dans la récursivité dépasse une certaine valeur."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Comparaison sur les différents tris"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAD8CAYAAAB+UHOxAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsnXlclFUXx78PDDsqmrvGkqam4pL7hmKhlrlUapmalaZW\nplmvaUH1ZmqlVtpmWtabSpm55VaJJK650eKWK25g4oKyDQzMzH3/uOwMmw7MAPf7+cxnmGee5c4A\n59zn3HN+RxNCoFAoFIrKh4OtB6BQKBQK26AcgEKhUFRSlANQKBSKSopyAAqFQlFJUQ5AoVAoKinK\nASgUCkUlRTkAhUKhqKQoB6BQKBSVFOUAFAqFopKis/UACqNmzZrC19fX1sNQKBSKckVkZOQ1IUSt\novazawfg6+vLwYMHbT0MhUKhKFdomna+OPupEJBCoVBUUpQDUCgUikqKXToATdMGaJq2OD4+3tZD\nUSgUigqLXa4BCCE2ABvat2//bN730tPTiY6OJjU11QYjUxQHV1dXGjZsiJOTk62HolAoCsEuHUBh\nREdHU6VKFXx8fFC9DOwPIQRxcXGcP3+eRo0aoWmarYekUCgKoNw5gNTUVHx8fEhISMBgMNh6OAoL\nCCG4fv06J06coG/fvuh05e7PTKGwCaGHQwkOD+ZC/AW8q3kz675ZjPAfUWrXK5f/mSkpKaSmpqoQ\ngx3j6OjIiRMnqFOnDu3bt7f1cBQKuyf0cCjjNoxDn64H4Hz8ecZtGAdQak7ALheBi8JoNOLgUC6H\nXiQJCQl88803FSK85ebmRlxcnK2HoVCUC4LDg7OMfyb6dD3B4cGldk27tKL2nAUUFxdHr1696NWr\nF82bN6dly5ZZr9PS0nLtO3ToUBITE4t9boPBwKuvvkr37t2zYuezZ8/miy++KPE4b9y4wTfffJP1\nOiYmhjFjxpT4PLeL2Wwu82sqFOUFo9nI3ui9vLP9Hc7HW67duhB/odSub5choMKygEqK86pVuM+c\niUNMDOYGDdCHhJA2ZMgtn69GjRpEREQA8P777+Ph4cHEiRNz7SOEQAjBjz/+WKJzu7i43JKxt8SN\nGzf49ttvefrppwFo0KABS5Ysscq5FQrFrSGE4HTcacKiwgiLCmPb2W3EG+LR0HB2cCbNnJbvGO9q\n3qU2Hru8A7AWzqtW4TllCo7R0WhC4BgdjeeUKTivWmX1a0VFRdG1a1fGjx9Pt27diI2Nxd/fn7x3\nMUajkeeee44ePXrQvXt3Fi9eDMCZM2cYOnQovXv35qGHHuL06dP5rlHQPrGxsYwcOZKAgAB69uxJ\nZGQk77zzDqdPn6ZXr17MmDGDqKgoevXqBcg1lBdeeIEePXoQGBjInj17AFi2bBlPP/00Q4cOpUOH\nDrzzzjtW/54UisrGNf01fjjyA2PXj8VvgR9NPm3CC5tf4M9//2Ro86H8MOQHrky9wteDv8bdyT3X\nse5O7sy6b1apjc0u7wCKi3twMLrDhwt8XxcZiZYnU0hLScFz8mSMS5daPMbo749+1q194adOneKz\nzz6jbdu2Be7z999/ExcXx86dOwGyHMTLL7/M/Pnz8fPzY9++fUyfPp1VeRxVQftMmzaNXr16MXbs\nWIxGIykpKbzxxhucPXs2624lKioq6zxffvklzs7O7Ny5k+PHj/P444+zf/9+AI4cOcJvv/2GTqej\nU6dOjB07lnr16t3S96FQVEZSjansurCLrVFbCYsK489//0QgqOZSjd5+vZnWbRpBjYJoVD13mnTm\nQq/KArIWBaWJllL6qK+vb6HGH8DPz4/Tp0/z2muvERQURGBgIPHx8URGRmaFa0DeKeSksH12797N\nl19+CYBOp6NKlSpcvXq1wDHs3bs3K2zVrFkz6taty9mzZwHo2bMnVapUAeDuu+8mJiZGOQCFohDM\nwsyh2EOEnZFhnZ0XdpJqTMXJwYkud3ZhRuAMgu4Kol39dugcCje5I/xHlKrBz0u5dgBFzdS92rTB\nMTo633Zzw4YkrF9v9fF4eHgUuU+NGjXYvn074eHhLFmyhA0bNvDWW2/lWluwhBCi0H2sVXDl4uKS\n9bOjo2M+R6RQKOBi/MWsOH54VDhX9XLC1aJWCya0m8D9d91PT9+eeDp72nikhVOh1wD0ISEIN7dc\n24SbG/qQEBuNCK5du4YQgkGDBjF9+nQOHTqEl5cXderUYdOmTYDMnDly5Eiu4wrbp3v37vzvf/8D\nwGQykZiYiKenJ0lJSRbH0Llz56zw0smTJ4mNjcXPz680Pq5CUSFIMCTw0/GfeHHzizT7tBne870Z\ns34MEeci6Nu4L98O/paYl2M48vwRPur3Ef2b9Ld74w92egegadoAYEDjxo1v6zxpQ4aQBFbNArpd\nYmJieOmllxBCoGkab775JiDj8lOnTmXOnDmkpaUxdOhQWrZsmevYgvZ57733mDJlCt9++y06nY4P\nPviAe++9l9atW9OjRw+CgoIYOXJk1nmeffZZXnnlFXr06IFOp+Ozzz7D2dm5TL8HhcKWFFVxm25K\nZ3/M/qxZ/r7ofZiECXcnd3r69GR8u/EENQqiRa0W5VruRLPngqP27duLvA1h/vnnH+rXr4/BYMDR\n0dFGI1MUxdmzZzlw4AB+fn7069fP1sNRKLLIW3ELMtvmv73+i6ujK2FRYUSciyAxLREHzYH29dsT\ndFcQQXcF0blhZ1x0LoWc3T7QNC1SCFFkCb5d3gEoFApFafF6+OsWK25fDXsVgEbVGzHCfwRBjYII\n9A2kult1WwyzTFAOQKFQVBiS0pKISYghJjGGS4mXsn6OSYwhJkFuu5hwscDjoyZF4Ve98qyHKQeg\nUChKDWupWxrNRmKTYgs17DGJMSQYEvIdW9WlKg2qNKBB1Qb0rtmbtcfXWtzPp5pPpTL+oByAQqEo\nJYqjbimEIMGQkN+w55zFJ8ZwOekyZpFbV0rnoKOeZz0aVG1A81rNuf+u+7MMfeZz/Sr182XjBB0O\nsrgGUJoVt/aKcgAKhaJUKEjdctyGcSz5Y0mWoU9OT853bHXX6lkGvGXtlrkMe/0q9WlQtQG1PWrj\noJU8k90WFbf2inIACoXC6lzTXytQ3VKfrsdgMtC6TmsebPxgPsNev0r9fJo41qasK27tFeUASkhc\nXByPPPIIAFeuXMHBwYGaNWsCsGXLllz59EOHDuXrr7/OklYoaru1OHfuHH/88UfWOCMjI1mzZg2z\nblHjSKEoDtf111l7fC0rj67kt7O/FbifTzUfdj+zuwxHpigIu3QA1ioEA1i1ypmZM92JiXGgQQMz\nISF6hgzJL7laXKwhB11SmeiSYDQaOX/+PGvXrs1yAO3ataNdu3aldk1F5SUuJY51x9ex8uhKws+G\nYzQbaVS9Ea92exVPZ09m7ZylYu12jF06AGv1A1i1ypkpUzxJSZGVetHRjkyZ4gkk3ZYTsERUVBQj\nR47E39+fw4cPs3r1avr06cOuXbuoVq1arn39/f3ZtWsX169f58knn6Rdu3YcPHiQhg0b8u233+Lq\n6srChQtZtmwZOp2O5s2b88UXX5CUlMT06dM5ceIERqORadOm0a9fP5YtW8aWLVtISEjAwcGBhISE\nLPnnJ554gqZNm/LVV1+xbNkyrl+/zqRJk7h48SIeHh58+OGH3HPPPcyePZvY2FiioqK4dOkSzz//\nvE0ayCjsnxspN/jpxE+sPLqSsKgwjGYjfl5+vNLlFYa1GEbbum2zqmN9vHxUrN2OsUsHUFyCg905\nfLjgjxAZqcNgyF2mnZKiMXmyJ0uXWhY58/c3MmuW3uJ7RVEcOei8nD59msWLF7NgwQJGjx7N5s2b\neeSRR/jkk0/466+/cHZ2zpKMnjdvHr179+bTTz/l5s2b9OnTJ0vj//Dhw0RERODl5cX27duzDD7A\n9u3bs6737rvv0q5dO0JDQ9m2bRsTJ04kPDwckP0G1qxZQ3x8PF27duWpp55S1dYKAOJT47OM/pYz\nW0g3p+Pr5cvLnV9maIuhtKvXzqIkgoq12zfl2gEURRmrQRdLDjovfn5+NG/eHIDWrVtz8aIsUmnW\nrBnPPfcc/fr148EHHwQgIiKC8PBwPv74Y0C2kIzOUDvt1asXXl5eRV5v3759fP/99wAEBgYyceJE\nkpNlFkafPn1wdnamVq1aeHl5ce3aNerUqVOiz6OoOCQYElh/Yj0rj67k1zO/kmZKw7uaN5M7TWZY\ni2G0r9++XOvgKMq5Ayhqpt6mjRfR0flnsA0bmlm/Pn8hyO1SHDnovBQkv/zjjz+ye/dufv31V+bP\nn8+OHTsQQrB06dJ8yp2///77LV07LzkXsB0dHTGZTLd9TkX5ItGQyIaTG1h5dCW/nP4Fg8lAw6oN\nmdhhIsNaDKNjg47K6FcgKrQcdEiIHje33GJ3bm6CkJBbC/GUFSaTiUuXLhEQEMBbb71FXFwcer2e\nwMBAvvrqq6z9Dh06ZPH44kpBb9++nXr16lnFeSjKL0lpSaw4soJHfniEWnNrMWLNCA5eOshz7Z9j\nzzN7OP/SeT7o+wGdGnZSxr+CUa7vAIpCLvQmWTULqCwwGo2MHz+epKQkzGYzzz//PFWqVGHq1KkE\nBwfTo0cPzGYzfn5+LF++PN/x/v7+mEwmevbsyYgRI2jatGnWe9OnT2fSpEkEBATg4eHBJ598UpYf\nTWEnJKcls+nUJlYeXcmmU5tINaZSz7Me49uNZ1iLYXS5s8stFVkpyhdKDlpRKig5aPtDn65n86nN\nrDy6ko0nN5JiTKGuZ12G3DOEYS2G0c27mzL6FQQlB61QVCIKEl1LSU/h59M/s/LoSjac3IA+XU9t\nj9o83eZphrUYRnfv7jg6qIlUZUU5AIWinGNJdG3MT2P4bP9nHL5ymKS0JGq51+LJVk8yrMUwAnwC\nlNFXAMoBKBTlHkuiawaTgX0x+xjbdizDWgyjp29PdA7q312RG/UXoVCUQwxGA3su7mHLmS0Fiq4J\nIVg0YFEZj0xRnlAOQKEoBwghOHb1GFvObCEsKozt57ejT9ejc9Dh4uiCwZS/utG7mrcNRqooT9il\nA7CmGJw98tdff5GQkEBAQICth6KwY2KTYtkatZWwqDDCosK4lHgJgKZ3NGVM2zEE3RVEL99erD+5\nXjU4UdwSdukArCUGVxpYQw66efPmjBo1iqZNmxYotdC/f3/ee+89/P39izUuo9FIkyZNiIqKIioq\nimeeeSZLtVRRPkhJT2HXhV2ERYWx5cwW/o79G4A73O7g/rvuJ+iuIIIaBeWb2asGJ4pbxS4dgDVZ\ndWIVM/fOJCYxhgZVGhDSOYQhTYfc8vmsIQft7OzMhx9+yIkTJ5TWTiVGCMGh2ENZBn/nhZ2kGlNx\ncnCiu3d3ZveeTZ9GfWhbr22R+flKdE1xK1RoB7DqxCqmbJtCijEFgOjEaKZsmwJwW07AEiWRg54y\nZQqHDh0iNTWVwYMHM3XqVIvnXLFiBS+++CImk4mPP/6Ytm3bMnv2bGrUqMGECRMAKe2wZs0aateu\nbfEcRqOR//73v+zbtw+DwcCzzz7LqFGj+Pfffxk7dizJyckYjUY+/PBDOnbsaNXvRJGfS4mX2Bq1\nlS1ntrA1aiuxybEANK/VnAntJtCnUR8CfALwcFbyHIrSp1w7gOCdwRy+erjA9yNjI/MtjqUYU5j8\n22SWHl1q8Rj/Wv7M6nFrsdPiykG/+eabVK9eHaPRyODBgxk4cGAuuYZMDAYDERER7NixgylTptxS\nSGfp0qXUqlWLsLAwDAYD/fr1IzAwkDVr1tC3b18mTZqEyWQiJSWlxOdWFE1yWjI7zu/IiuMfuXIE\ngFrutQhqFCTDOncF0aBqAxuPVFEZKdcOoCgsZUYUtv12Ka4c9Jo1a1i+fDkmk4nLly9z4sQJiw4g\nc60hICCAq1evFijwVhjbtm3j5MmTrF27FiCrWUybNm145ZVXSE1N5cEHH6Rly5YlPrciP2Zh5s9/\n/8wK6+y+uJs0Uxouji708OnBqFaj6NOoD63qtFKyCwqbU64dQFEz9TbftiE6MTrf9oZVGrL+kfVW\nH09xVDXPnDnDokWLCAsLo1q1akyYMIHU1FSL++ZVXtQ0DUdHR8xmc9Y2QxHNDYQQzJ0712LG0fr1\n69myZQsvvPACEydOZOjQoUWOv7JjSXIhwDsgy+CHnw3nmv4aAK3qtOLFji/Sp1Efenj3wM3Jzcaj\nV9g7oaEQHAwXLoC3N8yaBSNKcWmnXDuAogjpHJJrDQDATedGSOcQm40pMTERT09PqlSpwuXLl9m2\nbRu9e/e2uO+6devo0qULu3btonbt2nh4eODt7Z0VCvrjjz+IiYkp9Hq9e/fm66+/pmvXruh0Ok6d\nOkXDhg25du0a9evXZ/To0aSkpHD48GHlAIrAkuTCqDWjEEhBxbqedXmg8QP0adSH+++6n7qedW05\nXEU5IzQUxo0DfUY27/nz8jWUnhOo0A4gc6HXmllAt0vr1q1p2rQpnTt35s477yx04VWn09GrV6+s\nRWCAgQMH8uOPP9K9e3fatWuHj49PodcbPXo00dHRWa0ja9asybJly9ixYwcLFy7EyckJDw8PFi5c\naLXPWFGZvnV6PskFgaC6a3W2P7WdlrVbKr18RYm5eROOHoVJk7KNfyZ6vbwjKC0HoOSgFaVCRZKD\nPn/zPB/t/YgF+xZYfF9Dw/yW2eJ7CkUmiYlw7BgcOSINfuajiJt4NA3MJfzzUnLQCsVt8tflv5i7\nZy4/HPkBTdPwcPIgOT05335KckGRk+Rk+OefbAOfafAvXMjex9UV7rkHeveGFi3kY8IEy87AuxT/\nvJQDUChyIIRga9RW5uyZw9aorXg6ezK502Re6vwSOy7sUJILiixSU+H48dxG/uhROHsWMgMrzs7Q\nrBl06wbjx2cbez8/yBvAeP/93GsAAO7uciG4tFAOQKEA0k3p/HjsR+bumctfl/+irmdd3r3vXSa0\nn4CXqxegJBcqEiXJtklLgxMncodtjhyBM2eyQzM6HTRtCu3bw+jR0si3bAmNGsn3ikPm9VUWkEJR\nRiSlJbHkjyV8uPdDLsRfoFnNZiwZuIQR/iNw0bnk219JLpR/Csq2MZmgQ4f8M/pTp8BolPs6OkLj\nxuDvD8OHZ8/o775bzvZvlxEjStfg50U5AEWlJDYplk/2f8LnBz7nRuoNunt359MHPqV/k/6qQKuC\nExxsOdtm9Ojs15omZ+8tWsDDD2fP6Js2BZf884Jyi3IAikrFiWsn+OD3D1j691LSTGkMbjaYqV2n\n0uXOLrYemqIU0ethzx7Yvl3O+Ati6VJp7Js1k/H3io5yACXEGnLQa9asYe7cudSrV481a9aU6Pqz\nZs0iICCAHj163OYnqVz8fvF35uyZw0/Hf8LZ0ZnRrUfzStdXaHJHE1sPTVEKJCdLgx8RIY3+/v2Q\nni5DOM7OMq6fFx8fGDWqzIdqUyq8A3B2XoW7+0wcHGIwmxug14eQlmZbOejly5fzySef0L59kWm6\n+QgODi7xMZUVszCz4cQG5u6Zy+6Lu6nuWp3gHsFM7DiROp5KhrsikZQEu3dLYx8RAQcOyLi9o6Nc\nmH35ZejVS2bjrF9f9tk29kqFdgDOzqvw9JyCpkkpCEfHaDw9p5CUxG05AUsUVw763XffJTIykhde\neIH+/fvj5+fH8ePHmZXx1zds2DBefvll2rdvz4svvsiRI0cQQvDkk08ybtw4JkyYwMCBA3nwwQfZ\ntm0bb7/9NiaTiXbt2jFnzhycnZ3x9/dn5MiR/PLLL5hMJr7++msqanc1S6QaU1l+aDnz9szjxPUT\n+FTzYUG/BTzT9hk8nT1tPTyFFUhMzG3wDx6UBl+nkwu5//mPNPhdu0KeG3CbZNvYK2XmADRNuwsI\nBqoJIaxifd3dg9HpCpaD1uki0bTcYmmaloKn52SMRsty0EajP3p96clBv/baa+zatSur29eyZcss\n7vf3338TFxfHzp07AYiPj8/1vl6vZ9KkSaxfvx4/Pz/Gjx/P0qVLGTt2LAC1atVi27ZtLF68mIUL\nF/LBBx/c0mcqT9xIucEXB7/g4/0fcznpMm3rtuW7R75jaIuh6Bwq9FynwpOQIA1+RIR8REbKrB2d\nDjp2hFdfhZ49pcH3LIaPL+tsG3ulWP8VmqZ9DTwEXBFCtMyxvR+wAHAEvhJCvFfQOYQQUcAYTdNW\n3d6QS0JBSpm2lYMuDn5+fpw+fZrXXnuNoKAgAgMDc71/8uRJGjVqhJ+fHwCPPfYYoaGhWQ7goYce\nAqT20NatW60yJnvlQvwF5u+dz5d/fElSWhJ9GvVh2cPLuM/vPqXNU06Jj4ddu7Jn+JGRMufeyUka\n/OnT5Qy/SxcohgivogCKOy36H/ApkDVt1jTNEfgMCAKigQOapq1HOoN38xz/jBDiym2PNg9FzdS9\nvNrg6JhfDtpsbkhCgm3koPOi0+lyyTtnSkPXqFGD7du3Ex4ezpIlS9iwYQMfffRRsc/rkpGr5ujo\niDEzibmCcSj2EHP3zGXFkRUIIXi85eP8p+t/aFO3ja2HpighN29Kg5+5aPvHH9kGv3NneP31bINf\nGbJzyopiOQAhxA5N03zzbO4InM6Y2aNp2gpgkBDiXeTdgs3R60NyrQEACOGGXm87Oei83HnnnYSG\nhiKE4OLFi/z9t2wEfu3aNVxcXBg0aBB33XUXL730Uq7jMhvAnzt3Dl9fX3788Ue6du1qi49Qpggh\n+O3sb8zdM5dfz/yKh5MHEztM5KXOL+HjVbgyqqLsKaji9uZN2LkzO6Tz11/S4Ds7S4MfEiJDOp07\nK4NfmtxOYLQBcDHH62igU0E7a5p2BzALaKtp2msZjsLSfuOAcQDet6mClJY2hKQkrJoFZG26detG\n3bp16dKlC82aNcPf3x+AmJgYXnrpJYQQaJrGm2++mes4d3d3FixYwFNPPYXJZOLee+9lVAXKYcvb\neOWdwHdwcnRi7p65/PHvH9TxqMOs3rN4rv1zVHerbuvhKixgqeL2qaeyHYIQsqiqc2d44w05w+/U\nCdxU35wyo9hy0Bl3ABsz1wA0TRsC9BNCjM14PQroJISYWOBJSoiSgy6/3I4cdN7GKyAllwWCJnc0\n4T9d/sOo1qNw1blae9gKK9KwoWV1SxcXeO21bIPvqn6NVqcs5KBjgDtzvG6YsU2huC2Cw4MtNl6p\n5V6Lf174R0k12DEnTsDq1fJRkM59Whq89VbZjkthmdtxAAeAuzVN80Ma/seBJ6wxKE3TBgADKlPu\nukKSZkrjfLzlWv1r+mvK+NsZQsDff8OaNdLoHzsmt3fqBF5eMtafl9LUt1eUjGL9N2ma9j3wO9BU\n07RoTdPGCCGMwETgV+AfYKUQ4qg1BiWE2CCEGJezgEpRsTGZTSw/tJxmnzYrcB/VeMU+MJth716Y\nOlUqY7ZtKxd3a9eGjz+Gixfl+59+mn8Bt7JW3Norxc0CGl7A9s3AZquOSFGpEEKw6dQmXg9/ncNX\nDtOmbhumdp3KZwc+U41X7AijUaZprl4Na9fK8I6TE9x3n4znDxwoHUBOVMWt/aPKIxU2Y9eFXUzf\nOp3dF3fTqHojvn/0e4a1GIaD5kDruq1V4xUbk5YG4eEyvLNuHVy7Jhds+/WD996Dhx6SYZ7CUBW3\n9o1dOgC1BmB/rFy5ku7du1O/fv3bPteh2EO8Hv46m05toq5nXRb2X8iYtmNwcnTK2kc1XrENej38\n+quc6W/cKCtyq1SRxv6RR+CBB1TlbUXCLh2AEGIDsKF9+/bP2nosebGGHLS/vz9eXl5ZaawffPAB\n7dq1K9E4lixZQtWqVRk6dOjtfByioqIICAigcePGGAwG2rVrx/z589Hl6GP37bffkpaWdtvGP+pG\nFG9ue5PvDn9HNddqvHvfu0zqNAl3J1XpY0sSEmDTJmn0f/5ZOoEaNaTBf/RRGeZRqZoVE7t0ANbE\neZUz7jPdcYhxwNzAjD5ET9oQC2LgxcQactAAGzdu5HYWuceMGXPLx+alcePGREREYDQaefjhh9mw\nYQMPP/xw1vujc7ZKugUuJ11m5o6ZLIpchJODE9O6TePVbq+qAi4bcv26lEVevRrCwmS4p149Waj1\nyCOyCre4vWwVVqQkzYqtQIXOqXNe5YznFE8cox3RhIZjtCOeUzxxXmWF5p15iIqKomvXrowfP55u\n3boRGxuLv79/PhXPgti+fXuuSt5XXnmFlStXAvDWW2/RtWtXAgICePvttwGYPXs2X3zxBSCVQ/v0\n6UNAQABPPfUUCQkJAPTv358ZM2YQFBREp06d2L9/f6Fj0Ol0tG3bln///RcAo9FISEgIQUFBBAQE\n5FIu/eijj+jRowc9e/bMkrLOS5opjZ+O/0SjjxvxxcEvGNt2LKcnnebd+99Vxt8G/PsvfP453H8/\n1KkDzzwje99OnCiVNqOj4bPP5IxfGX8bkFk6ff68zK/NbFYcGlpql7TLX3Nx1wDcg93RHS74I+gi\ndWiG3GqQWoqG52RPjEstC6QZ/Y3oZ+ktvlcUxZGDzuShhx7C0dERNzc3fv755wL3u3LlClu3bmX3\n7t1ommbRoTz33HN89NFHdOrUiZkzZzJv3jxmzJgByLuRsLAwfv75Z+bNm5flVCyRkpLCn3/+ydy5\ncwFYunQptWrVIiwsDIPBQL9+/QgMDOTIkSOEh4ezZcsW3NzcuHHjRq7zCAQGo4Flh5Zx1fkqAwMH\nMqPXDO6+4+4ivxfFrVHQxPHcuewc/d9/l3alaVOYNk2Gd9q2lf1vFXbAa69ZblYcHFxqdwF26QCs\ntgZQtmrQJZKDLm4IqHr16jg4OPDSSy/Rp08f+vTpk+v9uLg4DAYDnTpJGabHHnuM559/Puv9TFno\nNm3acOHCBYvXOH36NL169eLcuXM8+OCDNGsmc/G3bdvGyZMnWbt2LQAJCQlERUWxY8cOnnjiCdwy\nRFuqV8+ezevT9SSmJZJiTKGORx3Gdx7Ps4/a3VJOhcKS5s7TT0u7kdn/tk0bmDFDhneaN7fdWCs9\nJpP00idOwMmT2c8nT8oCCksU8H9rDezSARSXombqXm28cIzOrxdkbmgmYX2C1cdzK3LQmTg6OuaS\nhTYYpJfu6TbsAAAgAElEQVRycnJi69atREREsH79er755htWrSp+S4XMRWkHBwdMJpPFfTLXAK5d\nu8YDDzxAWFgYQUFBCCGYO3cuAQEBufb/5Zdf8p0j1ZhKoiERozDi5OCEp7MnDzV5iDur3ZlvX4X1\nMBplQVbeiWN6ugz5zJ0rjf5dd9lmfJUSIWTObF4Df+IEnD6duyFx1arylqxHj+y0q7yUYul0uXYA\nRaEP0eM5xRMtJfseV7gJ9CG3FuIpTe68805OnDhBWloaer2enTt3EhAQQGJiIgaDgb59+9KxY0c6\nd+6c67gaNWrg6urK/v376dix423JQtesWZOQkBAWLFhAUFAQvXv35uuvv6Zr167odDpOnTpFw4YN\n6dmzJ5988gkPP/wwDs4OXIy9iEdVD3QOOqq7VMdV50qiQ6I1vhZFDkwmaUcOHsx+/PknpKRY3j89\nXbZGVJQSej2cOmXZ0OfUwHBykiXTTZpA//7S4DdpIh+1a2fH4EJDCd26leC33uKCtzfeFy4w6+23\nGXH//aX2ESq0A0gbkkYSSVbNAiotfHx8eOCBB+jWrRu+vr60atUKgMTEREaPHk1aWhpms5l33nkn\n37Gff/45U6dOJTU1FT8/Pz755JNbHsfAgQOZM2cOBw8eZPTo0URHR9OrVy9AOohly5bRt29fDh05\nROB9gTg6OhJ4fyDBrwfj5qR0fK2F2SwnizmN/R9/QHKyfN/dHe69F8aPh2XLZFZPXpTmTiEUN9vG\nZJILKTmNe0Ehm4YNpXEfPlwa90xD7+NTrFX10BEjGPfYY+gz9j3v68u4L78EnY7SygMqthx0WZJj\nEfjZU6dO5XpPyUHbFqPZSGJaIqnGVBw0BzydPfFwyh/6uh056MqGEBAVld/YZyRz4eoqF2vbt5eP\ndu2gWTPI/PPPuwYA0kEsXqyqcC1i6Qtzc5O3Sz4+uQ39mTO5QzbVqknDnnMW37SpnOHfZoWcL2BJ\nBtEHOFfCc5WFHHSpYc+FYJUVkzCRaJCLuxoaVZyr4OHsgYZKISkJmdl9OY19ZGR2xMDZWS7Yjhwp\nDX379nLRtrAJpNLcKQEmk+VFk5QUyLy7dnaWBr1pUylylNPQ16xp9bSps8DPWDb+AKW3BGynDkBh\nP5iFmaS0JJLTZezBw8kDT2dPJctcDISQufU5jf3BgxAXJ993coJWreCxx7KNfYsW0v6UFKW5YwEh\n4OxZOHAA9u+Xz5GR+Y1/Jpom424+Ptm3V6VAKrAdafR/Bk5mbNcBlpLTSzOSpxyAwiICQXJaMklp\nSQgEbjo3qrhUwVGr3GG3wkLHly7lN/ZXr8r3HB3B3x8efjg7lOPvL7tjKaxEbKw08jkNfubiiIuL\nXDQZO1b+EgtaNCmldKkzZBv8bUAK4Ar0Al4A+iEbrIwDcrond2Qf3dJCOYBKTooxhURDIiZhwlFz\npIpLlaxZv1mYcdW5UsW5CjoH9adSUL79vHnS9mQUUOPgIGfy/ftnG/tWrVSvW6uSmChn85mGfv/+\n7Hz5zF/A4MHQoQN07AgtW8pbLpCvLS2aWLFRQQoQQbbRP52xvTEwFngA6Ik08Jk0yXgORoZ9vJHG\nvzRv7NR/dSUmxZhCfGo8ApkIYBImbqbKYLSzozNVnavmUuis7Fgq1ExPl3IKw4dnG/vWrZViplUx\nGODQodwz+3/+kSEekLP2Ll1g8mRp8O+9t/BfQCktmpwi2+BHIEM9rkAgMAlp9IvSNx5B6Rr8vNil\nA1By0GVDoiExy/jnxEFz4A63O2wwIvvk0CFYtKjgQk2TCZYuLdsxVVjMZpmBk3Nm//ff2Zk4tWtL\nI//YY/K5Qwe5MFtSrLBooif3LP9MxvYmwHikwQ8A7PnGzy4dgD1nAVlDDro0iIyMZM2aNQUKs1ni\ntVdeY8xzY/Br5Jdru1mYCzii8qDXw8qV0vDv3StDyB4e2Xn4OVH59oVQ2KKJENKr5pzZHzwowzsA\nnp7ylmryZBm26dBBnsNG4kUCuWCbafC3I1Vl3IDewBSk0b+tVYRQyjQGZJd1AJm0b99eHDx4MNe2\nktYBrHJ2Zqa7OzEODjQwmwnR6xmSZp1CsKLkoB0c7DdTxmg2clV/1eJ7jpojtT1q59tuNBpz9Qko\njPJaB3DsmDT6S5fK1MymTWWx1ZNPwi+/qHz7EmEp397FRXaXMRikwY+NldudnGTsLNPQd+wov3wb\n1/okIxdtM43+2YztTZHGPnOWb5V2CaFYXgVeTImdQHHrAOzXQlmBVc7OTPH0JNrREaFpRDs6MsXT\nk1W3kmdXBMWVgzYajdx1112EhITQrVs3hg4dSmRkJAMGDKBdu3aEhYUB0oA+9NBDBAYG0rt3byIj\nIwH46aefsprA/Pvvv3Ts2JGrV6/mkpOePXs2EydOpH///rRp04bNmzfzxhtv0L17dx5//HESUhK4\npr/Gk0Oe5PjR4wDs3LaTEQ+PYFj/Ybz64qskZ0x1/f39mTFjBoGBgWzatMnq35s9kJoKy5dLOZYW\nLWDhQtn5KiJChpqnTIE77pBGfvFimSWoafJZGf9CeP31/IsmBoOUJj1zBvr2lZ3j9+2Ts/4DB6Qe\n9VNPyeKHUjT+ocjCK4eM50zBZQH8A3wIBAE1gAHA/4CWwOdAFHAc+Ajow20a/2vAHuAb4HlyG38y\nXgffzgUKxy5DQMUl2N2dw4XMSCN1Ogx5bhdTNI3Jnp4sNVqWg/Y3GplVUJ5wERRXDjohIYH777+f\nmTNn8sQTTzBnzhzWrl3LkSNHeOWVVwgKCqJOnTqsWrUKV1dXTp06xQsvvMCWLVsYNGgQGzZs4Jtv\nvuHnn38mODiYWrVq5bvG+fPn+emnnzhy5AgDBgxg2bJlvD3jbR4b/hibt2ymT58+ODk4UcWlCjev\n32TJwiV88/031PaqzcKPF7J48WKmTJkCSAmIbdu23dJ3Ys8cPy4N+Lffytz8xo1hzhxpfyx8pYDK\nty+SxER5q7RuXcEqlpomb7VsRN6J9nlgDNIGnya7IOseYCJylt8DuOWMXUPGiU8gY0gncjziinF8\nKVaClWsHUBRlrAZdbDloNze3LH2d5s2bU7VqVXQ6Hc2bN+dixkpjWloa06ZN4+jRo+h0Os6ePZt1\n/Jw5c+jevTtdunRh0KBBFq8RFBSUdU6ALj26cFV/lUZNGnH98nVquNVA0zRcHF04e/Qs586cY/SQ\n0VnXzpSXBnJ1ByvvGAxSH3/RIti+XVbYPvywDPMEBsoMQkUJiY2V7cXWrYOtW+WCbc2aNl80SUfa\n1+s5nq8Dr5B/om0AfkPO9qcjjb5PSS4mgEvkNu6ZBv8ckHNZrR4yhjQ04znz0RvLxr4Uv65y7QCK\nmqm38fIi2sJtZEOzmfUJtpODdnLKTq10cHDIJdlszLgz+fzzz2nQoAFffPEF6enp+Phk/znGxMTg\n6OjIlStXEEKgWVgUy3lOnZOOuJQ4dA46PFw8cBS5vxMhBL1792bhwoUWx+vuXv579p46JWf7//uf\nVOr184N335V5/HXq2Hp05ZDTp6XBX7cO9uyRC7p+frK92ODB0LUrrFhhFXVLAcSTbcBzGnNLrzO3\n3cp/+E9F7ZCINOp5Z/InkQsGmbgj04E6ACPJNvJ3A1ULOPdsyrwSzC4dgLXSQEP0eqZ4epKSw0C6\nCUHILYZ4ypKEhAT8/PzQNI0VK1aQuVifnp7O5MmT+frrr1m6dCmLFi1iwoQJFs9hNBu5pr8GAtyd\n3KnqUtViJW+HDh14/fXXOXfuHL6+viQnJ3P58mUaNWpUqp+xtElLk/Zp0SL47TcZUh40SM72779f\nzfZLhBBSoW7tWvmlHj0qt7dtC//9rzT6/v65MnQsqVs+++WXxOl0BFCw4c77Og6w3MlC4gXckfGo\nDTTL8TrzUSPHzwGApYzerIm2CTlrz2ncM3++lOMADbmA0AQZI8o5m2+Q8X5JyAwtlmEWkF06AGul\ngQ5JS4OkpFLLAipNxowZwzPPPMN3331HUFAQLhmaAfPmzSMgIIAOHTrQtGlTgoKCuN/CjCrNlMY1\n/TVMwoSmaVRzKbj7WO3atVmwYAFjx44lPT0dgODg4HLrAKKi5Gz/m2/gyhW5WDtzpuyBW6+erUdX\njkhPhx07smf60dHSiwYEyOyeQYPkl2uBm8DLkGX8M0nR6ZhUwOXcyW2oW5HfeOd9XR0o6VLxu7tg\nXFvQ57hhd0+GWbOBdch4fU4TUR1p1O8nt5FvjJXSf3JQxpVgFT4NtLJhFmZupt7EYDLg4uiCl6uX\nTYTbyjoNND0dNmyAL76AsDA5ux8wQM72+/SxeTZh+SE5GX79Vc70N26UubBubjJjZ/BgmcJ5R+4i\nQRNwFNib4/FPEZdZRX5jftu21ADEZjwuW/g58/kUhD4OwbPhgjd4X4BZr8OIH4H+yBl9TkNfk5LP\n5m1MuZaDVtwaBpOBm6k3MQszVV2qWtTpr2icPw9ffglLlsDly7Inx9tvw5gx0KCBrUdXTrh6VXrP\ndeuk90xNhRo1pMEfPBiCgmTBQwaxwD6yjf1+ssPfNYEuyLD3AuCKhcv5AI8Wd2xpZBtyS8Y85883\nCzhHNaAOUBdoDZyEEd/LRy405B1AJUI5gApCgiGB5PRkdA46arjVwMmh4mr4GI2waZOM7We2J37w\nQZgwQebvq9l+MYiKgp9+kkZ/1y4pweDjI2+ZBg+G7t1Bp8MA/EVug5+Zj6YD2gLPAJ0zHn5kT5Z9\nCgq1RAKNKNyYZz7fKGD8Vck26v7I8EzdjG118vyc99bCF8vi+5Wwols5gHKO0WzkRuoNjGZj1kJv\nRWjSYklBICAAvvpKzvZjYqB+fQgJkQq/So6hCISAv/7KjucfOiS3t2oFb7wBgwcjWrfmoqaxF/gd\naez/IDscfifSyE/MeG5LITo3ehgxFAi0EGrJO/POpArZRrsFMi2yIKN+OwI7syh73WU7RTmAcow+\nXU+CIQFN06jhWgMXXcUQl7ckuzx6tBRd07TsAtKHHipWq9XKgSWP+dhjcnafafTPn5eLI927w4cf\nkjx4MAf9/HLF7i9nnM4NaA9MRhr7TsjElnxk5r//jbxV+DvjcVK+ZzHUAvAF+Y16WWUb2yDbxl5R\n/z7lEHtZ6C0tgoPzKwiYTFC1qpzE+vlZPq7SEhoq8+0jIrLz7UNCGDF+vFzUdXFB9OnDyQ8+YG9Q\nEHurVmUvcJjs9Mq7kdIHmaEcfyBfEDENubqbaeQzDX7O3ip+yDj740jdBEtyUz5IuUxbUta6y3aK\ncgDljIq+0JuYKCeqBb2njH8e0tII3bWLcZ9+ij6jEPG8ry/PLl7MobZtcX/gAfY2acI+nS4rnF4V\nOaN/HWnsOyIXb3NxjWxDn/k4hiyvBRlX9wceRhr81si8zZzZxnejQi12jl06AHvuB2BLOejMhd5t\nW7ZxNfoqkydNzvW+0WikSZMmREVFWeV6ZUlCAnzyCXz4YcH7qDg/Usti/36pYxERAXv2EHzsWJbx\nzyTF3Z05r7yChhQxG0L27L4ZOVQgTci897whnJgcJ6uHNPD9gDYZP99N0dZDhVrsHrt0ANbsB+B8\naRXup2bikBqD2bUB+rtDSKs/5JbPV6NGDSIiIoCi5aB//PHHIs9nMpmKrGfIu9A7/JHhFWKhF2Sa\n+ccfw0cfyZ/795dKwO+/X6od+8oPKSlSLTMiQhr9vXtlmqamcTEoiPVLl3K+gGIszWwm3sGBrOlH\nInCI3CGcI2TP0HVIBbRAsmf1rZHltbeKCrXYNXbpAKyF86VVeB6dgmZOAcAxNRrPo1NIgttyApaI\niopi5MiR+Pv7c/jwYVavXk2fPn3YtWsX1apl3xdnztKHDx/Ozp07+eCDDwgPD2fr1q2kpqbSqVMn\n5s2bh6Zp9O/fnxb+Ldi9ezdms5kFCxbQsX1Hli1bxvHjx5k1axZnz55l/PjxpKSk5Cu4WrBgARs3\nbsRgMDBgwACmTp1q1c98O9y4AfPnw4IFEB8PAwfCm29Cu3by/UaNrN6xr3yg18Pvv2cb/H37pKaF\ngwOiTRuOzJjBugED+KlxYyIzVsB1RjNGXf4JgfdVI1UWOWcb/DM53qyONO7jyDb0zbkNyUtFeaRc\nOwD3f4LRJR4u8H1dfCSaObf2p2ZOwfPoZIzRlnv4Gav4o7/n1qaaJZGD7tKlS1b3rsaNGzN9+nSE\nEIwbN47w8HB639ebdHM6SSlJbNiygcMHDvPqf17NuvvI5LXXXmPcuHEMGTKERYsWZW0PCwsjOjqa\nLVu2IITg8ccfZ//+/XTs2PGWPpu1uH5dzvY//ljG9B9+WGYh5v3KKo3sclKSFFPLNPgHDsiyZkdH\nuPdejFOmsHvQIH66917WubhwFpln3xl4HxgEHHzZgXHvWsi3n+IMK5CSBW2Bp5CGvg3QkHJX3aqw\nPuXaARSJuQDh54K23ybFlYN2dnamf//+Wa937NjBp59+isFg4Pr167Rs1RL/Lv4IIRjy6BBquNWg\nZ0BPrl69SlJSUq5zHThwgNBQ2c5i2LBhvP/++wBEREQQHh5OYGAgAMnJyZw5c8ZmDuDaNRnf/+QT\nafOGDJGGv1UrmwzHdiQkwO7d2QY/MlJWtul0sv3hK6+Q3Ls3W7p35yc3NzYik2xckLVOryEli+te\nBn4FfoamPwDXLOTbr0BKYnra5qMq7J9y7QCKmql7bW+DY2p0vu1m14YkdFxv9fEUVw7a1dU1S8JZ\nr9czffp0fvvtN+rVq8dbM97iRtINHDQHnByccHPKXfFiSfrZ0jYhBC+//DIjR468hU9iPRISYNo0\n2ehJr4dhw2TxVsuWNh1W2XHzpszFzzT4f/whq26dnORix7Rp0LMnV7p2ZaOHB+uAMCAVGaXpDwwG\n+hrB83fgF2Rvwj8zzl8X8Cgg394HZfwVhVJxksctoL87BOGQ24AKBzf0d4fYaET5SU1NRdM0qnpV\n5dyVc2zetBknBydqutdE0zTWrZPiJLt27aJ27dr5nEyHDh2y9lm1alXW9sDAQEJDQ7NaO166dInr\n169TVpjNMrIRHAzz5knhyCNHYMWKcm78Q0PB11cWVPn6ytc5iYuTEgtTpsC990pNnQEDZOWau7v0\nfuHhcPMmp3btYt7MmfQICqKuhwdjkGu044BwIDYGln0Njw4Fz5pIHeP3kUZ9NtIJxACLyF9EpdIt\nFcWgXN8BFEVa/SEkgVWzgKxNjRo1eHTYo3Tr1o1atWvRvl17XHWuWVk+Op2OXr16YTKZ+Pjjj/Md\nP3v2bCZMmMD8+fNzLQIHBQVx6tSprG2enp4sWrSIO/IoOVobs1mGeBIT4e+/pQ3cuFH29y73WCpR\nfvZZmZYphJzhHz4sf3Z1hS5dpFZ+z57QqRNmV1cOIpuOrEOm1YMMyb8FDEqH1rtBy5zlZ6g1UB+Z\nx/kAcB9SAD8nKt1ScYsoOWgbUlRFb//+/Xnvvffw9/e34SiLh9ksjX6mbYyLO8uePQdo06Zs5KDL\nBF/fgqvU3N1lF6xevaTB79ABXFwwANuQRn89UjXBEeiJXMAddAl8NiEN/lZkqqYO6I40+P2QBVdq\nwVZRApQctJ2RYkwh0ZCISZhw1Bxx07mhN+rLfUWvySRn/JmG380NqlSRqerVCu5BU75ISZEa+QUZ\nf02Tea0ZRYA3kfZ8XcZzIuCBtOWD0+HBPVBjY8abGY21uBMYjjT6vSm4baBCYUWUAygDUowpxKfG\nI5B3WyZhIik9CQfNgVrutdA5WP41bNq0qSyHWSLyGn53d/D0rEBSzElJsHkzrF4ttaeTk8HBgdDH\nHiN49uxszZ3XX2fEnj1cdHZmPXKmvw0wIvXNHgcGxcJ968F1IzK4n4wU2gkAnkYa/XtQs3xFmVMu\nHYA9h60skWhIzDL+OdHQCjT+9kpxDH9mJXS5Iz5eLlisXg0//yxvY+rUgVGjYMgQQp2dGXfvvbk0\nd57+3/8IMRg4l3GKpsArRhj0B3T6ARw2A8cz3vQFnkQa/EBUho7C5pQv64NMoYyPj8fV1drNOEsP\nk7Dc0rqg7faIySRj/CmyqLrAGb8QgsTERAyG0qm1sDpxcbB+PaxaJbthpaXJVmLPPiuLFbp1A0dH\njMBUcuuaAaQ7O3PJ2Zn3rsOgX6DZ98hbAD0yeb8nUvmyH9I7qFm+wo6wSwdQmBhcw4YN+fPPPxFC\nlJtF4ARDAmZhzrfdQXMg1SXVBiMqPmaznAhn9IrH2RlcXOS2uLj8+wshMBgMxMTEIIRAZ4+C/Veu\nSH381avht99kIZaPD7z4Ijz6KKJTJy44OLAf2e5wHxBJfuOfSboZpmXKaTZCtsh6AGn8y+fSjqKS\nYIf/nYWLwTk5OeHl5cXGjRupWrWq3TsBszCz9O+lXNHn7o7q5OBE38Z9aV6zuY1GVjhxcVKS5tgx\nWaTaujV06gTFrHXDZDKRmpqKt71IeF66JBudr14t0zXNZmjcGP7zH24MG8aBNm3Yr2lZRj824zAX\npIrCWCA0Dq7XyH9q74vAx8hZ/t1l8mkUCqtglw6gKJo0aUJQUBCHDx8mLS2t6ANsyNaorVzRX6F1\nndacu3mOBEMCVV2qEuAbYBfG/9gx2LFDVuxWrSo1ea5cgX/+kYa/Qwdp+N1L2K3J3d2dzp0706RJ\nk9IZeHG4cAHWrJHhnT17QAgMrVrx9+efs/+hh9hXvz77NY2TOQ5pBvRF6uV3BFpdA+efgFXQsTqM\n+9KC5s7rQJ56MIWiXJC5YGePj3bt2onyzLzd8wT/RUwLm2broVhk+XIh3N2FkJVL2Q9nZyGmTRPi\nyhVbj/AWOHNGiDlzhOjYUZg0TZy4+26x9PXXxcR9+0RHvV44i+w/sLpCiEFCiFlCiDAhxM3Mc/wr\nhPhcCHGfEMIxY2c/IURVIZYPF8LnrBCaST4vHy6E8CnDz6dQFAPgoCiGjS13hWDlhTX/rGHIyiE8\n2vxRfhjyg122bCyorqlhQ7h4scyHc+ucOAGrVxP722/sd3Njf8eO7AsK4kCbNtzMSBbwQPa47Uj2\n7D6XIGY0sAZYDexE9rptiqzAfRRZrvsdljtcLUZV3SrsiuIWgikHUAociDlAz//1pFWdVmwbvS2f\noJs9IITM4LH069c0GSK3JaEUomwgBMnHjvHHvn3si4tjv7c3+zt25LyvLwCOQtBS07IMfUek1H2+\n1aJzSIO/CtkRHWTV7aNIw9+c/Fk7hQ5MUX6o2L9IVQlsI87fPM+A7wdQx7MO64evt0vjHxMDzz9v\n2fiD7VsvhgLjjEb0GRlE54GxRiPbbtzA4dw59lWpwpFmzTC3aAGAb3w8nZyceBE5u2+raQUn35xE\nGv3VyNQegHuR//+PImf9haE6XJUQezS0oeS+lTuf8RpsP7ayRTkAKxKfGk//7/qTakxl2+ht1Pa4\nnV561sdshq++gqlTZVrn8OFSuNLeWi8GJyWh98xdJZWq07GkVi28dDo6njnDoD//pGOjRnSoXp06\nRWlOHEPO8lcBmf2DOgFzgUeAu6z9CRQSaxpaE2BACmXf7uMb8if16oHngH+QAUP3jOecj4K2WTMT\nsWwdpnIAViLdlM7QH4dy4voJfh35K/fUusfWQ8rF6dOytikiQuqVffmlzIIMDbWP1osCKX65Cjhf\nQK6pZjYTZzKhtS/izlYgWyBmhneOI0M53YH5SKN/p5UGrsiDGdnC5grwMpYN7QRkN5uSGO302xyX\nBrhmPJIK2CcReDfjM5QEFwp3FMV1Jjsyrp9ZG1T6dybKAVgBIQTPb3qesKgwvh74Nb39ett6SFkY\njbL37htvyCKuxYth7FgZ5wfbtl4UwAGyIzJnAAezGReDAYNb/tCZ94ULaBlxfosnO4g0+FknA3oB\nk4CHkc1TFLdAOtKgx+Z4zvtz5uuryNl6YSQBu8k2yC4ZzzVzbLP2w4nsBR1fpHHNiw9wFnmnoUeK\nNuV8WNpW0HY90hFeyLOtoHLCgtAj7wiUA7Bb5u6Zy1d/fkVwj2Cebvu0rYeTxaFDMGYMHDwom65/\n/rlUObAlZmAP0kavQf576ITgvvPnmfbZZwz69lvC+vVj3MKFWZo7AO7Jycz68EPZTDjnyfaSbfQv\nIP+i7wemI/WWa5XJx7IDSho60GPZkFsy6hZKvgFwQ0re1UEa1Y45XtdBet5YC8f5kLtDfVkzC8vp\nXLPIfadgoervtjEDKVh2HveBBc0w+TstHZQDuE1WHVvFtK3TeLzl48wInGHr4QBgMMDMmfDee1C9\nOvzwAwwdmj3rL2uMyJvb1cBa4F/knK9PWhozNm9m4MsvU/3sWejdG77/nhGXL8OE5QS/M4YL3o54\nXzAx643ljOjXSU4udyKN/lqkwL4L0Ad4B9kwt7oNPqRNsRRrfwbZXNIby0a9oDBINbINeAukNnXm\n69rkNvAeFC5ulE7BhtaW2LKDjgPZIZ+8eGP5zqQUszKKUyxgq4e9F4L9fvF34TrTVXRd0lWkpKfY\nejhCCCF27xbinntkQdeoUUJcu2abcRiEED8LIcYKIWoK+Qt1E0I8KoT4Li5OxIeECOHpKQc6cKAQ\nv/+effByIYRzeu6/Bp1RiEAhRO28JxNCxJfZx7JT7hQF/xtpQohaQoiWQla2DRdCvCSEeFcI8bUQ\nYqMQ4oAQ4oIQojT+hpcLWSmnZTwvL4VrVBSWCyHcRe7fn7u4le+MYhaC2dzIF/awZwcQFRclas2p\nJRotaCSuJNm+ZDYxUYhJk4TQNCG8vYX4+eeyH0OKEOInIcQoIYSXkL/EKkKanNVCiOSzZ4V47jkh\nXFyEcHAQ4oknhDh0KP+JfETBtuxxIcSPQoikUv4w5YJ/hBDPi8KNf7rNRqe4FazjMIvrAFQI6Ba4\nkXKDB797EKPZyKYnNlHLw7aB5i1bZKvaCxfghRdg9mzZlassSEY2tloFbEIGFqojw+9DkOF412PH\nZDzqu+9kM/WnnoJXX5VpSDkxI9cGC2i8BcD3Vv8I5QwzsBn4BNgCOCPDCckW9vVGRXnLGWeRGWx6\nZPCbhyIAACAASURBVLSsNeBXepdTfx0lJM2UxpAfh3Am7gxho8JoWtN23c7j4uDll+Hbb2XT9Z07\npXx9aRMPbETG9H9BLmnVAp5A1lIFInMuOHhQeqO1a2WBwaRJcsANG2afTAB/IA37D0hJBg3La2F2\nIixqG+KR+eufIhdQ6wMzgWeRsX57jLUrSsTZUNg/DkwZv0f9efkawK+U1ieKc5tgq4e9hYDMZrN4\net3Tgv8ilv611IbjEOLHH4WoXVsIR0chgoOFSCnlJYjrQkaM+wuRJahWTwgxUQixTQhhzDm4iAgh\n+vSREUYvLyHeeEOIq1dzn/AfIcSbQogmGSdzEkIMEDKmv0RYKxRaATgmZJjHQ8gvopsQYoUQIi3P\nfirWXq4x3BBidT0hQsn/WOtT4tOhQkDW591d7/LNX9/wVs+3GNV6lE3G8O+/Msyzdi3ce6/sVd6m\nza2fr7DkwVhkY/PVZPe59QYmImf6nZE5DYDUldi8Wc749+yRrRTffx8mTJA602RcZAVytv8XcqYf\niGy19Qi5s+5cChlYhSczzPMxcnbvjLy/ehGpW2EJpVFhtwgB6Tch6Rwkn4fkc9mPpIzn9PiCj9er\nNFCbs+LICoJ/C2Zkq5G81fOtMr++EPDNNzKCYjBI2/ryy1Kz/1axlDz4LLJG8wIy29IMNAb+gzT6\n7ciT+GcySb392bNl4YGPD3z2GTz9NLi5yYzDZUijvzvjmE7IitxhQL0CBlcp7dlNZJjnM2SYpwHZ\nYR77khVR5EAISLuRw7CfzzbsmY/0hNzH6DzBw1c+aveQz8feA8O1/Od3L73YZ5k5AE3TBgP9garA\nEiHElrK69u2y+8Junlr3FD28e/DVgK/QyjihPipKLvKGh0NAgNTzudsKnaeCyV+XmIK01y2AEKTR\n98dCtndaGixbJhd3T5+GZs3kYsTw4aB3kvH874FwZO5+S+Qs/nGU9k4+/kHG9r9FLuZ2A2Yjy5ed\nbDiuCszZUPg7WM6u3b2h9ayC4+xCQFpc7hl7zpl80jkwJuY+RlcFPH0zDHxP+ezpCx4+8mfnGvkL\nc1zr5l4DAHB0l2MrJYrlADRN+xp4CLgihGiZY3s/YAFSDekrIcR7BZ1DCLEOWKdpWnVgHjKFwe45\nHXeaQSsG4V3Nm7WPrcVF51Jm1zaZZOFrSIiUbv7iC6nn42CF1gKXKTjZRgOOFHRgcrL0QPPmQXS0\njEOtXg19B8NmB3gMGb0wILMXpgHDkQ5AkQMTMn8qM8zjgvyiCgvzKKyCxcXWZyEpCqrdk8PQ5zDy\nxjyFc7oq4OkHHn5QOzDb2Hv4SiPvXL3klZeZDqi4jskKFKsfgKZpAcgMv6WZDkDTNEekuG4QMnfj\nAPIv2BGpaJSTZ4QQVzKO+wAIFUL8UdR1bd0PIC4lji5LunBdf529Y/fSuEb+JvWlxZEjUsZh/37o\n318a/5zJM7fCDWQ8fwUypl+Q5JUPUio/FzdvytDO/Plw7Zq8FXk1GAiCFZpcLEhC6u08hvxL6Ejh\nhaKVkswwz6dAFDLM8zwyzFNpdCvKHmMKJJ+VRv73J2XIpjCcquWYted4ZM7inbxsV1pfDKzaD0AI\nsUPTNN88mzsCp4UQURkXXAEMEkK8i7xbyDsgDXgP+Lk4xt/WGIwGHv7hYc7dPEf4k+FlZvzT0mQ4\nffZsqFZNps4//vit/60lAeuR0ZhfkcX5jZHhH0/gbYpIHoyNlUb/s88gMREe6A8PzIajrWA0Uu/K\nCxnaGQ70xLrquBWGf5C5+0uRYZ7uyHmSCvNYBSEgNRaSzkgjn/eRcqkYJ9HggT8zZvBepT5ke+B2\n1gAaADkbB0Yjl/cK4kVkXVA1TdMaCyG+sLSTpmnjyNBA9bZRZxIhBM9ueJYd53fw3SPf0d27e5lc\nd98+Oes/elQqdM6fDzVrlvw8qcjgwgpgAzKu3xApzTUcGWDI9CcNKCDZ5vx5Geb56itINcD906Du\nFNhWW57cHRiYccK+yAiGIg8msou2VJjntjGmZIRnMg17HmNvSsmxswbuDcHzLqjXVz5nPnYOhZTo\n/Od394bqrcvq09gFZbYILIT4GBnwLGq/xcguq7Rv394m/Srf2fEOyw4t453AdxjuP7zUr5ecLOWa\n58+Xap0bN8qwT0lIR663rkBqpCUgAwpPIyfn3ciRspmDEaGhjMjZEOCFF+DYMVi+HEQz8P8BbvSD\nrc5yotoP2UhlIJb1rBRYDvPMolKGeUq62Jp6pYBZ/Jn8s3idhzToVRrnN/IePuDoavk6bd4r88VW\ne+V2HEAMudtqNMzYVq5Zfmg5b0W8xejWownuEVzq19u6VWb4nD0Lzz0nk2oy0+aLwgzsQoZ3VgHX\nkFqOjyKNfm+K+AWHhsLTW//f3pmHR1Umfft+EggQlrDLGhLFBVwZEGUZBCMIAoLjiogiKOjojIoK\nal5RP+TDXUedF0VAcYwgiCCbLAqCMhoVRkWEAZTdKGERCAlke94/6rTpdLpDErpzmu66rytXp0+6\nz6luseo5VfX8CvI+BRJh+w4Y/QLENIX6W2FvC9mW3gNpCfLt1Vd8+BFx+t5pnqeAgURlmifQztac\nXyDhbP8r+QKfvrQ/VvG9oKbj3GufJo/VGlUsN+pCsTVcKfNQeKcGsMCrCFwFKQKnII7/a+BGa+36\nEzbKmP5A/9atW9++efPmEz1dmVm1fRU9/9WTzi07s+SmJcTFxoXsWgcOwAMPwNSp0tI5ebLUVY+H\nZ+7JDKTTcjeiyu7JxvSmHNmYhn+HfRPwu5S/yDlhab36UYnv1rlxSBHkZeBj5Nv3bNpq55KNLlGY\nDzkZkLMbsndLZ83xiq2x8V4r99OKr+JrJQVexSulUtYicFm7gKYjs5UaIhtEH7PWTjHGXIFs6YkF\nplprg3oPVZldQJv2baLTlE40im/EF8O/oF6N4IrKe49ebNhQNnMdOSJB4LHHZM9UafyAOP0ZyBah\nqkAfZKXfHynoloutR+DUo0ADP3/cDdblyTFhie/WOSgSLmoO3AXcRkSmefIOi1P3OPec3ZC9q/jz\no7+BLeM4xZ7/FidfvXFYd9OcrAS7C8hvItxauwipcp3U7M3eS993+xJrYlk0eFFInP+IEUXD1zMz\n5d/8uHESFALxE0VO/wckh58CPIL0jpTbyr3AbAuv/AbrGxE4iR/NS/4Cimbaev9kImsd361zFlkX\nbcXVNE95cu3e2ELJu/s6dl9n77uTFaTXvUZziG8Odc+TdE1886Jjn/YPUGxtBY06nfhnVk6YqJeC\nOJp/lIEzBrLz4E5W3LKCU+sFf5tqamqR8/dgrQxm9w0Au4GZSF7/a+dYFySzfA0yh6lc7EN69N8D\nllsoMMBhaLIQsq6DLD+60Q2yqcA9RZAp74jDQFhESdPXoXucuu+xffiXIo0h8M6Jfbju/P3l2gtz\noXG3wE49e5ekbGx+8fOZWKjRVBx5Qhto0rO4Y/c8Vokv3S4ttoY9YRkAvGoAIb2OtZZhHw5j9c7V\nvHfNe3RqGZpVyY4AWk6e45nIBq3piP6ORZoEn0VS8OVuhj2AOP2ZSFo6H6idCQWTod4yeGYw3DoU\nZsTCsHzI9fpnEJcP/wgH5++rUuTI4jLYOV4WZ+45nhfgOvWQdE1j4Cygm/O756eR1+/1EQ2LSh7Z\nVxa+e6Rk8bQgG9KHlXxtlVqOE28Bp/TwcerOCr5aY4gJwmYOLbaGPWUuArtBqGsAY1eMZdyqcUxI\nmcBDXR8KyTUKCmQ4S85ARN4lEVnUjoMGdeHC56VDvABxQYOQvP4Z5b3Q78CHiNNfhvi8ZAvJ38BX\nD0DOv+Hvf4OxY6Gu1yaXYC20K4xFmlb3Is56LzAUWVX7EosM6/Y3/AQkpeXttAM588ZI2qa8RX5/\nNYB4pGu5kp1aTgZkLIWMxbB9RuDXXfymOHaPo69axhYz5aQmqDWASGTat9MYt2ocw9sNZ0yXMSG5\nhrVw772O83+DopR7EjAZ9hnYiKgh3wCcRzmVEw4i23xnUrTNtxVwL9AqHV69FZZvgMsvhxe/hzZt\nSp5jcBoMDmYEyEGcuOcn0+e5v+P5fs9UkgJgJP6dfGk1jWDh4jDxglzY+4U4/IzFcOBbOV79FIit\nCQV+gmJ8Kzh1aOhtU05aojIArNi6gtvn305KcgoT+04Mmbrnc8/Bq69C7X1w2Nc3GZHN+ZlyOv1D\nyPbemcg4rlxkN8bfkXxRg5/h/lHw7Idw2mkwbx706xeg0+J4qZZ8ZCV+PAfufcy3SOr1gWmArLwb\nIoIUFzu/N/I63hApcfvbut8KeL6UL6cyqESd6qxtkLFEHP6vn4jipKkCjbrA+ROgWW8pvm6brrl2\npUKEZQoolPsANu7dSKcpnWhWuxmrh62mbvXQaH5Mnw433gjXXw8zp4P1438NgcuKxTiMzGCcicgw\nHEO6Dq9FhNc6AtlZMGGCRJ2qVUVC9L77oFppuwKS8J/TrgLURooJgahNScft+fF3vB5lFwkKo1RL\nZZKfA3tWFa3yD22U4zVbQdPe8tPkUv9pnIp2ASkRSVD3AbhFsGsAmUcyuWjyRRzJO0L6bekk1U0K\n2rm9WbFCsi6dOsNVy+C+AA0iflU3PWQhU9ZnIo22R5HuzGuRlX4npDHFWlGMGz0afvkFbrpJpsU0\na3YcK39CVuGBuJvADr0BoRf/cb04EXqshcOb4BfH4e/5FAqOyuanxt3F4TfrDbXP0F55pVxoDcCH\no/lHGTBjABlZGawcujJkzn/dOrjqKmjdFpKXiPNvh+T6vaWq/I7sPoI4+5mI889B8kS3IU7fV9Bn\n7VoZtL56NbRvL5O5OpXWyVSI3EL8E8kfBaIVImDmJhE6EizvMPy2vMjpH9kmx+ucCa1HitNvfAlU\nOc7OQEUJAlERAAptIUPnDuXLXV8y69pZdGzeMSTX2bULrrgCqreEOl/CtGrwMDLUb/rnkJoEO5pB\n4i8wfhsM7opkOT5CnP4C53ljRMXtOkROxjdzsmePbCCYMgUaNZLHoUNLmRSzH5gKTESqDk2Bschq\nfgzHEYRWTgRr4ffvxdn/shgyP5e++yq1oEkKtB3jCJklu22pEoVERQB4dPmjvLf+PZ7t+SxXt706\nJNc4eFCc//4WkLASvouTJMaNAGkweAQM9vaz1ZBm/++RlX8j4GbE6XfDf7o8L0+qyk88IToS990n\nbZ0JCQGsWotsIZuO5JC6UVKDvh4Rn2qpbI7th1+XObn8JdKyCVDvAmhzv6zyG3aGEGpNKUpZCMsa\nQDCLwFP/M5Xh84Yz4k8jeK3fayHp+MnNhT594NN6EDcD6leRfVgXel6QhP9aawxF6Z1LKD0cL10K\n99wDGzdC797w4osyh7cEx4BZSJrnS2RFPwTRqTm3Ap9OKYa/YmurG2D/N0Wr/P1ficRCXH1RsWza\nWx5rRLPEhlKZaBEY+OTnT+id1ptLky9lwaAFVI0N/nb9wkIYcjO8mwQ8KQ05c4BiJdgY/KsLlKUN\n6KefYNQoaec87TQZGtC3r5+i4A7gdWTDQSaylewuZGxXoDsEpVz4Si6AyCbEVHf68A006OgUb/tA\n/Q7B2VGrKOUkaovAaevSSP0klR0HRWehee3mzLxmZkicP8Dox+Hd/sD1cBPifksI2DZGNFR9KU1B\nICtL5kI+/zzExcmggHvv9WnrtMByJM0zzznWH3H8KfgfAaOUCVsouvVZzhzZrK2w4bmSkgu2QB47\nT4emPaGaP3VVRQlPIioApK1LY8T8EWTnFf1Pui9nHws2L2DwucHPa49/G54fALSDpyyMNn42da1A\narAe1WAPgWqt1op86Jgx0tZ5883S31+srfMQMA34X6S/qCEwGrgD6eBRykTuQXHunmHhHkef9bN0\n5xTmer3Y9z+gFwXZkHRDJRisKMElogJA6iepxZw/QE5+DqmfpAY9ADy9Cv6nF1SpIwrLV/pbbC8H\n+iHZmL8Cz1B6rfWbb6St84svoEMHmD0bLr7Y6wXrkdy+Z+JUR+f3a/Fz36EU5MKR7V4Ofmtxh+87\nrCSuHtRMlt21LQZKZ06tU+VYzUSYf6YobfoS77IYnKJUkIgKAJ60T1mPV5RHt8CTF0G1PTKSsYO/\nNO8niPNv7fzeGAkC/tizBx55RMaDNWokj7fc4rR15iEl5X8CKykaLH4XcNwU38lLWXa2WgtHfy2e\npjni5eizd1Fs1R4TBzWTxKk36Fjk3GudKs4+7ji7ws8fr5ILSkQRlgGgonLQiQmJbD9YcoWWmBCc\nFVoBcPt+eLM11Pg3rD0dzvInif4xkoo/HXH+gQZEedo6H39cBgaMGiXT4RMSgAykovA6oouTBDwN\nDENSPhGMP3379OHwy0dQrX5RuubINijIKf7eGs3EoTfuXuTYPY81moE5gbqIyhsrEUZEdQH5qwHE\nV41nUv9JJ5wC+h24+hgsrwbVJ8Pa7tDGX3xaCgygpPP3ngmZmCgiQfPmSVtnnz7S1nnmGcBqpKg7\nGxFj642s9vtQdi2dk4z8HBkMfngTHNoE65+E/ACSz1XrlFy5/5GmaaU7aBWFKO0C8jh5TxdQYkIi\n41PGn7Dz3wT0K4QtsVD1bvh0SADnvwRx/mcizt+zUPedCbl9OzzzDJxyCixYAH27I9vGrkN2htVF\nhorfiUSSCKAwT9QtD2+Cw5uLnP3hzZC9k4AF1mIYuOZ31cVRlCARUXcAoWApcL2F7EOQNwDmjoIr\nr/TzwsXAQKANkgLy7gZMSoLO24sPhHkE2N0UVl4PvImI+5+PiLANIvTa9iHAFkre3ePkD3k5+6yt\nxUcPVq0Ldc4QobPaZ0Dt053nrWHheQGKra1g4LZK+ziKcrISlXcAwcQCLwOjLNTdDbldYeJDAZz/\nIkRd4WxkGpdvK3iX7aJk7D0Q5l9AbAZS3L0GSfN0ppzTAU6c8soIWytDxD2O3dvZZ20RNUsPsfHi\n2OtdAInXFjn62mdIv3yglbwWWxWlUtAA4IdjiDueArTZBBvawyP3wB13+HnxQuAviPP/GBkd68tT\nMVDTZ8tvLHDQQMIORPLTBQINEwdo3rfkKt7zmHeo6BwxVaHWaeLYm17utZI/wym6ViCgabFVUSoF\nTQH5sAfx56uB/t/B/HYw5CaYNs2PL1sAXI1I7CzFv/NftQq6XuJ/U64FjIvf/9wk/6kWYiiuUWGk\nwFosVeP8XrMVxOg6QlHCiZM6BVTRNtAT5VukhpsJPPwdPNsBUi6FyZP9OP/5iPM/H3H+9fyccF06\nrOkFfw5wQePirl1rZXXtl0K44JkiZ1/rVBlSoihKRBGWYjHW2vnW2hEJAWWOg89sZN5KITD5v/BK\nV2jbVjbjxvmq9n6IOP8LkJy/P+f/69tQpwvcdwyOdQR82xNd0t0vLIAd78OSCwnYeRPfCto+CC0H\nQkJbdf6KEqGEZQCoTAqBx5Ey7PnABzvhgR5Qrx4sWuRHan8uorzQDln5l9g8+hscvRqa3AK5FrZO\nherpyKauVkiRtxWVPt+24ChsmQQL28Dn14oOzqnDpbjqjRZbFSVqCMsUUGVxBBFLnu08TtgPKZdL\nu/7q1dC8uc8b5iCt+u2Rnv9iwaEQmAp2NMT8Dk/GQo8l0CXF+btLIw5zD8KW12HjiyKbUL89dJ0F\nLa4SqeJTemixVVGilKgNADuQfP/3wPPAnUfh8oEiv79kCZx9ts8bZgM3IPI7i/Fx/huAkcBnsK4e\nDDLw1Bwv5+8COb/Cf1+CzROla6fJZdD2HTjl0uIFjeTB6vAVJUqJygCwGmnbP4Y08lxeCDfcDJ99\nBtOnQ/fuPm94H3H+HRHnX8fzh6PIiMUJYGvBGx3hjq9g8hTo378yPkpJDm+BDc/Cz9PA5kHLq2Xu\nbP327tijKErYEnUBYCqimp+EjFA5C7j/QZg1C557Dm7wlXWfhWzMvQhx/rU9f/gUWfVvAnsjPBoP\n4yeLdv+wYaH/IL7sXwM/Pg07Z4OpAqfeCm0ekJ21iqIofoiaAJAPPAi8BPQE3kOad156CV54QWT4\nR43yedN7SNr+YuAjHOe/zznTm0AysBie/g+Mf1hm9o4ZUymfB5BWzt+Ww49Pwa8fi1BamwfhzHt0\n/qyiKMclKgLAASSDsxS4F3gW+eCzZonT/8tfJAgU6/Wfgcx47Izs9q1tEcG2UciIrzHAWHjzPXj4\nYRg0yM9JQkRhAeyaI45//xqo3gQueBpaj4Q4nf+rKErZCMsAEMyNYBuBK4FtiLSDJznz2WcwZAh0\n7gzvvAOx3krL7wJDgK6I86/1E6LMuQwpBCwDzof58+H226FXL3jrLWeASwgpOApb35bZtIc3Q63W\n0HESJA/RXn1FUcpNxElBpAGpSJdPI+AwUAv4APHnABs2QJcu0LixtHs2aOBzgpuR3bsL8qDW88AT\nQFVEzvNOIFbeeNllcO65sHw51KpV8Q96PHIPwpbXYONLRa2cbR8qauVUFEXx4qSWgqgoacAIwKMh\nuQfZdvUURc4/I0Pmr8TFwUcf+Tj/d5ANAd2ABV9BzduAdUjP0CuAszFg/Xro1w9atoSFC0Pn/Mva\nyqkoilIBIioApFLk/D1Y4AXg78Dhw3DFFbB3L6xcCcnJXi98GxgKdM+HBQ9A/MuIw5+L7Bhw2LED\nLr8catSApUtlhm+w8W7lLMyFxGu0lVNRlKATUQEgkLTZDmT87jXXwLp1MoSrvbcvnQbcaqFHJszv\nBPFbkYlcT+LV9ymRo1cvyMoSlc+kpOB+gBKtnEPhrAegToRMBVMUJayIqACQCPgTN25pZSLj0qUw\nZQr07u31x7eAYRZSvoMPO0P8mUA6cGHxkxw5ImmfbdvkROedFxyjtZVTURSXiKgAMJ7iNQAQzc0/\nvS9NOo8/7rNHa2oB3BYDly2HD6+DGuOAeyjxtXhuH77+WuRBu3Urv3G+k7fOGwdVqsuK/49Wzqeg\n9R3ayqkoSqUQUQHAo2jj6QJKRHz7lOtg+HAYO9brxVO2w22toNcSmPsa1FiD7A/2obBQosbixfDG\nGzBwYPkN8zd568tbAOu0cr4OyTdrK6eiKJVKRAUAKK65uXAhDBggXT8TJ3oaZ7LgjUUw4jq4fDnM\nPQzVPyDgLN7Ro2WjwJNPwm23Vcyo71KLz7cFwEK1htBvo7ZyKoriChEXANLSIDVVmnUAEhNh5kyo\nWhVgAUz6HEY+Bb1/gDl/guolBP2LePZZeP55uPtueOSRihsVaPLWsX3q/BVFcY2IGgiTlibF3u3b\npbZqLezZA0uWZADXwmsLxPlfsR/mnFO68582TVb/110H//hHxfruC/Phx2cIPHkrsfznVBRFCRIR\nFQBSU2HAgDS2bk2ioCCGrVtb8eqrt9Kz51kwsQnc+Rr0LYQP6kNp6faFC6VokJICb79dMYmHA9/D\n0ovh2zFQvwPE+oyE1MlbiqK4TEQFgC5d0njjjREkJW0nJsaSlLSDYcPeIuvpB+Gvr0A/YHYMVCvl\nJF98AddeCxdcAHPmQLXSXuyHgmPw/VhY3B6yd8r0rd5fQ8c3ZNYuRh47TtJBLIqiuEpYagF5icHd\nvnnz5jK/b9euJFq08NkJ8Opd8LdXRRFuJqU7/x9/hK5dRR9i9WoRCyoPe9MhfTgcXA9JQ6D9i1Ct\nwfHfpyiKEkTKqgUUlncA1tr51toRCSUmspdO8+Y7IG0QJG2FmAKovw/+9ip2wFwZ7FKa89+5UyQe\nqlWTjV7lcf752bD2fljWGfIOwiULofPb6vwVRQlrIqoLyLx7N4yYANk15cCB+hCbj7lqJcSV0r+/\nf784/0OHROKhmEjQcfjtU0i/DbJ+kk1c7Z6W3byKoihhTljeAVSY1P9f5Pw9FFSBx8YFfk92tkg8\n/PwzzJsH559ftmvlHYKv7oBPesjzlBXQcaI6f0VRThoi6g6AHQFkmQMdz8uTNs/0dBkPdsklZbvO\n7kXw9UjI+QXOuh/O+39QJb5iNiuKorhEZAWAQGpw/trtrZVpXgsXwmuvyVzI43FsH6y5F7a9Awln\nQ9fZ0LDjCRqtKIriDpGVAhqPqL95E+8c9+Whh2Sz1xNPwMiRpZ/XWtgxCxa2he0z4Jyx0HuNOn9F\nUU5qIusOwJ8a3Hiv4x5eeAGeeQb++ld49NHSz5mTAV/fJUPY67eHHsugXpCkoBVFUVwksgIAFFeD\n88c778D994u888svB5Z4sBa2ToM190FBDlzwNJw1CmIi7ytTFCU6iS5vtngx3Hor9OghgSA2gBDb\nke3w1UjIWAKNusJFU6DOGZVrq6IoSoiJngCQng5XXw3nnANz5/qXeLCFMoD924cACx1ehdPvBBNZ\npRJFURSIlgCwcSP07QtNmsBHH0EdP736hzbJhq7Mz6BJL7hoEtRsVfm2KoqiVBKRHwB27ZJdvrGx\nIvHQpEnxvxfmw8YXYN1jEFMdLn4Tkm+pmPyzoijKSURkB4ADB2QC/IEDsHIlnHaaz9+/h/RhMpO3\nxVVw4T91ELuiKFFD5CW309IgKUk0/Js2lfTP3LnQrl3RawqOwfePeUk2z4Q/z1bnryhKVBFZdwCe\nkWDZzvzdY8cgLg4yMopes/crWfUfXA9JN0H7l1S1U1GUqCSy7gBSU4ucv4fcXDmenw1rH4Blnbwk\nm/+lzl9RlKglsu4AdgQYvh6/HRad50g2j4R2z6hqp6IoUU9kBYDERGi+Ha4DGgL7gAzgXOfvKSvg\nlO5uWacoihJWVFoAMMa0Ae5BXPMn1tqJQb/I+Csgd2LR5K+GQAPAngdXfKGSzYqiKF6UqQZgjJlq\njNljjPnB53hvY8x/jTFbjDEPlXYOa+0Ga+0dyPq8S8VNLoWai0qOfTRAzYPq/BVFUXwoaxH4LaC3\n9wFjTCzwT6AP0BYYZIxpa4w51xizwOensfOeK4GFwKKgfQJvsgPUAAIdVxRFiWLKlAKy1q4yxiT5\nHO4IbLHW/gxgjJkBDLDWTgD6BTjPPGCeMWYh8G5FjQ5IfCJk+5kIE+9vIoyiKEp0cyJtoM2BPk0c\nrQAABUlJREFUnV7PdznH/GKM6W6MedkY8zql3AEYY0YYY74xxnyTmZlZPovOHw+xPqme2Hg5riiK\nohSj0orA1tpPgU/L8LpJwCSADh062HJdJNkZBPBdqqR94hPF+SeXNiBAURQlOjmRALAbaOn1vIVz\nzF2SB6vDVxRFKQMnkgL6GjjdGJNsjIkDbgDmBcMoY0x/Y8ykgwcPBuN0iqIoih/K2gY6HfgCONMY\ns8sYM9xamw/cDSwBNgAzrbXrg2GUtXa+tXZEQkJCME6nKIqi+KGsXUCDAhxfRKhaOhVFUZSQElli\ncIqiKEqZCcsAoDUARVGU0GOsLV+nZWVijMkE/OzsKhMNgb1BNCdYqF3lQ+0qH2pX+YhUu1pZaxsd\n70VhHQBOBGPMN9baDm7b4YvaVT7UrvKhdpWPaLcrLFNAiqIoSujRAKAoihKlRHIAmOS2AQFQu8qH\n2lU+1K7yEdV2RWwNQFEURSmdSL4DUBRFUUoh4gJAoOllbmOMaWmMWWGM+dEYs94Yc4/bNgEYY6ob\nY74yxnzn2PWE2zZ5MMbEGmP+Y4xZ4LYt3hhjthlj1hljvjXGfOO2PR6MMXWNMe8bYzYaYzYYYzqF\ngU1nOt+T5+eQMeZet+0CMMbc5/yb/8EYM90YU91tmwCMMfc4Nq0P9XcVcSkgY0w3IAt421p7jtv2\neDDGNAWaWmvXGmNqA2uAgdbaH122ywA1rbVZxpiqwOfAPdbaL920C8AYMwroANSx1vodMuQGxpht\nQAdrbVj1jxtjpgGfWWsnOwKN8dba3922y4MzRXA3cJG1tqL7e4JlS3Pk33pba22OMWYmsMha+5bL\ndp0DzEAGbuUCi4E7rLVbQnG9iLsDsNauAva7bYcv1toMa+1a5/fDiIBewAE6lYUVspynVZ0f11cF\nxpgWQF9gstu2nAwYYxKAbsAUAGttbjg5f4cU4Ce3nb8XVYAaxpgqQDzwi8v2ALQB0q212Y7g5krg\nL6G6WMQFgJMBZ7xmOyDdXUsEJ9XyLbAHWGatDQe7XgJGA4VuG+IHC3xsjFljjBnhtjEOyUAm8KaT\nNptsjKnptlE+3ABMd9sIAGvtbuA5YAeQARy01i511yoAfgD+bIxpYIyJB66g+NyVoKIBoJIxxtQC\nZgP3WmsPuW0PgLW2wFp7ATLUp6NzG+oaxph+wB5r7Ro37SiFrs731Qe4y0k7uk0V4E/ARGttO+AI\n8JC7JhXhpKSuBGa5bQuAMaYeMAAJnM2AmsaYm9y1Cqy1G4CngaVI+udboCBU19MAUIk4OfbZQJq1\n9gO37fHFSRmsAHq7bEoX4Eon1z4DuNQY8467JhXhrB6x1u4B5iD5WrfZBezyunt7HwkI4UIfYK21\n9je3DXG4DNhqrc201uYBHwCdXbYJAGvtFGtte2ttN+AAsClU19IAUEk4xdYpwAZr7Qtu2+PBGNPI\nGFPX+b0G0BPY6KZN1tqHrbUtrLVJSNpgubXW9dUZgDGmplPEx0mx9EJu213FWvsrsNMYc6ZzKAVw\ntcHAh0GESfrHYQdwsTEm3vl/MwWpy7mOMaax85iI5P/fDdW1Km0ofGXhTC/rDjQ0xuwCHrPWTnHX\nKkBWtUOAdU6+HeARZ6iOmzQFpjkdGjHIZLewarsMM04B5ojPoArwrrV2sbsm/cHfgDQn3fIzcKvL\n9gB/BMqewEi3bfFgrU03xrwPrAXygf8QPruCZxtjGgB5wF2hLOZHXBuooiiKUjY0BaQoihKlaABQ\nFEWJUjQAKIqiRCkaABRFUaIUDQCKoihRigYARVGUKEUDgKIoSpSiAUBRFCVK+T/1VOldU++H8gAA\nAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1bbc8472f60>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "from random import *\n",
    "from pylab import *\n",
    "\n",
    "def Production_Liste(n) :\n",
    "    return [uniform(0,1000) for k in range(n)]\n",
    "\n",
    "def Differents_Tri(L) :\n",
    "    print(\"Liste de départ :\")\n",
    "    print(L)\n",
    "    print(\"----------------\")\n",
    "    print(\"Tri Sélection :\")\n",
    "    print(Tri_Par_Selection(L))\n",
    "    print(\"----------------\")\n",
    "    print(\"Tri Insertion :\")\n",
    "    print(Tri_Par_Insertion(L))\n",
    "    print(\"----------------\")\n",
    "    print(\"Tri à bulles :\")\n",
    "    print(Tri_A_Bulles(L))\n",
    "    print(\"----------------\")\n",
    "    print(\"Tri fusion :\")\n",
    "    print(Tri_Fusion(L))\n",
    "    print(\"----------------\")\n",
    "    print(\"Tri fusion récursif :\")\n",
    "    print(Tri_Fusion_Rec(L))\n",
    "    print(\"----------------\")\n",
    "    print(\"Tri maximier :\")\n",
    "    print(Tri_Par_Tas(L))\n",
    "    print(\"----------------\")\n",
    "    print(\"Tri_Rapide :\")\n",
    "    print(Tri_Rapide(L))\n",
    "L=[randint(0,100) for k in range(300)]\n",
    "#Differents_Tri(L)  \n",
    "\n",
    "def Temps_Calculs(n) :\n",
    "    \"\"\" on forme les listes des temps de calculs sur des listes de taille 1000*k lorsque k varie de 1 à n \"\"\"\n",
    "    LX=list(range(1,n+1))\n",
    "    LY1,LY2,LY3,LY4,LY5,LY6,LY7=[],[],[],[],[],[],[]\n",
    "    for x in LX :\n",
    "        L=Production_Liste(100*x)\n",
    "        t_0=time.clock()\n",
    "        Tri_Par_Selection(L)\n",
    "        t_1=time.clock()\n",
    "        Tri_Par_Insertion(L)\n",
    "        t_2=time.clock()\n",
    "        Tri_A_Bulles(L)\n",
    "        t_3=time.clock()\n",
    "        Tri_Fusion(L)\n",
    "        t_4=time.clock()\n",
    "        Tri_Fusion_Rec(L)\n",
    "        t_5=time.clock()\n",
    "        Tri_Par_Tas(L)\n",
    "        t_6=time.clock()\n",
    "        Tri_Rapide(L)\n",
    "        t_7=time.clock()\n",
    "        LY1.append(t_1-t_0)\n",
    "        LY2.append(t_2-t_1)\n",
    "        LY3.append(t_3-t_2)\n",
    "        LY4.append(t_4-t_3)\n",
    "        LY5.append(t_5-t_4)\n",
    "        LY6.append(t_6-t_5)\n",
    "        LY7.append(t_7-t_6)\n",
    "    figure()\n",
    "    semilogy()\n",
    "    plot(LX,LY1,color=\"red\",marker=\"o\")\n",
    "    plot(LX,LY2,color=\"blue\",marker=\"o\")\n",
    "    plot(LX,LY3,color=\"green\",marker=\"o\")\n",
    "    plot(LX,LY4,color=\"yellow\",marker=\"o\")\n",
    "    plot(LX,LY5,color=\"magenta\",marker=\"o\")\n",
    "    plot(LX,LY6,color=\"cyan\",marker=\"o\")\n",
    "    plot(LX,LY7,color=\"orange\",marker=\"o\")\n",
    "    legend(('Tri sélection','Tri insertion', 'Tri à bulles','Tri fusion','Tri Fusion Réc','Tri maximier','Tri rapide'),loc='upper left', shadow=True)\n",
    "    show()\n",
    "Temps_Calculs(9)       \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans l'ordre d'arrivée :\n",
    "    \n",
    "$\\quad$  $\\bullet$ tri rapide\n",
    "\n",
    "$\\quad$  $\\bullet$ tri fusion\n",
    "\n",
    "$\\quad$  $\\bullet$ tri fusion récursif\n",
    "\n",
    "$\\quad$  $\\bullet$ tri maximier\n",
    "\n",
    "$\\quad$  $\\bullet$ tri sélection\n",
    "\n",
    "$\\quad$  $\\bullet$ tri insertion\n",
    "\n",
    "$\\quad$  $\\bullet$ tri à bulles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici ce que cela change lorsque l'on tente de trier une liste déjà triée $L$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAD8CAYAAAB+UHOxAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsnXt8U/X9/58nSdM2Ta+Wi1AKBeQmlftVKIUBoiBOBs6J\nyoaCzjtjTrFs6CZ4d17nZF4mjOlv8EWn8zIuctUhUBFBuRco5U4LvSVNmuT8/ngnTdImbXpP4Twf\nj/NIc3KSnKTt6/0576uiqioaGhoaGpceuuY+AQ0NDQ2N5kEzABoaGhqXKJoB0NDQ0LhE0QyAhoaG\nxiWKZgA0NDQ0LlE0A6ChoaFxiaIZAA0NDY1LFM0AaGhoaFyiaAZAQ0ND4xLF0NwnUB3Jyclqp06d\nmvs0NDQ0NFoU2dnZ51RVbVXTcWFtADp16sT27dub+zQ0NDQ0WhSKohwN5TjNBaShoaFxiaIZAA0N\nDY1LFM0AaGhoaFyihGUMQFGU64Hru3btWuWx8vJy8vLyKCsra/oT0wiJqKgoUlJSiIiIaO5T0dDQ\nqAYlnOcBDBw4UK0cBD58+DCxsbEkJSUBEM7nfymiqioFBQUUFRXRpUsXFEVp7lPS0LjkUBQlW1XV\ngTUdF5ZXANVRVlZGx44dKSkpwWq1NvfpaARAVVXy8/PZuXMnkyZNIjIysrlPSUOjRbBsGWRlQW4u\npKbCwoUwfXrjvV+LMwAANpsNi8WiuRjCGL1eT25uLlu2bGHUqFHNfToaGmHPsmUwezZYLHL/6FG5\nD41nBFpkENjpdF60roWioiLefffdi8K1ZTabOXv2bHOfhoZG2FNeDr/7nVf8PVgsckXQWLRIA9Cc\n4lhQUEBmZiaZmZn06tWL3r17V9y32+1+x06bNo3i4uKQX9tms/G73/2OESNGVBi4RYsW8de//rXW\n53n+/HnefffdivvHjx/njjvuqPXr1JeLwZBpaNQXhwOOHIH16+Hdd2HBApgxAzIyxNUTFQUnTgR+\nbm5u451Xi3QB1QbjihWYnnwS3fHjuNq3xzJ/PvapU+v8eklJSaxfvx6AZ555hpiYGO677z6/Y1RV\nRVVVli9fXqvXjoyMrJPYB+L8+fO89957/OpXvwKgffv2vP322w3y2hoaGv44nSLgR47A4cNy6/vz\nsWNyjAdFgZQU6NQJRo+W29dfh/z8qq+dmtp45x2WBqC6NNCasQLFgBPjis8xz1mA4g4W6/PyMM+Z\nQwnUywgEIicnh1tvvZX09HR27drF//3f/zF+/Hg2b95MfHx8xXEOh4P777+f3bt3o6oqt99+O7Nn\nz+bQoUM8+uij5OfnYzKZeOmll6j8+YMdc/r0aebOnUtubi6KovDiiy/y2muvcfDgQTIzMxkzZgy3\n3norM2fOZP369VitVn7729/y/fffYzAYWLhwIcOHD2fp0qV8+eWXlJSUcOTIESZPnszvf//7Bv2e\nNDTCgdoGW10uOHWqqrB7bnNzxY3jS7t2IuxXXy23nTpBWprcdugARqP/8d26wZq3lrHgp1mkJueS\ney6VJz5ayNg7Gy8KHJYGQFXVT4BPBg4cOKu640xZWRh27fLZ4wIcFfcM2d+j2PzdMorVivnBB3Es\nWRLwNR3p6VgWLqzTeR84cIDXX3+dfv36BT1m586dFBQUsGnTJgAKCwsB+M1vfsNLL71EWloa33zz\nDY8++igrVqzwe26wYx555BEyMzO58847cTgcWK1Wfv/733P48OGKq5WcnJyK1/nb3/6G0Whk06ZN\n7N27l5tvvpmtW7cCsHv3br788ksMBgNDhgzhzjvv5PLLL6/T96GhEY4EC7YWFsKAAYFX8UePgs3m\n/zpt2oiYDxwI06b5C7zHrVMbpg9fxs+ZjUGRE+vU6ih/u3M2huEAjWMEwtIA1B2n/91K4u/dbwu8\nv5506tSpWvEHSEtL4+DBg8ybN49x48YxevRoCgsLyc7OrnDXgFwp+FLdMV999RV/+9vfADAYDMTG\nxlYbfN2yZUuF26pHjx60bduWw4cPAzBq1ChiY2MBuOKKKzh+/LhmADQuKh55JHCw9d57/fclJ4uY\n9+kDN9zgL/AdO4LJ1AAno6pgOwfFByH7wQrx92BQLLAzC9I0A1CFqiv1k373EvqOR593ksq4UlIo\n+vjjBj+fmJiYGo9JSkpiw4YNrF27lrfffptPPvmEBQsW+MUWAqGqarXHNFRWlG/Ovl6vr2KINDRa\nEufOwfbtsG2bbNu3w8mqklDBJ594Bd69Dqo/qgplp0Tkiw9CyUH/n8uLqn++pfGiwC3aAFRFj+9V\ngGX+g5jnPI5i9baNUKOjscyf3wznJpw7d47IyEhuuOEGOnfuzEMPPURCQgJt2rTh008/ZeLEibhc\nLn788Ud69+5d8bzqjhkxYgR///vfufPOO3E6nVgsFsxmMyUlJQHPYejQoaxYsYLhw4ezf/9+Tp8+\nTVpaWoUbSEOjJVJcDNnZ/mLvvrBFUaB7d/jJT+DTT+H8+arP79gRJk2q45urLrAcryruxQeh5BA4\nSr3HKnqISYPYrtBqOJi7ys9bZ4M1QCqQqfGiwBeZAYgFCgFJPbRPnUgJYHryVXTHTzRIFlB9OX78\nOA899BCqqqIoCn/4wx8A8cs//PDDPPvss9jtdqZNm+ZnAKo75umnn2bOnDm89957GAwGXnjhBfr3\n70+fPn0YOXIk48aN49Zbb614nVmzZjF37lxGjhyJwWDg9ddfx1g5IqWhEcZYrbBzp1fst22Dfftk\nsQ1e3/zdd8OgQeLbj4uTx5Ytq2Ow1eUEy7HgIu/06U+mM4K5s4h7mzEi8B6hj0kFXYAi1r7PihFw\n+riB9CboU7eYZCi0uF5Ae/bsISUlBYvFgsEQyH55s4CEaCChcU9UowqHDx9mx44dJCQkMG3atOY+\nHY0WTHk5/PCDv9jv3i259QBt24rIDxzovW1V3Sysw8twfD3bz9/uUE0Yhi+GjjdB6dEAAn8QSnLA\n5ZPqo4/yirqvwMd2hegU0Olr/2EPLxOfvyVXVv59FtbJ/3/R9gKqmWj3BnAOKK/mWA0NjXDC5ZKV\nvK/f/rvvwNP8NzFRBP53v/MKfvv24uIJmZ1ZgYOtW34JW2aA6pNMYjCLoMenQ8qN/kIffTkoDVxL\nmza90QK+gbgIDYAvJsQlVA5ofYM0NJqa6vLtVVXSLD3++m3bxIfvKZ6PiYH+/eGee7xi36VLLcUe\nwGGFCzshfxsUbAdLkGmJqgOunO+/oo9qXYc3bDmEpQGoXyGYL9FAEVCK5gbS0GhaAuXb33EHrFgh\nPvzt272Vr0ajpFvedpvXjdOzJ+hr60VxlcOF3VCwzSv4F3aLuANEtQV9NDgDdBI2dYQ+f6rz522J\nhKUBCLUQrGYUxAhYgHj3fQ0NjcbGYoG5c6vm29ts8NFHkJ4uufWDBsmWnl61MrZGXE4o2isi7xH7\n89+By13nY0yCpIHQ6xG5vWwQRLeDI/9s8mBruBKWBqBhMSEGwALUnKevoaFRO1QVDhyALVtk++Yb\nydBxOgMfryjw/fd1eJOSQ16hz98G57/1plcazJA0ALrf7xX7mLTA7huPj70Bgq0tnUvAAES4N80A\naGg0BBcuwNat/oJfUCCPxcbC4MHw6KOweDEEKkivsbmZqoIlz+3G2e69Lb8gj+ujILEfdJ4pQp80\nEOK61y4g28TB1nDlEjAA4A0G24H65bsXFBQwZcoUAM6cOYNOpyM5ORmAVatW+eXTT5s2jXfeeaei\ntUJN+xuKI0eO8O2331acZ3Z2NitXrmRhHXscaVy6OBySgukR+y1bYO9eeUxR4MorYcoUGDoUhgzx\n99v37Blivr31tL8bp2AblJ1xv4kBEq6S9MykQSL48b0C59Fr1JqLsA7AnxUrjDz5pInjx3W0b+9g\n/vwypk4N0iOoltTUDlqna/pxCw6Hg6+++oq33nqLpUuXNvn7e9DqAFomp055V/VbtkhmTqnby5Kc\nLELv2QYN8hZXBSRgvn00hl4PgDHeJyvnmDyo6CCup3dVnzQIEq+SFb9GrbiE6wC8rFhhZM4cM1ar\n+AHz8iKYM8cAlDSYEfAQajtogPT0dDZv3kx+fj633347AwYMYPv27aSkpPDee+8RFRXFG2+8wdKl\nSzEYDPTq1Yu//vWvlJSU8Oijj7Jv3z4cDgePPPIIEyZMYOnSpaxatYqioiJ0Oh1FRUXk5OSQmZnJ\nLbfcQvfu3SsMQn5+Pg888ADHjh0jJiaGF198kZ49e7Jo0SJOnz5NTk4OJ06c4J577mmWATIaTYfN\nBjt2+K/uj7ozJCMioG9fmDnTK/hpQVzqASkvgR0PB8i3t8KeZ+SOuSu0GuH12Sf2gwhzw31AjRpp\n0QYgK8vErl3BP0J2tgGbzf8v1mpVePBBM0uWBG5ylp7uYOFCS8DHaiKUdtCVOXjwIIsXL+bll19m\nxowZfPbZZ0yZMoVXX32V7777DqPRWNEy+vnnn2fMmDG89tprXLhwgfHjx5OZmQnArl27WL9+PQkJ\nCWzYsMHvCmDDhg0V7/fUU08xYMAAli1bxrp167jvvvtYu3YtIPMGVq5cSWFhIcOHD+eXv/wl+lrn\n4Wk0BzX1t/fk3PuK/XffgWeIXWqqiPyDD8ptv34htDN22qH0MBTth2L35vk5UE+bChSYmg/GxHp+\nao360qINQE0E6/rcSN2gQ2oHXZm0tDR69eoFQJ8+fTh2TC6He/Towa9//WsmTJjAddddB8D69etZ\nu3Ytr7zyCiAjJPPy8gDIzMwkIaHmWodvvvmG999/H4DRo0dz3333Ueq+xh8/fjxGo5FWrVqRkJDA\nuXPnaNOmTa0+j0bTEyjfftYs8d3HxnoF/4zbrW4yifvmoYe8vvt27YK8uKfJWWWBL9ov4u9bNRuZ\nDLHd4PLxcrv3RWl1XBlTqib+YUKLNgA1rdT79k0gL6/qCjYlxcnHH9fQgrUOhNIOujLB2i8vX76c\nr776iv/+97+89NJLbNy4EVVVWbJkCWlpaX6v8b///a9O710Z3wC2Xq/HGSyPTyOseOyxqvn2Vis8\n9ZT83L07XHut15XTuzdUCZ/Z8gOv5IsP+BdN6U0Q1w2S+kPHm+Xn2G4QewVEJvm/pilVy7cPc1q0\nAaiJ+fMtfjEAgOhoF/Pn5xPOH93pdHLixAkyMjIYOnQoK1euxGKxMHr0aN56662KbJ7vv/+eq666\nqsrzQ2kF/dBDD7FhwwYuv/zyBjEeGk2H0yl59Js3w6ZN4vb5xfBlLLrJm23z2L8W8sH/ppOfL/1z\nAMmZLz4IJyqt5Iv3g73A+waKQTpZxnaDtmPl1iP00e1CDwRo+fZhT/iqYAMggd4SnywgF/Pnn2Pq\n1LNAG6Dps3RCweFwcNddd1FSUoLL5eKee+4hNjaWhx9+mKysLEaOHInL5SItLY1//OMfVZ6fnp6O\n0+lk1KhRTJ8+ne7du1c89uijj/LAAw+QkZFBTEwMr776alN+NI06YLVKNs6mTSL6X38NRe4L2NRU\n+GXmMl67fTYxkd5Rgu/MvoOpwz8n8UCsd1VvyfN/YVOKiHrqTT4r+W5g7tRwaZZavn1Y02RpoIqi\ndAaygHhVVUNqyN8QaaBVcQBngTi0wrDGQ0sDrTsFBSLyHsHfts07cLx3bxgxAkaOlNvUthcoW96N\nKCXICFBjIsR29wp8hdB3BYP293+x0qBpoIqivANMAs6oqtrbZ/8E4GVkFNdbqqo+Hew1VFXNAe5Q\nFGVFsGOaBgNSGVyKZgA0woHcXK87Z/Nm6XUPkoo5aBDMmSOCP3w4JEWfhrOb4MxG2L0RNn9PlBJs\nEafA1IIgj2lohO4C+jvwGrDEs0NRFD3wOjAOyAO2KYryMWIMnqr0/Jmqqp6p99k2GDHABRqiMlhD\noza4XPDjj/6Cn+se+RobKyJ/880i+IMGQbQrV8T+zEb4eiMU7ZOD9SYZJ5j+BBx4HcpOV32zRhwl\nqHFxEJIBUFV1o6IonSrtHgwcdK/sURTlA+AGVVWfQq4WwpgopDNoKZoB0GhMbDbpce8R/K++8s6j\nbdtWhP63vxV3zlXpKnrLAa/gr9oo06kAIuKh1UjofAe0zpAsHI+f3txZy7bRqBP1CQK3B4753M8D\nhgQ7WFGUy4CFQD9FUea5DUWg42YDswFSa+waVVcUpD9QKeAiXIPBGuFHTQVXRUXiv/cI/tat3mlW\n3btL3xyP/75zmgulcLeI/dmN8PFG70o+qjW0yoAec0Xw43sHHzGoZdto1JEmywJSVTUfuDuE4xYD\ni0GCwI13Rh4DYEWLBWiEQrCCqy1bJDNy0yZJz3S5pCFa//7w61+L4F99NbROLoeCHSL2eRthx2aw\nuy8HTB2g7TgR+9YZEqitzSQqLdtGow7UxwAcBzr43E9x76s3DTcRrDoMiPun6YPB3333HUVFRWRk\nZDTp+2rUj6yswAVXr70m1bVDh8Lvfy+CP2QImKPLIH+rN2B77mtv//rYbtDhZ17Bj+nY9B9I45Kn\nPgZgG3CFoihpiPDfDNzSECfVcBPBasJEbYPBDdEOulevXtx222107949aKuFiRMn8vTTT5Oenh7S\neTkcDrp160ZOTg45OTnMnDmT9evXh/RcjeAUFsL69bBmjaz4gxVcXbgAERTDuf+J4P9vI+R/Ay53\ns52Eq6Dzr0TsW42E6LbN+rk0NCD0NND3gUwgWVGUPGCBqqpvK4pyH/BfJPPnHVVVf2i0M60jK/at\n4MktT3K8+DjtY9szf+h8pnb3lCHUPhiclJRUIaw1tYNevnx5wNcwGo28+OKL7Nu3T+u1E2bYbOLS\nWbNGtm3bpPLWZILbRy3jLzOqFlzd8ZN/ErH2rEyoUp2g6N3TqR4QP36rq6u2SdDQCANCzQL6RZD9\nnwGfNegZ0XAuoBX7VjBn3RysDullklecx5x1cwDcRqDhgsG1aQc9Z84cvv/+e8rKyvjpT3/Kww8/\nHPA1P/jgA+6//36cTievvPIK/fr1Y9GiRSQlJXH33RJO8bSKaN26dcDXcDgcPP7443zzzTfYbDZm\nzZrFbbfdxsmTJ7nzzjspLS3F4XDw4osvMnjw4Dp//paKywW7dnkFf+NGcfPodDLZat48GDtW3DuO\nFfOIqdTeOCrCxpjun4EhA3rNkxV+8jCtrbFGiyAsW0GE6gLK2pTFrrO7gj6efTobm9O/9afVYeXB\nLx9kyQ+ekgYVKEcuYvSkt0pn4ci6pc+F2g76D3/4A4mJiTgcDn76058yefJkv3YNHmw2G+vXr2fj\nxo3MmTOnTi6dJUuW0KpVK1avXo3NZmPChAmMHj2alStXcs011/DAAw/gdDqxWq01v9hFQm6uV/DX\nrvV2yezRQ/rfjx0LmZkQH+uQgSUnV8PG1UQqxwK+nqIoMHZDwMc0NMKZsDQADUVl8Q+8X0FW/i7E\nCNSdUNtBr1y5kn/84x84nU5OnTrFvn37AhoAT6whIyODs2fPBm3wVh3r1q1j//79fPjhhwAVw2L6\n9u3L3LlzKSsr47rrrqN37941vFLL5fx5WLfOK/oHDsj+tm1h/HgR/J/8BFLaq9Is7dRq2LkGTn8J\n5YWAIsNKDHHgCNBFViu40mgglm3eTFanTuS2a0fqiRMsPHKE6SNGNNr7haUBCNUFVNNKve97fckr\nzquyPyU2hY+nfOyzx4oEg5OAyCrHh0ooXTUPHTrEm2++yerVq4mPj+fuu++mzJMoXgmlUhqgoijo\n9XpcLlfFPlsNww1UVeW5554LmHH08ccfs2rVKu69917uu+++i6ZnT1mZ5OJ7BD87W1w9ZrOs7O+9\nV0S/Vy9QbOfg9Fo4vgayV3sLr2I6Quo0Sc1sMwaikuHwMq3gSqPRWLZ5M7P79cPi1pGjKSnMTkyE\nzZsbzQiEpQFoqCyg+UPn+8UAAKIN0cwfOr/SkdFAEWChPgYgFIqLizGbzcTGxnLq1CnWrVvHmDFj\nAh770UcfMWzYMDZv3kzr1q2JiYkhNTW1whX07bffcvx49Zm3Y8aM4Z133mH48OEYDAYOHDhASkoK\n586do127dsyYMQOr1cquXbtarAFwuWS6lUfwN20SI2AwiO/+D38QwR88GCJ0ZXB2M5xaA1+shvM7\nAFUqbduMgV6PiOibu1TNw9cKrjQamAvAISAHuC89vUL8PVhiYsjq1InG+gsLSwPQUHiyfYJnAfkS\nTVNUBvfp04fu3bszdOhQOnToUG3g1WAwkJmZWREEBpg8eTLLly9nxIgRDBgwgI4dq88fnzFjBnl5\neRWjI5OTk1m6dCkbN27kjTfeICIigpiYGN54440G+4wNQU0Vtzk5XsH/8kvIz5f9vXvD3XeL4Gdk\nQKzZBRe+Fz/+ptXSSM1ZJj3vWw2Hq/4oPe+TBoIuhH8HreBKoxY4kRYJh4Acu52c4mIO2e3k6PUc\nMps5bzJ5D66ULOIhN+i4tvrTZO2g60LjtIMOhhM4A8QCWgZHfalPO+jKFbcA0dFwxx2SprlmDRw+\nLPtTUkTsPX78tm2B0mPixz+1Gk6tBZu7VXL8lSL2bcdB61Fapo5Gg1CCrOAP2WzkFBZyqKyMHCAn\nOpojiYmU++hUhN1OpyNH6JyTQ+cjR+hSUEDnsjK6KAqTZs3iWEpKldfvmJfHkQD7q6NB20E3NU1T\nCVwZPVILYEEzAM1LdRW38fEwejTMnSui360bKI4iOL0Ojq2G7Wu8HTOj2sLl14jgtx0LpsZbSWm0\nLGoTbHUBJ4GcsjIOFRSQY7GQ43JxKDKSnPh4znhmcUdGQuvWJBYU0Dknh36HD/Oz/Hy6lJbSWVXp\nEhlJSlIS+tRUuPJKGDdOeoa4eWrzZmYnJvq5gUylpSw8ckRWOo1AWBqApqsErkwMcB6w0dixAI3A\n5ORUX3F77hwYdOVw7hvx469eLRW3qlMCsq1HQde7RPTjr6xdPx2NS4JAwdZZSUkc37qVXm3bipvG\n6STHYOBQXByHk5Mpi4qCqCho1w6d00lqbi6dc3K44fRpOpeU0MXhoHNEBJ3j4khs1w46dYJ+/fwE\nviamjxgBTZwFpLmAqnAauRJIrOlAjWqojQvo/HlYvhyWLJF2yb8Yvoy/3emtuAWw2qP4dNc0pk6+\nAKfXg6MYFJ347tuOky15KOg1w60RGBdw1GplSEkJZ1u1qvZYc3ExXXJy6Hz6NF0KC+lst9NZp6NL\nTAyprVph7NhR/I268Owk3KJdQM2LCfHqaW2iGxO7Hb74QkT/k0/kfq9e8NRTcE/7LGL0/j6gaGMZ\nUwcshcIu0Gk6XD4O2oyWkYcaGj6UAfuLith78iR7SkvZoyjsjY9nX7t2lEVHS0ApEC4X/1uzhi6J\niSSnpKCkp0OfPk167k1NWBqA5okBePAYAC0W0NCoqvTWWbIEPvhAMndat5aWybfdBv3Ti1BO/Ae+\nPhrkFRSYfLBJz1kjfClQVfbk57P3zBn22GzsNRjYk5TE4csvR42Lg7g4FJeLTkeP0jMvj5/s2UNP\nl4v5Q4ZwOkDrlI4nTjB0/Phm+CTNR1gagOaLAYAWDG54jhyBf/wDli6F/fvFlXrDDXD77TAuI5+I\n0/+GYyth5WrpnqnoQHVVfSGt4vaSwwUcczrZc/o0e8+fZ4/Dwd6oKPa0asXZpCRITobkZCLLyuh+\n8CCDfvyR27Zvp6ei0CMhgW4dOhCdmgppaRWvGb15M7NjYpo02BquhKUBaH6CB4Mboh30ypUree65\n57j88stZuXJlrc5s4cKFZGRkMHLkyFp/qqZEVWW4+Y8/wk03yb5Ro+CRR2DqxFPEFX0Iuf8Hn6yX\nAG5MR+h2n/TIL8mBrXdpFbcXAaFm29iAA3Y7e0+dYk9REXtVlT1mM/vatsUSHQ3t2kG7diTl59Pz\n0CEmHzxIT5uNHkYjPZOS6JiWhv7KK6UQpAaaI9garlz0QWCjcQUm05PodMdxudpjsczHbg9UCFaZ\n00AE0h4iMDW1g9YFCRBNmTKFxx57jIEDa4zRtDhsNknhPHr0MA88sIP4+AQmTZrG7T87Soq6Ulb6\nZ78CVIjrLoLf4WfSa8c3Y+fwMq3itoVTOdsGINpi4ZE9e0hNSmJPaSl7dTr2JCSQ06YNLp+MmY5H\njtDj6FF6nj9PD4eDntHR9GzdmuSuXVEStbhPTWhBYET8zeY5KIq0gtDr8zCb51BSQghGwBMLcBJK\nk7hQ20E/9dRTZGdnc++99zJx4kTS0tLYu3cvCxfK6vamm27iN7/5DQMHDuT+++9n9+7dqKrK7bff\nzuzZs7n77ruZPHky1113HevWreOJJ57A6XQyYMAAnn32WYxGI+np6dx666188cUXOJ1O3nnnHRoz\nnlJeLqJfViZtGXQ6MBrh1p9foOtlO5nW5VnIdhvyhKsg/XER/fhewdM0tYrbFkkpMig8F3jgyiur\ntDawmkw8PmAAAEabjSsOHqTvrl384quv6AH0jI2lW7t2xHTtKqmUGo1KWBqAUIPAJlMWBkPwdtAG\nQzaK4t8sTVGsmM0P4nAsCfgchyMdi2Uh/sHg2IDHViaUdtDz5s1j8+bNFdO+li5dGvC4nTt3UlBQ\nwKZNmwAoLCz0e9xisfDAAw/w8ccfk5aWxl133cWSJUu48847AWjVqhXr1q1j8eLFvPHGG7zwwgsh\nfYZQcTqlOMtqBYdD9kVFQUy0A6PeiqWwmOTCv8slQdfLoO8z0GEKxDZHYF+jIXAiBVG5eEXedzsG\n5Ps+IchKXXG52Ld2LWmpqRi6dZOiKI1mISwNQMMFgYN1yqy+g6agR/z/oRuAUNtBh0JaWhoHDx5k\n3rx5jBs3jtGjR/s9vn//frp06UKaO7j185//nGXLllUYgEmTJgHSe2jNmjUNck6q6hV9u3vSodEI\nifHlREaUobis4HKCA1nZt8mElH5wzZ0N8v4awVkGZCFCnAoshFo1EFOBQvzFvLK45yFGwJd4p5PU\nwkI65OYydPduUn/4gdTcXDpcuMAtixdzvH37Ku+VeuIEV4wbV7sPqNEohKUBCBVZqQcnIaEven3V\ndtAuVwpFRR8HeEZlTNSmMjiUdtCVMRgMfu2dPa2hk5KS2LBhA2vXruXtt9/mk08+4c9//nPIrxsZ\nKeer1+vCb/YaAAAgAElEQVRxeJbodcTj1/d0rdbrISHOTlREGYqrTIK4DqQIy2gGXRQYyiCxr3TZ\n1GhUlgGzkaUKwFH3ffAaATsi4MHEPRcorvS6BqADYlBGAqmqSurJk6Tu2EGHdevo8MknxO/fLwe3\naiVR/owM+MUvoHdvnvn6a2YnJGjZNmFMizYANWGxzPeLAQCoajQWS+V20MGIQorBSmms1hAdOnRg\n2bJlqKrKsWPH2LlzJwDnzp0jMjKSG264gc6dO/PQQw/5Pc8zAP7IkSN06tSJ5cuXM3z48Fq/v9UK\nxcXi0tHrITZW6mTKy72rfY9fP85sI9pYhk4tkzRNJyL6+lh3Ba5WONccZOEVfw8WxAi8ggj8KWSV\n70srRNy7AT9x/+zZOgBtnE70338vczI3bJA+2+fOyZPbtxfB/81v5LZ79yrxHC3bpg7U91KullzU\nBsBun0pJCXXMAvJQu2Bwbbn66qtp27Ytw4YNo0ePHqSnpwNw/PhxHnroIVRVRVEU/vCHP/iflcnE\nyy+/zC9/+UucTif9+/fntttuq9V7W61QWCiuHRAjcOECFBWJ6CsKmKNtREda0VMmB6oK6CJBHyUb\nWq+d5qAY2AZsQVb8gbAA8UA63pW8Z0tBGqD7UV4O337rFfzNm+UPBCSPftIkWeGPGiX3Q+izNH3E\nCK9+paRoK//qCOVSroG56NNA64+nTbSZUGMBLYUzZyBCZyUuuhi9zonTpae4zIyq6oiLsaJXbCL6\niiJuHX2Ue6Vf8z9+fdpBa/jjAvYgYv+N+3Y33hW9AfHAVaYjcKS6F7bZYOtWr+B//TWUlspjPXqI\n2Hu2Dh0a5LNc0jiBAuAscM596/vzW1S9lIMQfpFV0dJAG4zaB4NbChE6KwkxhShuKdHrnCSY3Cs+\nRecW/GhZ8Ws0GWcRofeI/VZkXh1Ii8IhwM+AocBg4DNgtsOBxWdBZHI4WFh5gVRaClu2iNhv3Cg/\ne0aKpqfDr37lFfw2bRrxE4YBDeFqseAv4IFE3fe2gKp+OA9xBBZ/3OfYSISlAWjeXkCB8ASDy5C4\nQMtFVSWgW1ICyeaiCvH3xaXq0EVf5AIQJtiBnXjFfgsyPQpk6XEVoktD3dsVVL3+mr5sGaxZQ9aC\nBeSmppKam8vCJ55g+tVXi6/eI/jbtknOrk4nrYrvvVfEfuRISApe8HjREczVUgxkEpqYn0VGiQdC\nDyQjQZZk5Jfoe79VpZ8vQ9aYnQjsz2vEDiiaCyhkaq4MDmdcLlkAlpaCXnEQZyoh0hDsLxiIvrxe\n76e5gKqiIgFZX1dONt6k5MuBYXjFvj/SlKRGOnWSIQrBiIiAQYO8/vvhwyEuro6fooVzBgmKnKnF\nc8z4C3Z1Yp4MJFC30FhlwwSy9lxMra9ONBdQg9O4weDGwukU0bdYIEJv47LYUiJ0NncAT/FGgH1R\nWs7nC2dKge34r+5Puh+LAgYA9yFiPwQJzIakGxcuSKOlXbtkq078166FoUPBd/bspYCKrKa/BXb4\nbCdqeN4y/EU9maa76PeIvJYFFI7UvjK4OXE4xM1TZoUoo5VWcSXoFYf49g2xYDCB0wblhf5GQFEg\nIvw/X3MRzHXsAvbjL/a78BZOdUVSLT2r+6uQ68lqsdth716v0Hu2Y8e8x8THyyhCW4Dixo4dYcyY\nun3QloQD2Ie/0H+HeG1BspN7AmOAfsAzBL4C6Ajc0tgnWwPTaVTBr4xmAEKmZQSDy8tF+G02lZjI\nUtoklKLgAp0BDPES1PWsM/XuRMDyYinmUvQi/vqqAzP+9a9/MWLECNq1u3Tn6gZyHf8K0ZNjwAX3\n/jhkRf8Y3kBtcnUvrKqyiq8s9Pv2eftsRERAz57ixklPl613b8nO+ec/YfZs/0HKJhMsvAi7p5Yh\nltUj9N+673u8mVGIdb0JEft+iMvH90+6DYFdLRfh11UTmgGoFTEUFOQwZco0QFfndtDp6ekkJCSg\nd3c/fOGFFxjgbpAVKm+//TZxcXEV/nWbTYTf6XBijiwlMd4CqKA3gsEcNJMn5+hJMjIy6Nq1Kzab\njQEDBvDSSy/5xVfee+897Hb7JSv+ZxGtuY+qiRrlwF7EEHhcOT2opiSuoKCq0O/eLdV4Hjp1EoG/\n4Qav2HfrJkYgENPdS8asLMjNhdRUEf/pLbyZXiGykvd14+zBe1kVjwj83XjFvgc1q1ozuFrClYs+\nCGxcYcT0pAndcR2u9i4s8y3Yp9rrcVbeYHBd20Gnp6dX6RJaV8rKRPhxlWOOKiEqwtOvIRoMMaCr\n3tGQk5PDzJkzWb9+PQ6HgxtvvJGZM2dy44031uu8WmoQ+ASiN77bsWqfIddTVcbXlJXBnj1Vxf6E\njxM6MdEr8OnpcNVV0hjtYgrQhppueRJ/F84OIMfn8cvxinx/920ntDrEIGhBYET8zXPMKFb5K9Hn\n6THPMVNCST2MQAySL+bfFivUdtDB2LBhA2+99VZFd9C5c+cyZMgQbrrpJhYsWMDq1asxGAz85Cc/\nYcGCBTzxxCJiYpKY+ctfcfTgN8ybv4CysjI6d+7MK6++Rlx8AhMnTmTIkCFs2rSJoqIiXn31VQYP\nHhz0HAwGA/369ePkSQlVOhwOHn/8cb755htsNhuzZs2qqDb+85//zMqVK9HpdIwfP56srKy6fZ3N\nhIpoUmWxP+V+XAG6Iz1w+ru320tLyQvQ7ym1qAi+/NJf6A8ckAg8iI++Vy8YO9bruklPlyEnIVTT\ntliCpVueQUqTfd04p32e1xWJkN+JV/S1rORGoUUbAFOWCcOu4B/BkG1Asfn/gylWBfODZhxLAjdI\nc6Q7sCwMVpEB4kwsJlDVRijtoD1MmjQJvV5PdHQ0n3/+edDjzpw5w5o1a/jqq68AhZMnCzlzRsVZ\nXo7JWEJSTAGT5vyWP7/wLEOGj+LJJxfy/At/5o9//CMgVyOrV6/m888/5/nnn+df//pX0PeyWq3s\n2LGD5557DoAlS5bQqlUrVq9ejc1mY8KECYwePZrdu3ezdu1aVq1aRXR0NOfPnw/6muGAC8mtryz2\nBe7H9UAv4BpEd/oDfag6EPTpefOY/dRTVZub3X03vP++iHnnziLu06Z5V/Zdu0KTpiyHAWXA7wjc\npOg37p8NyBc/Aa/Q90FcOxpNQlj+VTZYIVh9ukEHxTcY7E9t2kH/5z//CenKIDExEZ1Ox733PsSI\nEWOZMHYECeYzREWUodOZKShRsdmdDBmeCUhb6Hvuuafi+Z620H379iU3N3BJ4cGDB8nMzOTIkSNc\nd9119OjRA4B169axf/9+PvzwQwCKiorIyclh48aN3HLLLURHR1ecY7jgRBJCfIV+B95KWiMSE/wZ\n3pV95RihH7m5sG4drFvH9Pfeg3PnyFq0yFtw9dhjTH//famqvfJKMF8ic6RdiL8sBzgc4LamdMvt\nwJU0Y11lE3ddC5mmPa+wNAChzgOofqUOCX0T0OdVzWl3pbgo+rgowDNCJQZZP/pfRdSlHbQHvV7v\n1xbaZrO5++9H8MH7X5C9dRX/XfUhK5cvZsX/e0/SOA0x7oZswfEEpXU6HU5n5W7uQteuXVm/fj3n\nzp3j2muvZfXq1YwbNw5VVXnuuefIyMjwO/6LL76o8+cMlVD+DezAj/iL/U68pjkaWVDehlfseyFG\nICh5ebB+fYXoc/iw7L/sMoiOZvr774vg+9KxIwwZUpePGd6cxyvolUX+KPIL8KAgbp00YDzQGXiZ\nShNi3HRELrWajWbouhYSTX9eYWkAGgrLfItfDABAjVaxzK/ecNRMJHIlUF7P1/HSoUMH9u3bh91u\np6jIwoYNm+jf72rsJceIpIjJ1w5l5Ih+DB05HoxJFcVaSUlJREVFsXXrVgYPHlznttAAycnJzJ8/\nn5dffplx48YxZswY3nnnHYYPH47BYODAgQOkpKQwatQoXn31VW688cYKF1BDXgUE+zfIAVojQp+N\nZP95NCgW8SDMxiv23QnhD/zkSRF6j+gfPCj7ExOlavahh2D0aFndv/9++KZb1mXhWIZ8uYFW8DlI\nFo4vSYjA9wVuREQ+zX2bSlXL2nkzzO4HFp+FkakUFq5BIrgqcinhqvRz5fsN8Zjvzw8T2Df1AFK+\np1TaaKJ9c4KcVxaaAagD9ql2Sihp4CwgDybE4dAwWVQdO3bkmmuuZdiwq+mQkspVvXtgjirGXpbP\njNm/wV7uwOVS+dOfnqzy3L/85S88/PDDlJWVkZaWxquvvlrn85g8eTLPPvss27dvZ8aMGeTl5ZGZ\nmQmIgVi6dCnXXHMNP/zwA2PHjiUiIoJrrrmGefPm1fk9KzOPwP8GnobYiYjAP4jXZ9+FEKcRnD4t\nYu8R/H37ZH98vOTY33OPCP5VV0nPHF/CNd0ymMVUkd42vsLu+/PxSq8TiQh6GjAcr7h79oXkmz+D\nXIfthOmPA5MhaxHkpkJqLix8DKa/X/1LNBsFwF3NfRIBaLxucBd9Gmjj4UJSF2KQ0p+6Y7dDSYmK\nHgvmyFL0OndRlsEMBp/CrRZEqGmgDsSNs81n+zbIsQqiXR2pxTdy9qw0Q/Os8n/8UfbHxorgZ2aK\n4PftKxNxWiIdCU0jFKA9/qLuu4pvSy1m+jiQ2uedPtt3ePOoajqRFe4307nv64LcD/ZzfR4bTlXr\nB/LlfINYTs9GpfuNuW8Sgb+/2veD1tJAGx0dEsGyEooBCDR5S1HAUurCqCslMaoURVElb98QV6Nv\nvyWiAgfxF/sdeBeu8cBA5NsMFKFJRRwH1ZKfL50vPT783btlf0yMdL28/XYR/P79W25mjgocADa4\nt+rE/y94Rb4jdRxsdwF/od8J/ID4kEDqYnohzv8+PttAgre3nFKXE2kgniFwKfAziBFoLp6nqUuU\nW+h/QLhgQv4JrFSTR4LVCjaLlctivINXLFYTBr2DJJO7hl0f5S7cqjZE2aIoQdZZOxCx3463XUI0\n4rOfBQxyb10RsxqsKWLAf4Pz52VUoUfwv/9eWitER8OIEXDLLbLKHzgweCVtuONCLpM2IoK/Ee9C\nsTXy5QQbJPLr2r5RDrKS9xV7XwvTChH3e/EKfQ8Ch9YXEp49F8K1FLjpz0szAPXCEwy2UJ0BsFut\nxJv8B6/ERhfLPYNJXD0tvAOnCwmJlyOB2SJkwJENWQOmI+1ZPGJ/JcH/+KZD8FmyhYUi+B4f/o4d\nIvhRUdLm+I9/lBX+oEFgbKHG1Al8j1fsN+LNpmmPNDUb5d66Af+kDjpbgoTRfYV+l3s/iCnujrhL\nfo1X7C8ndAdcuAotNHnXtZBp2vPSDEC9MSGFYQ6CfZ3myOLAg1dcOvQRLa/qRcVf7Mvxr4s2uLfR\niPfhHmqZ7r1sGdNnz2a6b7aNwSCNz44eleEGRiMMGwYLFojgDxkiFbctkXLkMskj+JvwZuCkAdcD\nGYjgpxFgIgzAZsjqBLntIPUELDwC00fgrXmu7MI5hNf/HI+I+6/wCv2VVLeoCZ1wFVoN0AxAA+Ax\nABaCxQL0usD593pdlQ4yTY4Vb2MLPZJO6ftvryKmzSP05fhXP+gRD3CM+zYC0acSREYSqIX4u1yw\nfz88+KB/qiVIV8wTJyQDZ/Ro6XEf3RAC1QzYEJ+Yx6XzFZJ9CLKivwkR+wwkt75GlsH02TDd9zsz\nILlRp/E63nDv6wPcjlfsU2mJiQYa9UczAPXGNxgci+8/kqpCaZEVcxBPhIq+Wf/trMhC07MOdCJS\nYUM+hUfwPegQgY/GK/YhJ40E4swZ+OYb77Ztm7h4gmG3i4unpWFFBgR4Vvj/wxs/7Q3MwCv4bWv7\n4meQhNjKQQAHkuvpu6pPJ5xbmWs0PZoBqCUFBQVMmSIZDN520EmAk1WrPsNoFJeO0wnTpt7Ie4uf\nQzXGo1SpGVBQjA33z5idnc3KlStZWIuipPvvv5+ZDzxA2hVX+O23IgYgAumH4xH7ekUpysrg22/9\nBf/IEXlMr5eeOTffLK6crCwp0KpMaiMOR21ISoCv8Qr+VuQSSkGKqO5GxH4kNQwKCIQTuXz4HBkH\nv72aY8uBv9b2DTQuIZq0DkBRlJ8CExFfyduqqq6q7viGqANYYTTypMnEcZ2O9i4X8y0WptobohCM\nSu2gzyASeRl2mxOXrYCoCAdOJQZ9VBw4rSENXmlsVESLygicOOIh0ERgh8MRcu3F4YMH2fH//h8J\nZ88ybc8e2LnTO9ykQwcRes/Wv7+kaXpYtixwxe3ixeFRdFU5pjkRceN40jKz8frUBuAN2F6N+MRq\nzTngv4jof4FEhHXIBILrgNfxDpv0pfb54xoXB6HWAYR8Ba8oyjuKopxRFGV3pf0TFEXZpyjKQUVR\nHq3uNVRV/UhV1VnIGujnob53XVlhNDLHbCZPr0dVFPL0euaYzaxohOyQnJwzDB9+LbNm3UnmqGEU\nnDtB+uBxlNjcBlYfDVGtcUS0onOvocxfsJCrr76aadOmkZ2dzfXXX8+AAQNYvXo1IIVUkyZNYvTo\n0YwZM4bs7GwA/v3vf1cUVp08eZLBgwdz9uxZNmzYUNGqedGiRdx3331MnDiRvn378p/PPmPe73/P\nsBEjmHLzzZxxOLACt0+cyN5duwDYtGYN0ydM4KbRo3n4jjsoLRWndHp6On/84x8ZPXo0n376aeAP\n73LJRJriYhl4cuqU/Pzf/8qqPy4Ofvtb+PBD8ePn5sLy5bJv5Eh/8QcR+cWLpceOoshtuIj/LCSt\nyTNz9jakNHkS0vvGCDyK6PUFpK7oWcRIhCz+LmRl/0dE5FsDtwKr3C/0PjKm5ivEGj2HxKJ8CYd0\nS41wpzYuoL8DrwFLPDsURdEjy49xQB6wTVGUj5G1z1OVnj9TVVXPJM757ufViyyTiV3VrEizDQZs\nlfqtWxWFB81mljgCt4NOdzhYWDkAGRJRHDhwmNdfXESfqxahRCYSLLBWVFTE2LFjefLJJ7nlllt4\n9tln+fDDD9m9ezdz585l3LhxtGnThhUrVhAVFcWBAwe49957WbVqFTfccAOffPIJ7777Lp9//jlZ\nWVm0atWqynscOXqUZf/+N9/t3s2t11/Py0uXMudPf+K+W25h59q1TLrmGgzuM8w/e5a3X36Zt1au\nxGQy8d6LL7J48WLmzJkDSAuIdevWeV+8vFz88Xa7/OzbZM5gkOCsyQS33QZpafDzOtj66dObVvBL\nkA6W1W05VO38oSJJNB8h48DqfFFXgAi8Z5V/BvntDAYeB65FLicCrdnCOd1SI5wJ2QCoqrpRUZRO\nlXYPBg6qqpoDoCjKB8ANqqo+hayJ/FAURQGeBj5XVTVYxX+D0SjdoAOhqpRbS+nUsQP9+l0JxmQZ\nvh6E6Ojoiv46vXr1Ii4uDoPBQK9evTjmHvhtt9t55JFH+OGHHzAYDBz2dKUEnn32WUaMGMGwYcO4\n4YYbKva7kKBuKTB03DisBgPdevUC4IbMTAzAVb16ccr9HjrAXF7O91u2kLN/P7ddey16VcXhcDDE\np7vljRMmSHC2vFw2DzqdpGOaTHIbEeEdcFJQIB00g0xFq5GG6opro2ZhP0Hg0mMTknffDvlLPxTk\nPYqQnju1QkUKrj5DRP9/yG/wMmQywXVIZW1V4x4YLd1So/bUNwjcHv+JeXnIOigY9wNjgXhFUbqq\nqlolQqUoymzcPVBTawj61bRS75uQQF6A/i4pLhcfF9WnHbQPqorDkk+EUobJFOMutbdR3VIwwqci\nVafT+bVsdrivTP7yl7/Qvn17/vrXv1JeXk7Hjh0rnnP8+HH0ej1nzpzBoqrYFIUCxLdvRYQ9zmik\nDeDS6TBGRFT8on3fA5eLyKIi4gsLGTtsGG885b5oi4qSFKZTp8DpxFReLuXMERHS7z4iQgS/ruJe\nE6F0xXUgGY7HqV7YA7UjNiKi3g7Jwhnvc9+ztadyUpcEdoN1NgiJQmA1XtH3lPMORKzddUiZXMsu\nCtRoOTRpFpCqqq8Ar9RwzGJgMUgQuD7vN99iYY7ZjNXHDRStqsyvk4unKqrLieooRa84KCcORacn\nlMrgUCgqKiItLQ1FUfjggw/wBOut5eXc/+CD/Pmdd3h/yRJee/NNZtx9N5GIrrVxv7MRMQTVVho4\nnaCqDOrTh8eefpojx47RqUMHSgsKOFVQQJcrrhCRT06W1XxTkUXgdqCzgBcRYT9NVXeMHkmjbIdU\noI2gqrC3QxbZdcm/rXVnAxWprvVk7HyFRIcTkFX+tcg4LG3eoUbzUF8DcBz/UpUUArfZaxamSpvN\nRskCctpKUVxWVNWMQ59MRJRHFWIQn0DgGEOo3HHHHcycOZN//vOfjBk3DmNkJGeAl59/nkEZGfQd\nNIie3bszZdw4powdSwzevoch4XDIKh9onZzMy088wZ0PP0y528WT9fjjdElIEJdOUzRNcwG7gXUE\nXmWDXN60Rfo/BxL21jTu4jkkV3sRsBbvKt/z79APeARZ5Q9By8DWCAdqlQbqjgH8R1XV3u77BqQn\n7E+Qv/RtwC2qqv5Qr5PyjoScdeDAAb/Hmr8dtIrTegE9ZdgcUeijEzAYfGXX0ybaRF2Hm6pImmYZ\n4kzy/IYikZIzTweiOuE2itiqiYTo9dC6dV3fAQihHbQK7EEEfx2SPnnO/ZiBwPYzLLIaAwUn+uJd\n5W9CTj4O8S15VvntmuNkNS5RGrwdtKIo7yOhrmRFUfKABaqqvq0oyn1I0pseeKe+4g+hj4RsclQn\nrrIC9Diw2GOJijUHcINXbhMd2prciVf0PdcnnlfyiH69qobLykT4y8vFrWM2i9AXFVVcCQCy4o9t\nhGpRTy/odT7bafdjqUh242j3tinYJKkdiF+nsfBtaRdo+xBYgLeM15MH6vn+0oG5iOgPR8rnNDTC\nl9pkAf0iyP7PkKVPg9FgQ+EbEqcN1X4eVCgpTyImLhIlqCLH4JVziQUE6rmjR1b4ZXgXvAak+tbj\n068XMlRYhN8ziCA+XtI0PSevKFUHFTRUj50iJHPmY0TwPd6Qy5FrRo/gd8bHuqkw/WYgI8AkqU+B\nmVQv0vXZ6tKbSUVmJX5HiI17NDTChrB0RIbbFYBaXoLiKMbhjMBOIub4mhwwRuSrLQWig/bc8T06\nDlnpN4gL2+WC0lKppHW5JGsnLk6yeyoTHd1wgu9ELl9siPi/4/PzaJ+tmwOUY8glwaFKtzmARcYG\nBhwd+Dbe5hQ1bTG1ODaU7XYCjwA9jyb+Gi2RsDQA4YOKajuP4rJhtUeDMZ6Y6FAdMSY8weBiDAFl\nQ4fELRusIZzTKat9T5ZTZKS4ehqrL74LEXiP6HvqwRTEko22QM8CuOclUHyF/jD+Tv5IpEtlF6Sm\n8O+IqFamuYMA86lnHqiGRlgRlgYgLFxAqgPVVoCiOimyxhNlNtVSR6OBIpxYcQbpwOiigcS/vFyE\nv8ztm46OFuFv6CC5C6/Y2/FquAIYnRBjh0gbGOxgLYQ+iyHB5hb/OETg+wI/Q+Z/dXHftsO/wnUA\n4TlJKlwnXGlo1I2wNADN7gJyWsFeiKoqXLBeRmy8sQ5aqqOEBEqq6YZfb3dPWZm4eux28eWbzdJX\npzYFWlY7FOvBqQe9E2KdEO22dC7AroJNBbsCDk/cQAWjHUw2uY3wVAfr3J/KiKzqJyAVVbchbS9b\n+iSpcD0vDY26EZYGoFkpLwJHKXaHkRJ7IgmJOj89DdwOWnr6rlq1CqPRiB3x+d8x7XZee+cNLouN\np5iISs2g69iZXVX59MMPydm/n/tnzJDAbVwcmEw4nE66de1KTk5OaK9ltUNhBKhuYXbq4YJO9jt1\n4HB3C1IQoY+2Q2Q5RKjIn44eCVnr3fd9Bf48Mis2gdDbGfgSrq0NwvW8NDRqz0VvAIwnVmA68CS6\nsuO4otpjuWI+9nZTqx6ousB+Hlx2Sm0mytV4EpOokumTlJTE+vXrgcrtoGXBfAGwqCo6VeVfy5cT\nxVmgEB3JASdvOZ1O9AHaVVQ9P1VW+6WlTBw2TLpoms11COD6DHQsjvKKfwUK2IxgdECsDYwqGD1O\nfTPa5CgNjYuHRmrmUj8URbleUZTFhdVNhwoB44kVmH+Yg74sDwUVfVke5h/mYDyxwv9AVznYzoLL\nzgVLAi59PAmJVcW/On7MyWHo8OE8cNddTLn6alynTzMoPZ3CQhHbaMppDbRyOBjauTNPZmWRkZHB\nt99+y9NPP83YsWMZMWIEc+fOrWj7MHHiRLLmzSNz5EhGDh/Oji1bICKCpV98QdZLL0F0NIcPH2b8\n+PGMHDmSZ555xu+cXn75ZcaNG0tGxgiee+5PSAvhU0C+FII5qzE8lxnAHAlGTxVC5RW+hoZGSycs\nrwBCjQGY9mRhKN4V9HFDYTaKy7/iVXFZMf/wII48d1dr1SUBXxQcTgPG+Kuw9w49qOdCCliLgcMH\nDvCX119nYL9+PkdE4x2/IpXBRUVFDBs2rGJ6V9euXXn00UdRVZXZs2ezdu1axo4aBQ4HtsJC1v/r\nX2z87jvm/OlPrN+wwS+4O2/ePGbPns3UqVN588033HsLWb16DXl5+1m1agmqqnLzzfewdcsuBl85\nAiwR4KpGzPWe6xQNDY2LmbC8AmgwXEHaHXj2q05QHbhUHeWOCPQGBUOIuqciyTCliFsnFujUqVMl\n8Qf5iqORUjBZ2RuNRiZOnFhxxMaNGxk3bhyjRo3i66+/Zu+338K5c+BySbyhdWsyrr2Ws+fOUVJS\n4vkQQBnbtm3lxhszgFPcdNNo93tYWb/+K9au/YrRo29mTOYtHD54gkM7TkOJESIUGWKSYJeAri+K\nKoFgDQ2Ni56wvAIIFUvP6lfqCRv6oi/Lq7LfFZVCUZ93wFVOic2MxR5LUlLoWZNWJMO/HEkCbI0Y\ngpjKk60qMLmfZQWMREVFobj9SxaLhUcffZQvP/2Uy2NjWfTii9isVqnIjYhAiYkBvYKnK5CiXHC/\nuxUJtKpuV1U03sTStqjOKH7z699y6+RbZbfefRrR+CzujUA1WUAaGhoXNWF5BdBQMQDLFfNRdf5B\nUltN/6wAABuESURBVFUXjaXT/eBycL40kTJHLMnJoYm/A2kvfwGvnkYRimfc6A62FiKzW1WwF4Kq\nUlZQgKKqJOn1FJeW8sm6dWCOcsdbnXz00fvAaTZv/i+tWycRE+PxxxuBZAYNGsJHH20G4lmx3D2y\n8RyM7jeaZR8so9RRCklwwnGCfFt+Vc9OtBFa66U9Q2u9Jv4aGpcQYXkF0FB1APZ2UykBnyygdlg6\n3k9Zq8nkFyViMBq4LKHmYK+KTAwsQcQ+HhH/kK2nvVCyaXyJsEChhaQoPTdP+ylXT/kpbdq2YsDA\nXng7B6kYDEYyM3+O0+nilVdeRVIqTXjaEyxatIi777qbl154iQmjJsjJqjBu0jgOnDvAhJsnAGA2\nm3nzzTe5rCn7+mtoaIQ1tWoH3dQMHDhQ3b59u9++urWDVsF+AZxl2J1RFJQkEBOjhNT00oas252I\n9ySOOlw2OU+GEFPVIaJuxCPuEydez9NPP016enrVw12InbAglyYKcjliogG6yNWfGttBa2hoNBoN\n3g66xaI6wV4ALgel9liKLGYSEmpOn3cinvYy5Eu6jHroarXin4gIfojRZzsi+lb3/QjkkiQaLUtT\nQ0OjVlx8BsBphfJiEX5FV9Hr/rwlCVt5JJddVnNvtFLEAQOS3WOu9zkRWN+dgD54q4hPP3X79F2I\n6Fvcz1GQlX4MF+NvUENDo4kIS/moqRlcULeV0wrlhd4BJ6r0dy+yxlHujKwx2Otp4eBASp/iaYBs\n+OJiecEE/FfoKuA0Vf8GnjxTTzarEbFIoUWemw1VVYP/jjQ0NMKGsMwCUlX1E1VVZ8fHVx2pGBUV\nRWFhYWCBKS/2n27lxhxVWq34e1o45CO6nIiM+KiX+KsqnD8vXTp1Jig3edslO5H7xgAjI53I5cdp\noADJNTUjuaaXEfauHlVVKS4uxlbdyEkNDY2wICyvAKojJSWFXbt2UV5eXrWHjt137IovChhLA76e\nHfHzq8iqPxJZdNcLl0t68judMoTF06bZjzJE4fFrz0O5nG5FpqcB/+7DYY6qqthsNo4fP46qqs00\nt1lDQyMUWtx/Z0REBK1bt2b58uWYzWY/gSne8SaxkVVrB4pt8cT2u8tv3xlgFXACaeo7Dllg15uz\nZ+H//k9Ef9Ik8LixfkTmhRchqUQjkVX9TvdjVsTndBUyWrbegYfmxeVyUVJSwuDBg5v7VDQ0NILQ\n4gwAyFXAxIkTyc7O9nM1bPgxgwl9viBCX16xr9wZwYYfM7i+v/hN7IgOZyPelEnAlQ11YocOwccf\nyySu6dOhdWvZ/yPwX2R1DxJo+BRZ+euBbkAfxBKFsXunNkRFRdGnTx/69OnT3KeioaERhBZXB1Ad\nnTrB8PbLWHRTFqmX5ZKbn8pj/1rI18enc/gILAfmILW4dyOjPBIb4kRVFV56CebOhQED4N//hnbt\nfE6MwJMEE4H9yKwUDQ0NjQbikqwDWLgQZs+ezvtfewd2mEzwx/dlNtUqoD/wIdBgjonycrj/fnjz\nTZgyBZYulTf1cIjA4g8SedbEX0NDo5kIyyyguvYCmj4dZvwX9McAJ+jzoNceeGwybAFeBbbSgOJ/\n4QJcd52I/7x5sHy5V/z3IJMQu1XzfG2WuIaGRjMSlgagujTQ6lgGvDcCnCmADpztYXuqjBjfB9xH\nA3a5P3QIhg2DDRvg3Xdh0SKZxfsdMA0JLKxEfE6vIYVbvmizxDU0NJqZi8oFlEXgjMkTQNuGfKNN\nm+DGG8X3v2YNZGTIJcZC4D9Ils9jwEN4XTwJaLPENTQ0woqLygDk1nJ/nViyBGbNkojzfz6FE10l\nh3QNkkf6JHAvIvi+aLPENTQ0woywdAHVlWAu9QZxtbtcMH8+zJgBV4+AJ7fDr7pCJrALeB44gqzy\nK4u/hoaGRhhyURmAhTSSq91igZtvhoWLYOxrULgaboqVS4vXgMPAXFp88ZaGhsalxUXlAvJ4WBrU\n1X7qFFz/U9ieBm1Pw5pW0AV4C8nyCYPe+xoaGhp14aIyANDArvbs72H83+H8UuAKKdx6Hvg5F+E3\np6GhcalxUbmAGowy4N5dMCgeCl6Ebu1hBbAbsS6a+GtoaFwEhKUBaKih8LWmFHhRhTYl8Jd0MBXC\ne/mwxwQ/I0y/LQ0NDY26EZaSVtdCsDpTBDwFdFJhrgJFW2HEAjjVBW6/7KJp0KahoaHhS1gagCYj\nH1gAdEQKt9RtwNXw6GrYsADMMc16ehoaGhqNyaXpzT4FvAi8AZQA4/9/e/ceHVV9LXD8u/OCJCSB\nPNRCSKIEEli24DXFUougKSIUiAttfVB51MLtlYePtVrtRb3tugu7unqtFhQFX/iIUESkYG0VQUvt\nUkDwARKsAQUSQAiBPAjmue8fMwl5wiSZmTOZ2Z+1ZmXmZOacnUD2Puf3+53f7zT8ewYUr4dnl8Gs\nWc7GZ4wxfhBaBeAQ8AfgKVwLA9wEXLcT7rnWNa3Dxo0wZoyjIRpjjL8EXxNQPq7598PcX/OB/cAc\nXOP3nwBuwTVb54QXYfYoSEqCDz6w5G+MCSnBdQWQjyvRN84IdwCYgWvV90jg58CvgLQGePBB1wIC\nV18Na9ZAYqIjIRtjjFOCqwC0Nx1oPRAH7AX6A2fOwC0zYfVquP12WLoUoux2XmNM6AmuAtDRtJ+V\nuJL/0aOQlwfbt8Mf/uBawlFsjKcxJjQFVwFIo/3lF9OATz+FSZPgxAlYuxauv97PwRljTGAJrk7g\njqYDvfEjuPJK15TO771nyd8YYwi2AjANWI7rxi4B0hSm/g0eyYEhQ2DrVrjsMmdjNMaYABFcBQBo\nMQ60NB5emuhq99+yBQYMcDg2Y4wJHH7rAxCRocCduFbJ3aSqT3j9IPn5MGeOawEXgMpKiIiAqVMh\n1qZ1MMaY5jy6AhCRZ0XkmIjsbrX9OhH5XEQKReS+c+1DVQtU9RfAT4Arux7yOSxceDb5N6qrcy3l\naIwxpgVPm4BWANc13yAi4cDjwARgGHCLiAwTkW+LyOutHhe4PzMF+Cvwhtd+guYOdjAOtKPtxhgT\nwjxqAlLVLSKS0WrzSKBQVfcDiMgqIE9VfwdM6mA/64H1IvJX4OX23iMic3Ddz0taWieXc09LgwPt\njAPt7H6MMSYEdKcTeACu6dUaFbm3tUtExorIYhFZxjmuAFR1uarmqGpOSkpK5yJatAhiWo0DjYlx\nbTfGGNOC3zqBVfVd4F2fHmSaezXghQtdzT5paa7kP81rqwQbY0zQ6E4BKAYGNnud6t7WbSIyGZic\nmZnZ+Q9Pm2YJ3xhjPNCdJqDtwGARuVhEooCbgfXeCMrvS0IaY0wI8nQY6ErgfSBLRIpE5HZVrQPm\nAW/iml1/tap+5o2gHFsU3hhjQoioqtMxdCgnJ0c//PBDp8MwxpgeRUR2qGrO+d4XhFNBGGOM8YQV\nAGOMCVEBWQCsD8AYY3wvIAuAjQIyxhjfC8gCYIwxxvcCsgBYE5AxxvheQBYAawIyxhjfC8gCYIwx\noSh/Vz4Zj2YQ9tswMh7NIH9Xvk+P57fJ4IwxxnQsf1c+czbMoarWtajVgbIDzNkwB4Bp3/bN/GYB\nWQC6NRmcMcacR/6ufBZuWsjBsoOkJaSxKHeR15NsfUM9lTWVVNRUUFFd0eJ5RY37tft5RXUFT+18\nqin5N6qqrWLhpoWhVQBUdQOwIScnZ7bTsRhjgktHZ9oNDQ1MyZrSIkmfN3Gf4z2tk3lHBKFPVB9O\n155u9/sHy3y3omFAFgBjjPGG+oZ6jp0+RlF5EUXlRRwqP8QD7zzQ7pn29HXTPdpnY8KO6xVHXFQc\ncb3i6BPVh4HxA5u29Ynq0/S95u9pb1tMZAxh4mrzP1DWdkXDtATfrWhoBcAY0yPVNdRxpOJIU3Jv\nelScfX644jB1DXUe7/Phax9ukaRbJ/q4qDiiI6MJE++Pn1mUu6jFlQlATGQMi3J9t6KhFQBjjM90\nta29pr6GwxWHz565lx1qk9yPVh6lQRtafC46IpqBCQNJjU9lbMZYUuNSSY1v+ch5KqfdZpX0hHTu\nGXWP1372zmr8vfi6b6I5mw7aGOMTrdvawXVG+9iExxidPrrtmXuzx9env26zv8ZmltYJvfmjX+9+\niEiX4lo+eblPk60/eToddEAWgGajgGZ/8cUXTodjjPFAgzZwouoExRXFHK44zG2v3UbpmVKPPtuv\nd79zJvbU+FTie8V7LVZ/jAJyUo8uAI3sCsCYwFBeXc7hisMUl7uS++GKw02JvvH5kYoj1DbUerS/\nFXkrWiT32KhYH/8EocXTAmB9AMYEga6e0VbXVTcl8faSeuPzyprKNp+N7xVP/7j+DIgbwJj0MU3P\n+8f1Z0D8AG5cfSPFFcVtPpeekM6METO88nOb7rEC4CfBfslpnNPRuPZTZ05xReoVZxN649l75dnn\nJ86caLO/XuG96B/Xn/5x/Rlx0QgmZk5sSuqN2/vH9adPVJ9zxvX7cb/3+6gW0znWBOQHodDpZPyv\npr6GwtJCxqwYQ0lVyXnfHyZhXBh74dlE3qdlUm88e0+MTjxvR6qn7MTHGdYHEEA6usEjPSGdr+76\nyv8BmR6lsqaSvSV7KTheQEGJ+3G8gH0n9513jPu6m9Y1nb1fEHsBEWF20R8KenQfQLDNBdTRrdwH\nyg5w8sxJ+kX383NEJhCVVJWcTfLur3uO7+FQ+aGm90SERZCZmMmwlGHcMPQGhqYM5Zcbf8nRyqNt\n9peekE5edp4/fwTTwwRkAQimuYBUlfhe8ZRVt7+4TeojqUz/znTmXzGfYSnD/Byd8TdV5VD5oTaJ\nvqCkoEUzTnRENNnJ2YxOH82w5GEMTRnK0OShDEocRFR4VIt9ioi1tZsuCcgCECxUlXvfvpey6jLC\nJZx6rW/6XkxkDPePvp99J/ex4pMVPLnjSX54yQ9ZMHIBEwdPJDws3MHITUc8bdOura9l38l9bZpt\n9pbsbTHpV2J0IkOTh3J91vVNSX5oylDSEtI8nm7AiTtITXCwPgAfUVXu+vtdLN62mDty7mDUwFHc\nv/n+dv9AS6pKeHrn0zy+/XGKyou4pN8lzPvuPGZdNou+vfs6/JOYRu115kdHRLNw9EIy+ma0SPSF\npYUtxsSnxqe6krs7wTd+TYlJ8VqHqzGNrBPYQQ3awB1/vYNlO5Zx9/fu5uFrH/boj7yuoY51e9ex\neOti/nnwn8RGxjJj+AzmXzGf7ORsP0Ru2lNTX8NXp75i9LOjOVZ1rMP3hUkYmYmZbRJ9dnI2cb3i\n/BixCXVWABxS31DP7A2zee7j57jvyvt4KPehLp3hfXTkI5ZsW8LLu16mur6aawddy4KRC5gweIJP\nZiIMdWdqz7D/5H4KSwubHvtO7qOwtJADZQfaTDrWnCB8+l+fMjhxML0ievkxamPaZwXAAXUNdcxc\nN5P8Xfn8ZsxveHDMg92+vD9++jhP7XyKpduXUlxRTGZiJvO+O4+ZI2aS0DvBS5GHhvLqcvaV7ms3\nybe+Y7Vf735kJmY2PQb1G8S9b9/b7iRlNpzXBBorAH5WW1/LtLXTeGXPKzx0zUP8evSvvb7/1/a+\nxuKti/nXoX/RJ6oPM4fPZN7IeWQlZ3n1WIGgKzcQqSonzpxomeRPFja9Pl51vMX7L4y9sE2Sz0zM\nZFDiIBKjE9uNyW7oMz2BFQA/qq6r5qY1N/GXz//CH6/9I3ePutunx9txeAdLti1h5e6V1NTXcF3m\ndSwYuYDxmeODonnoXIn21ktv5UjlkRZJvvEsvrC0sMVwW0FIjU/tMMmfbyqDjmKz0TYm0FkB8JMz\ntWe4YfUN/K3wbzw24THmjpzrt2MfO32M5TuWs3T7Uo5UHmFw4mDmj5zPjBEzvDp1rr+lP5re7s1z\nkWGRRIZHtigM4RJORt+MNgk+MzGTi/tdTO+I3v4M3ZiA0KMLQE9ZD6Cqtoq8VXls2r+JZZOWMfty\nZ+5bq6mvYW3BWhZvXcz7Re8TFxXHrBGzmDdyHoOTBjsSkyeq66opLC1kb8lePj/xOXtL9rK3ZC/b\nD2/v8DN3f+/uFkk+LSGNyPBIP0ZtTODr0QWgUSBfAVRUVzBp5STeO/gez+U9x/Thni0o7Wvbi7ez\nZNsSVu1eRW1DLRMHT2TByAWMGzTOkeYhVaWkqqQpuTdP9F+e+rLF6JrU+FSyk7P5oOiDdqcfts5W\nYzxjBcCHyr4pY0L+BLYVb+OlqS9x86U3Ox1SG0crj7J8x3Ke+PAJjlYeJSspi/kj5zN9+HSfjEmv\nra9l/8n97Sb6k9+cbHpf74jeDEkaQnZyNllJWWQnZ5OdnM2QpCFNbfLW2WpM91gB8JHSM6WMf2k8\nnxz9hFU3rmLq0KlOh3RONfU1rNmzhj9t/RPbircR3yuen434GXNHziUzMbPTnZqlZ0r5vOTzNom+\n9cyUF/W5yJXck7LJSj6b6D2d4sA6W43pOisAPlBSVcK4F8ex5/geXv3Jq0waMsnpkDpla9FWlmxb\nwurPVlPXUMfwi4ZTcLyA6vrqpvfERMbw5I+eZNTAUe0m+uZDKSPDIhmcNLhNos9KyrJ7FIxxkBUA\nL/u68mtyX8hl38l9rLtpHeMzxzsdUpcdqTjCsh3L+N8t/3vOO1wbpcSkuJJ7kussvjHRZ/TNsPnl\njQlAVgC8qLi8mNwXcjlUfogNt2zgmouvcTokrwj7bRhK+//+z055lqzkLLKSskiKSfJzZMaY7ujR\nC8IEkoNlB7nm+Ws4dvoYb/70TX6Q9gOnQ/KatIS0Dlcqm3XZLAciMsb4U8+/bdSHvjz5ZdN6qxtv\n2xhUyR9gUe4iYiJjWmyzhUSMCR1WADrwxYkvuGrFVZRXl7Np+iauSL3C6ZC8btq3p7F88nLSE9IR\nhPSEdBtqaUwIsT6Aduw5vofcF3Kpb6hn420bGX7RcL/HYIwxXeVpH4BdAbTy6defMnbFWADenfmu\nJX9jTNDyawEQkVgR+VBEAnIA/c4jO7n6+auJCo/iHzP/YYu0G2OCmkcFQESeFZFjIrK71fbrRORz\nESkUkfs82NW9wOquBOprW4u2kvtCLnFRcWyZtYUhSUOcDskYY3zK02GgK4DHgBcaN4hIOPA4MA4o\nAraLyHogHPhdq8//DBgO7AECbn7e9w6+x8T8iaTEprB5+mbS+6Y7HZIxxvicRwVAVbeISEarzSOB\nQlXdDyAiq4A8Vf0d0KaJR0TGArHAMOCMiLyh6sFtqD72zpfvMHnlZAbED2Dz9M0MiB/gdEjGGOMX\n3bkRbABwqNnrIqDDsZKquhBARGYCJR0lfxGZA8wBSEtL60Z45/fWvrfIW5XHJf0uYdP0TVzU5yKf\nHs8YYwKJ30cBqeoKVX39HN9frqo5qpqTkpLiszhe//frTF45maykLN6d8a4lf2NMyOlOASgGBjZ7\nnere1m0iMllElpeVlZ3/zV3wWsFrTP3zVL5z4XfYPGMzKbG+KzTGGBOoulMAtgODReRiEYkCbgbW\neyMoVd2gqnMSErw/pfCfd/+ZH7/yYy7vfzlv3/Y2idGJXj+GMcb0BJ4OA10JvA9kiUiRiNyuqnXA\nPOBNoABYraqf+S7U7nvxkxe5de2tfH/g93nrp2/ZnPXGmJDm6SigWzrY/gbwhlcjosWi8F7b5zM7\nn2H2htlcffHVrL95PbFRsV7btzHG9EQBORWEt5uAlm5fys83/JzxmeN5/ZbXLfkbYwwBWgC86ZH3\nH2HuG3OZkjWFdTetIzoy2umQjDEmIATkgjDdaQJqvph4Qu8ETn1zihuG3sDLN7xMVHiU94M1xpge\nKiCvALraBJS/K585G+ZwoOwAinLqm1OESzh5WXmW/I0xppWALABdtXDTQqpqq1psq9d6HnjnAYci\nMsaYwBWQBaCrN4IdLDvYqe3GGBPKArIAdLUJKC2h/bmDOtpujDGhLCALQFfZIufGGOO5oCoAtsi5\nMcZ4zhaFN8aYINOjF4X39WygxhhjArQA+HI2UGOMMS4BWQCMMcb4nhUAY4wJUVYAjDEmRAX0ZHBA\nuYh80cXdJAMl3ovKayyuzrG4Osfi6pxgjSvdkzcF9DDQ7hCRDz0ZBuVvFlfnWFydY3F1TqjHZU1A\nxhgToqwAGGNMiArmArDc6QA6YHF1jsXVORZX54R0XEHbB2CMMebcgvkKwBhjzDkEXQEQkWdF5JiI\n7HY6luZEZKCIvCMie0TkMxG50+mYAESkt4hsE5FP3HH91umYmhORcBH5SERedzqWRiLylYjsEpGP\nRSRgZisUkb4iskZE9opIgYiMCoCYsty/p8ZHuYjc5XRcACJyt/v//G4RWSkivZ2OCUBE7nTH9Jmv\nf1dB1wQkIlcBlcALqnqp0/E0EpFvAd9S1Z0iEgfsAK5X1T0OxyVArKpWikgk8B5wp6p+4GRcjUTk\nHiAHiFfVSU7HA64CAOSoakCNHxeR54F/qurTIhIFxKjqKafjaiQi4UAxcIWqHnA4lgG4/q8PU9Uz\nIrIaeENVVzgc16XAKmAkUAP8HfiFqhb64nhBdwWgqluAUqfjaE1Vj6jqTvfzCqAAGOBsVKAule6X\nke5HQJwViEgq8CPgaadjCXQikgBcBTwDoKo1gZT83XKBfU4n/2YigGgRiQBigMMOxwMwFNiqqlWq\nWgf8A5jqq4MFXQHoCUQkA7gM2OpsJC7uZpaPgWPARlUNiLiAR4FfAQ1OB9KKAm+LyA4RmeN0MG4X\nA8eB59xNZk+LSKzTQbVyM7DS6SAAVLUY+D/gIHAEKFPVt5yNCoDdwGgRSRKRGGAiMNBXB7MC4Gci\n0gd4FbhLVcudjgdAVetVdQSQCox0X4Y6SkQmAcdUdYfTsbTjB+7f1wRgrrvZ0WkRwH8AT6jqZcBp\n4D5nQzrL3SQ1BXjF6VgARKQfkIercPYHYkXkp85GBapaAPweeAtX88/HQL2vjmcFwI/cbeyvAvmq\nutbpeFpzNxm8A1zndCzAlcAUd3v7KuAaEXnJ2ZBc3GePqOox4DVc7bVOKwKKml29rcFVEALFBGCn\nqn7tdCBuPwS+VNXjqloLrAW+73BMAKjqM6p6uapeBZwE/u2rY1kB8BN3Z+szQIGq/tHpeBqJSIqI\n9HU/jwbGAXudjQpU9deqmqqqGbiaDjarquNnaCIS6+7Ex93Eci2uy3ZHqepR4JCIZLk35QKODjBo\n5RYCpPnH7SDwPRGJcf9t5uLql3OciFzg/pqGq/3/ZV8dKyBnA+0OEVkJjAWSRaQI+B9VfcbZqADX\nGe1twC53ezvAf6vqGw7GBPAt4Hn3CI0wYLWqBsyQywB0IfCaK2cQAbysqn93NqQm84F8d3PLfmCW\nw/EATYVyHPCfTsfSSFW3isgaYCdQB3xE4NwV/KqIJAG1wFxfduYH3TBQY4wxnrEmIGOMCVFWAIwx\nJkRZATDGmBBlBcAYY0KUFQBjjAlRVgCMMSZEWQEwxpgQZQXAGGNC1P8DkYhdm/+sr4cAAAAASUVO\nRK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1bbc7ce52e8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def Temps_Calculs_bis(n) :\n",
    "    \"\"\" on forme les listes des temps de calculs sur des listes triées de taille 1000*k lorsque k varie de 1 à n \"\"\"\n",
    "    LX=list(range(1,n+1))\n",
    "    LY1,LY2,LY3,LY4,LY5,LY6,LY7=[],[],[],[],[],[],[]\n",
    "    for x in LX :\n",
    "        L=Production_Liste(100*x)\n",
    "        L.sort() # tri par la méthode Python\n",
    "        t_0=time.clock()\n",
    "        Tri_Par_Selection(L)\n",
    "        t_1=time.clock()\n",
    "        Tri_Par_Insertion(L)\n",
    "        t_2=time.clock()\n",
    "        Tri_A_Bulles(L)\n",
    "        t_3=time.clock()\n",
    "        Tri_Fusion(L)\n",
    "        t_4=time.clock()\n",
    "        Tri_Fusion_Rec(L)\n",
    "        t_5=time.clock()\n",
    "        Tri_Par_Tas(L)\n",
    "        t_6=time.clock()\n",
    "        Tri_Rapide(L)\n",
    "        t_7=time.clock()\n",
    "        LY1.append(t_1-t_0)\n",
    "        LY2.append(t_2-t_1)\n",
    "        LY3.append(t_3-t_2)\n",
    "        LY4.append(t_4-t_3)\n",
    "        LY5.append(t_5-t_4)\n",
    "        LY6.append(t_6-t_5)\n",
    "        LY7.append(t_7-t_6)\n",
    "    figure()\n",
    "    semilogy()\n",
    "    plot(LX,LY1,color=\"red\",marker=\"o\")\n",
    "    plot(LX,LY2,color=\"blue\",marker=\"o\")\n",
    "    plot(LX,LY3,color=\"green\",marker=\"o\")\n",
    "    plot(LX,LY4,color=\"yellow\",marker=\"o\")\n",
    "    plot(LX,LY5,color=\"magenta\",marker=\"o\")\n",
    "    plot(LX,LY6,color=\"cyan\",marker=\"o\")\n",
    "    plot(LX,LY7,color=\"orange\",marker=\"o\")\n",
    "    legend(('Tri sélection','Tri insertion', 'Tri à bulles','Tri fusion','Tri Fusion Réc','Tri maximier','Tri rapide'),loc='upper left', shadow=True)\n",
    "    show()\n",
    "Temps_Calculs_bis(9)     "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette fois-ci c'cest le tri à bulles qui remporte la palme, sans surprise et le tri rapide n'est plus aussi rapide ..."
   ]
  }
 ],
 "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": 0
}