{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dear difflib, What The F@&#! ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## TL,DR:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Acording to difflib, the following strings: 'baaaaa', 'aaabaa' and 'aaaaba' share 5 caracters with 'aaaaaa', but 'aabaaa' share only 3 .... but only if the change is in the first half of the string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "4\n",
      "3\n",
      "5\n",
      "- Control -\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "import difflib\n",
    "print sum(x.size for x in difflib.SequenceMatcher(None, '-aaaaa', 'aaaaaa').get_matching_blocks())\n",
    "print sum(x.size for x in difflib.SequenceMatcher(None, 'a-aaaa', 'aaaaaa').get_matching_blocks())\n",
    "print sum(x.size for x in difflib.SequenceMatcher(None, 'aa-aaa', 'aaaaaa').get_matching_blocks())\n",
    "print sum(x.size for x in difflib.SequenceMatcher(None, 'aaa-aa', 'aaaaaa').get_matching_blocks())\n",
    "print '- Control -'\n",
    "print sum(x.size for x in difflib.SequenceMatcher(None, 'aaaaaa', 'aaaaaa').get_matching_blocks())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It only get weirder and more fractal if you read the rest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Context"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A few weeks back I was in [EuroSciPy](http://euroscipy.org), where I had to dive a little deeper than usual into difflib.\n",
    "Indead, one often requested feature in [IPython](http://ipython.org) is to be able to diff notebooks, so I started looking at how this can be done. Thanks to [@MinRK](http://github.com/minrk) for helping me figuring out the rest of this post and give me some nices ideas of graphs.\n",
    "\n",
    "Naturaly I turned myself toward [difflib] :\n",
    "\n",
    "\n",
    "> This module provides classes and functions for comparing sequences. It can be used for example, for comparing files, and can produce difference information in various formats, including HTML and context and unified diffs. For comparing directories and files, see also, the filecmp module.\n",
    "\n",
    "[difflib]: http://docs.python.org/2/library/difflib.html\n",
    "\n",
    "More especially, I am interested in [`SequenceMatcher`](http://docs.python.org/2/library/difflib.html#difflib.SequenceMatcher) which aims to be : \n",
    "\n",
    "> [...] a flexible class for comparing pairs of sequences of any type, so long as the sequence elements are hashable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is also explicitely state that generated diff might not be minimal, but might looks more  \"human readable\" than classical diff (emphasis mine). \n",
    "\n",
    "> The basic algorithm [..] is a little fancier than,[...] \u201cgestalt pattern matching.\u201d The idea is to find the longest contiguous matching subsequence that contains no \u201cjunk\u201d elements [...]. The same idea is then applied recursively to the pieces of the sequences to the left and to the right of the matching subsequence. This **does not yield minimal edit sequences**, but does tend to yield matches that **\u201clook right\u201d** to people.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To do that, we need to define \"junk\" which are things you don't want the algorithme to match on. \n",
    "Let see a common example in python where when you add a function with a derorator, the decorator is often added to the \"next\" function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "s1 = \"\"\"\n",
    "@decorate\n",
    "def fun1():\n",
    "    return 1\n",
    "    \n",
    "@decorate\n",
    "def fun3():\n",
    "    return 3\n",
    "\"\"\"\n",
    "\n",
    "s2 = \"\"\"\n",
    "@decorate\n",
    "def fun1():\n",
    "    return 1\n",
    "    \n",
    "@decorate\n",
    "def fun2():\n",
    "    return 2\n",
    "    \n",
    "@decorate\n",
    "def fun3():\n",
    "    return 3\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Classical diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  \n",
      "  @decorate\n",
      "  def fun1():\n",
      "      return 1\n",
      "      \n",
      "  @decorate\n",
      "+ def fun2():\n",
      "+     return 2\n",
      "+     \n",
      "+ @decorate\n",
      "  def fun3():\n",
      "      return 3\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import difflib\n",
    "print ''.join(difflib.ndiff(s1.splitlines(1), s2.splitlines(1)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we will tell it that blank line are junk:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  \n",
      "  @decorate\n",
      "  def fun1():\n",
      "      return 1\n",
      "      \n",
      "+ @decorate\n",
      "+ def fun2():\n",
      "+     return 2\n",
      "+     \n",
      "  @decorate\n",
      "  def fun3():\n",
      "      return 3\n",
      "\n"
     ]
    }
   ],
   "source": [
    "blankline = lambda x:x.strip() ==''\n",
    "print ''.join(difflib.ndiff(s1.splitlines(1), s2.splitlines(1), linejunk=blankline))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is clearly better, as hunk do not have blank lines in the midlle, but more on sides."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Where it gets weird"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Things is, `SequenceMatcher` is also the method that help you get the proximity between two strings.\n",
    "If the sequence you pass to `SequenceMatcher` is a string, it will try to match each caracters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from difflib import SequenceMatcher"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0\n",
      "0.0\n"
     ]
    }
   ],
   "source": [
    "print SequenceMatcher('hello world','hello world').ratio()\n",
    "print SequenceMatcher('xyz','abc').ratio()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Oh, sorry, you need to explicitelty, pass the `isjunk` function. Hopefully, it accepts `None`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0\n",
      "0.0\n"
     ]
    }
   ],
   "source": [
    "print SequenceMatcher(None, 'hello world','hello world').ratio()\n",
    "print SequenceMatcher(None, 'xyz','abc').ratio()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, that's better, it goes from 0.0 for completely different strings (nothing in common) to 1.0 for perfectly matching strings.\n",
    "\n",
    "API is weird, but for compatibility we keep the old one... fine with me"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "let's try longer..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0\n"
     ]
    }
   ],
   "source": [
    "print SequenceMatcher(None, 'y'+'abc'*150,'x'+'abc'*150).ratio()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Still, don't pass it strings longer than 200 char, it automatically detect junk... Yes this is documented, but not obvisous."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.9977827051\n"
     ]
    }
   ],
   "source": [
    "print SequenceMatcher(None, 'y'+'abc'*150,'x'+'abc'*150, autojunk=False).ratio()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So let's define a custom SequenceMatcher that make sens for the rest of the post, so that `isjunk`is `None` by default, and no `autojunk` for `n > 200`, and a simple `ratio(a, b)` method as a shortcut."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def MySequenceMatcher( seq1, seq2, isjunk=None, autojunk=False):\n",
    "    return SequenceMatcher(isjunk, seq1, seq2, autojunk=autojunk)\n",
    "\n",
    "def ratio(a,b):\n",
    "    return MySequenceMatcher(a,b).ratio()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0\n",
      "0.75\n"
     ]
    }
   ],
   "source": [
    "print ratio('abc','abc')\n",
    "print ratio('abcd','abcf')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Where it gets weirder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I'll probably won't go into how we found out the following, but for some reason `ratio(a,b)` was different from `ratio(reversed(a),reversed(b))`, that is to say `ratio('ab...yz','ab...yz') != ratio('zy...ba','zy...ba')` in some case. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So let's look at what happend if we compare a string against itself, with only one modification, as a function as the position of the modification, that is to say the ratio of `aaaa...` vs `baaa...` vs `abaa...` vs `aaba...`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "aaaaaaaaaa ...\n",
      "aaaaaaaaaa ...\n",
      "-aaaaaaaaa ...\n",
      "a-aaaaaaaa ...\n",
      "aa-aaaaaaa ...\n",
      "aaa-aaaaaa ...\n",
      "aaaa-aaaaa ...\n",
      "aaaaa-aaaa ...\n",
      "aaaaaa-aaa ...\n",
      "aaaaaaa-aa ...\n",
      "aaaaaaaa-a ...\n",
      "..............\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<matplotlib.text.Text at 0x1037590d0>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": [
       "iVBORw0KGgoAAAANSUhEUgAAAYkAAAEPCAYAAAC3NDh4AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\n",
       "AAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xl8VGWaL/BfLdlDNsgeSICwmBDZVEAQMKBGRxQVBBsd\n",
       "+/boTLc99qat3WrfP+aK2q3ddo+38Tq29vjpUdCA7ItpkrBE0kQSA0kgEM3CEpIKJAESslad+0dM\n",
       "nQRSqSScU+9bVb/v5+PHVOVUnSdPDnnqfZ9z3mNQFEUBERHRAIyiAyAiInmxSBARkUMsEkRE5BCL\n",
       "BBEROcQiQUREDulWJGw2G6xWq15vT0RELmDW40337NmDyspKLF++HHFxcYNuW1dXh+zsbJhMJixa\n",
       "tAixsbF6hERERCNg0Os6iePHjyMsLMxpkdi2bRseeOABAMCWLVuwfPlyPcIhIqIREN6TCAwMtH/t\n",
       "6+srMBIiIrqW8CLRdyDj4+MjMBIiIrqW8CLRt7ltMBgERkJERNfSpXHtSGlpKYxGI1JSUuzPtbW1\n",
       "AegZUfR+7UhWVhZMJpOuMRIReZqwsDDMnj17RK/VpUjs3bsXlZWV8Pf3R1JSEhYuXAgAyM/Ph8Fg\n",
       "6Fck5syZg/Xr10NRFCxdunTQ9zWZTJg1a5YeIRMReayioqIRv1a3s5v0kJ2dzSLxnby8PCxYsEB0\n",
       "GFJgLlTMhYq5UBUVFWHJkiUjeq3wngQREcmLIwkiIg93IyMJlzautXTuUjviQ/1Fh0EEALjY2oXL\n",
       "Hd2iwyCyiwvxg5/5xieL3LJIWG0KfpNVie/PjsXCCeGiwxGC860qGXLx/M4KAIDZJPY07qutVxEY\n",
       "FOh8Qy/g7bn430vGY2zYjX+QdssiYTIa8KvFSXj5i2+RPCYQcSF+okMiL9dhteGPyyYjKljsqgE9\n",
       "BXNkpzp6GuZCG27buJ4cGYg1M2PwanYVOq020eG4nOhPzjKRIRc2mwKTUfzFoDLkQhbMhTbctkgA\n",
       "wIMpYxAzyhfvH64VHQp5OasCCJ5pItKFWxcJg8GAX9wxDofPXEJeVbPocFwqLy9PdAjSkCEXVklG\n",
       "EjLkQhbMhTbcukgAQLCfGS/dmYQ/fXkG5690iA6HvJRVUWDi2mPkgdy+SADA1KggrJ4ejddyqtHl\n",
       "Jf0JzreqZMiFLCMJGXIhC+ZCGx5RJADg4WmRiAjwwQdfsT9BridLkSDSmscUCYPBgOcWjsOX1ZeQ\n",
       "X3NJdDi643yrSnQuFEWBVQFkqBGicyET5kIbHlMkACDE34xf35mEtw+eRv2VTtHhkJewfVcgjOxJ\n",
       "kAfyqCIBACnRQViRFoXXcqvQbXObZamGjfOtKtG5kKlpLToXMmEutOFxRQIAVtwchWBfM/7K/gS5\n",
       "gNWmwCjDXBORDjyySBgNBrywOBG5lU0oOOOZ/QnOt6pE58Im0YV0onMhE+ZCGx5ZJAAg9Lv+xO8P\n",
       "nEZDK/sTpB+e2USezGOLBACkxQRjeWokXs+phtXD+hOcb1WJzoXVxp6EjJgLbXh0kQCAVdOj4Wc2\n",
       "4qPC86JDIQ9lVTiSIM/l8UWitz+xt6IRR85eFh2OZjjfqhKdC6sNMEnyL0l0LmTCXGhDkkNbX+EB\n",
       "PnhxcSLe2l+Di61dosMhDyPTKbBEWvOKIgEA0+NG4f6USLye6xn9Cc63qkTnQqbGtehcyIS50IbX\n",
       "FAkAeGx6NExG4H++rhMdCnkQjiTIk3lVkei97emekxdRdM69+xOcb1WJzkXPSEJoCHaicyET5kIb\n",
       "khzarhMe6IMXFiXid/tr0HiV/Qm6cT2L+3EkQZ7J64oEAMyMH4X7poxx6/4E51tVonPBnoScmAtt\n",
       "eGWRAIA1M2MAAJ8Usz9BN8Ym0cV0RFrz2iLR25/YeeICimuviA5n2DjfqhKdC5kuphOdC5kwF9rw\n",
       "2iIBAKODfPD8okT8dl8NmtrYn6CRkeliOiKtef2hfUtCCO6eFIHf7quBTXGf/gTnW1WicyHTKbCi\n",
       "cyET5kIbXl8kAOCfZ8ei02rDp0frRYdCbkimxjWR1lgk0NOf+PWdSdhS1oCSuhbR4QwJ51tVonMh\n",
       "00hCdC5kwlxog0XiO5FBvnhu4Ti8nluNS+3dosMhN8KeBHkyHtp93DY2FOkTw/E7N+hPcL5VJToX\n",
       "vJ+EnJgLbbBIXOP7t8ShtdOKjccsokMhN2FVeI9r8lwsEtcwGw14KT0JG0ssKKuXtz/B+VaV6FzI\n",
       "1LgWnQuZMBfaYJEYQFSwL35+R09/4jL7E+SEVQFMctQIIs2Z9XjTuro6ZGdnw2QyYdGiRYiNjXW4\n",
       "rcViQU5ODgICApCWloYJEyboEdKwzUsMxbHzV/Dm/hr8x90TYJBkzrkX51tVonMh00hCdC5kwlxo\n",
       "Q5eRREFBAdasWYPVq1fj8OHDg2779ddfY/Xq1XjwwQdRW1urRzgj9oNb49Dc3o1NJexPkGM2iU6B\n",
       "JdKaLkUiMDDQ/rWvr++g2/r5+aGtrQ1WqxXFxcXo7OzUI6QR8TEZ8XJ6Ej49ZsEJS6vocPrhfKtK\n",
       "dC5kGkmIzoVMmAtt6FIklD6nj/r4+Ay67YIFC5CdnY2tW7di8uTJaG2V649xzCg//GzBWLyWU40r\n",
       "HexP0PV6ToEVHQWRPnQpElar1f61s7l8s9mM+++/Hw8//DCuXr2KoKCgQbfv++kgLy/PJY/nJ4Vh\n",
       "XmIoXtr8NQ4edP3+B3q8YMECofuX6XHv3LOo/VuVnqv2ZchHXzLEI/LxtTkRHY/oxyNlUBTtrxrb\n",
       "vHkzHnroISiKgh07dmDZsmUAgNLSUhiNRqSkpFz3mubmZuzYsQOPP/64w/fNzs7GrFmztA53SDqt\n",
       "Nvx8+yksTY7AQ9OihMRAcvrk6zp0dNvwv26NEx0K0YCKioqwZMmSEb1Wl5HEnDlzsH79eqxfvx5z\n",
       "5syxP5+fn49Dhw7127akpASZmZnIysrCo48+qkc4mvA1GfFK+nh8UlyPkw3ip8S0+ITgKUTngveT\n",
       "kBNzoQ1dToGNi4vDY489dt3zTz/99HXPpaWlIS0tTY8wNBcb4odn5ydgbU411i2fgmA/XdJHbsZq\n",
       "U2Dm4k3koXhkD9PC8eG4bWwI/nDwDHSYqRsyngOuEp0LmS6mE50LmTAX2mCRGIF/vS0edVc6sP3E\n",
       "BdGhkARkWuCPSGssEiPgazbi5fTx+FtRHU5duCokBs63qkTnwibRAn+icyET5kIbLBIjFB/qhx/P\n",
       "S8BrOVVo7bQ6fwF5LKtNnukmIq2xSNyAxRPDMTNuFP548LTL+xOcb1WJzoVMZzeJzoVMmAttsEjc\n",
       "oB/OTcCZS+3YWX5RdCgkiEzLchBpjUXiBvl915/4qPA8vr3ouv4E51tVonMh0wJ/onMhE+ZCGywS\n",
       "Ghgb5o8fzo3H2pxqXGV/wuv0jCRER0GkDx7aGlmSHIFp0cH405euuX6C860q0bnouU5CjpGE6FzI\n",
       "hLnQBouEhp65PQFVjW3Yc5L9CW/CngR5MhYJDfmbe9Z3+vDIeVQ1tum6L863qkTnQqaL6UTnQibM\n",
       "hTZYJDQ2Ltwf/zonDq9mV6Gti/0JbyDTKbBEWmOR0MFdk0bjpqggvHPorG774HyrSnQurDZI07gW\n",
       "nQuZMBfakOTQ9jw/vj0BFQ1XkXWK/QlPZ1UUGCWZbiLSGouETgJ8THh5SRLeL6hFTZP2/QnOt6pE\n",
       "50KmxrXoXMiEudAGi4SOksID8C+3xuHVnGq0d9tEh0M6sUp0MR2R1lgkdHbP5Agkjw7Anw+d0fR9\n",
       "Od+qEp0LG3sSUmIutCHJoe25DAYDfjJ/LMrqW7G3olF0OKQDjiTIk7FIuECAjwmvpI/He4fP4XRz\n",
       "uybvyflWlehcsCchJ+ZCGywSLjJhdAC+f0ss1mZXoYP9CY8i08V0RFpjkXCh+6aMRmK4P979x41f\n",
       "P8H5VpXoXFgV9iRkxFxoQ5JD2zsYDAb8dME4HK1tQe63TaLDIY3INN1EpDUWCRcL8jXh5fQkrMs/\n",
       "i3OXRt6f4HyrSnQuZGpci86FTJgLbbBICJA8JhBPzIrBqznV6GR/wu1xJEGejEVCkGU3jUFciB/e\n",
       "O3xuRK/nfKtKdC5kGkmIzoVMmAttsEgIYjAY8Is7xuHI2cs4UMX+hDuz2gAj/yWRh+KhLVBPf2I8\n",
       "3vnyLGovdwzrtZxvVYnOBe9xLSfmQhssEoJNjgzE92ZEY21OFTqt7E+4I/YkyJOxSEhgeWokIoN8\n",
       "8ZeC2iG/hvOtKtG5kKlIiM6FTJgLbTgtEp2dna6Iw6sZDAY8t3Ac8msuIa+6WXQ4NExWBTDJUSOI\n",
       "NOe0SLz11luor693RSxebZSfGS+lJ+FPeWdQd8V5f4LzrSrRuZBpJCE6FzJhLrThtEjMnTsXZWVl\n",
       "yMzMxIULF1wRk9e6KSoIq6ZHY21ONbrYn3ALNkUBAN6ZjjyW2dkG6enpAICuri7k5ubiwoULyMjI\n",
       "wPnz55Gamqp7gN7mkWmROHb+Cj78qhb/NjfB4Xacb1WJzIVMowiAx0VfzIU2nI4kuru7AQBnz55F\n",
       "Y2MjpkyZgoKCAmzcuFH34LyRwWDA8wsTcbC6Gfk1l0SHQ06wH0GezmmR+OCDD7B+/XrU1dVh9erV\n",
       "mD17NjIyMjB9+nRXxOeVQvzN+PWdSXj74GlYWgY+cYDzrSqRuZBtJMHjQsVcaMNpkQgNDcWqVasw\n",
       "b968fs9HREToFhQBqdHBWJEWhbU5Vei2KaLDIQdkKxJEWjMoiqL5X6C6ujpkZ2fDZDJh0aJFiI2N\n",
       "dbhtVVUVCgsLYbPZMG/ePIwdO9bhttnZ2Zg1a5bW4UrLpij4zReVSAr3x9Nz4kWHQwNoauvCv24q\n",
       "R+bjaaJDIXKoqKgIS5YsGdFrh30xXV1dndNtCgoKsGbNGqxevRqHDx8edNvy8nKsWLECjz76KEpK\n",
       "SoYbjkczGgx4YXEiciubcPg0+xMystnkueEQkR6cHt5lZWX9Hh86dMjpmwYGBtq/9vX1HXRbq9UK\n",
       "m80Gq9UKHQY1bi/0u/7EHw6eRkOr2p/gfKtKaE9ConWbAB4XfTEX2nBaJCoqKvo9NpudnjXb74+9\n",
       "j4/PoNtOmzYNb775Jt566y3MnDnT6Xt7o7SYYCxPjcTrOdWwsj8hFfYkyNMNe6Bsszm/yMtqtdq/\n",
       "Njj5lHX06FG8+OKL+OUvf4kjR44MNxyvsWp6NPzMRnxUeB4AzwHvS+h1EpKNJHhcqJgLbTgcFuzY\n",
       "sQNtbW0oLy9HV1eX/fno6Ginb9rW1gagZ0TR+zUAlJaWwmg0IiUlxf5c73SU0Wh0OuoAeoaQvb/8\n",
       "3uGkNzw2GgxYHFCH/yoLwM2xwbglIUSq+Lz1cUOHASZjhDTx8DEfO3o8Uk7Pbtq+fTuWLVs2rDet\n",
       "ra3F/v37oSgKli5diqioKADA+++/D4PBgKeeesq+bXl5OY4fPw4ASE1NxZQpUxy+r7ed3TSQo7VX\n",
       "8HpuNZ6Mu4x775wvOhwp9P3g4GqVF9vw233VeO+Rm4Ts/1oicyEb5kJ1I2c3OW0w3HvvvcN+07i4\n",
       "ODz22GPXPf/0009f99zUqVMxderUYe/DW02PG4X7bxqDz0904G7OhwtnVfg7IM/mtCcxlEY1udZj\n",
       "M2IQHh6K//na+enI3oBrN6n4yVnFXGhj2I3rffv26RAGDYfJaMCvFidh98kLKDp3WXQ4Xk22xjWR\n",
       "1oZdJJqbeVMcGRwvOowXFyXhd/trcPFql/MXeDCxazcBRokupuO1ASrmQhsO55LWrVuHlStXYteu\n",
       "Xf0ujisvL8fy5ctdEhwNbmb8KNw3ZQzeyK3GG/cmSzXt4S04kiBP57BIrFy5EuHh4QgNDe1XFLZs\n",
       "2eKSwGhwvfOta2bG4Fe7v8EnxXV4YpbjNbI8GXsSKs7Dq5gLbTgcKEdGRsJsNiM5Obn/C2QaW5O9\n",
       "P7HzxAUU114RHY7XsXEkQR7O6V/8adOm9XuckZGhWzA0dH3nW0cH+eD5RYn47b4aNHlhf0J0T0Km\n",
       "Bf44D69iLrQx7MPb2YJ9JMYtCSG4e1IEfru/xn7fZdKf1caRBHk2p0Vi8+bNroiDhmmg+dZ/nh2L\n",
       "TqsNG4rrBUQkjvC1m9iTkBJzoQ2nReLaBf12796tWzB0Y0xGA359ZxK2Hm/AsfMtosPxCrI1rom0\n",
       "5rRI+Pr6wmKx2B93dHToGhANjaP51sggXzy3cBze2FeN5jbv6E+Iv5+EsN1fh/PwKuZCG06LRGtr\n",
       "K95++21kZmYiMzOTd49zA7eNDUX6xHD8jv0J3fU0riWqEkQac7owU0BAAF5//XX7Y14nIQdn863f\n",
       "vyUOz++oQOYxC1ZNd768uzsT3ZMwStS45jy8irnQhtORxLXLy9588826BUPaMRsNeCk9CZtKLCir\n",
       "Y39CL+xJkKdzWiSCg4P7PZ4wYYJuwdDQDWW+NSrYFz+/Yxxey63G5fZuF0QlhtjrJOQ6BZbz8Crm\n",
       "QhvDvk6isLBQjzhIJ/MSQ7FwfBje3F8DJ/eXohGwKnJdTEekNac9iWPHjqG8vBzNzc0ICQlBdXU1\n",
       "Zs+e7YrYaBDDmW/9wa1x+MWOCmwqsWDFzZ7XnxA592yTbCTBeXgVc6ENp5+BysvL8eijjyI2Nhar\n",
       "V6/GxIkTXREXacjHZMTL6Un47JgFJyytosPxKLJdTEektSFdJwEAVqsVAODj46NvRDQkw51vjRnl\n",
       "h58uGIvXcqpxpcOz+hPCexISFQnOw6uYC204LRKdnZ0Aeq68tlqtnNd2Y/OTwjAvMRRvHTjN36NG\n",
       "bAqkupiOSGtOi8TixYsB9MzvrV+/HiEhIXrHREMw0vnWp26Lw4XWTmwpa9A4InFE30+C10nIibnQ\n",
       "htPGdVRUlP3/jz/+uO4Bkb58TUa8kj4eP9l2CinRQZgSGSQ6JLfGngR5umGfvNc7/URi3ch8a2yI\n",
       "H56dn4C1OdVo8YD+hPCehEQ1gvPwKuZCG8MuEnv27NEjDnKxhePDcWtCCP5w8Az7Ezeg5zoJiaoE\n",
       "kcaGXSSuXTqcxNBivvXf5sSj7koHtp+4oEFE4ojuSchUJDgPr2IutOGwJ/H73/8e48aNu+758vJy\n",
       "LF++XNegyDV8zUa8nD4eP9t+CjdFBWHSmEDRIbkd2Rb4I9Kaw5HExIkTsXLlyuv+S0tLc2V85IBW\n",
       "863xoX748bye/kRrp1WT93Q14T0JiUYSnIdXMRfacFgk5s2bN+DzYWFhugVDYiyeGI6ZccH4Yx6v\n",
       "nxguK6+TIA/nsEhERw+8xk/vdRMkltbzrT+cm4Azze3YWX5R0/d1BfYkVJyHVzEX2uD6lQQA8Puu\n",
       "P/FR4Xl8e/Gq6HDchmwL/BFpbdhFYt++fTqEQcOlx3zr2DB//HBuPNbmVOOqG/UnhN/jWqKRBOfh\n",
       "VcyFNoZdJJqbm/WIgySxJDkC06KD8Z9f8vqJoei5x7XoKIj04/AU2HXr1mHlypXYtWsXAgPVUyN5\n",
       "Cqwc9Jxvfeb2BPxk60nsOdWIe6eM1m0/WhF9j2uZpps4D69iLrThsEisXLkS4eHhCA0N7VcUtmzZ\n",
       "4pLASBx/c8/6Ts/trMDUyECMjwgQHZK0ZGtcE2nN4UA5MjISZrMZycnJ/V9g5NhaBnrPt44L98fT\n",
       "t8VhbU412rrk7k8I70lINJLgPLyKudCG07/406ZN6/c4IyNDt2BILndPHo0pkYH4v4fOig5FWuxJ\n",
       "kKcb9uFdUVGhRxw0TK6ab/332xNwsuEqsk7Je/2E8OskJBpJcB5exVxow+n9JLZt24b29nYYvvuH\n",
       "0NbWhtTUVKdvXFdXh+zsbJhMJixatAixsbEOt33zzTcxadIkAMCFCxfw1FNPDTV+0lmAjwkvpyfh\n",
       "hV3fYEpkIBLD2Z/oy6ooMLInQR7MaZFob2/Ho48+an/c3T20+w8UFBRgzZo1AHqa3YOdEfXss8/C\n",
       "398fAJciH6q8vDyXfVIaHxGAH9wah1dzqvHOg1Pgb5ZrfsWVubiWbI1rkbmQDXOhjSHd4zorKwv7\n",
       "9u3Dvn378Oc//3lIb9z3tFlfX99Bt+0tEBaLxX4nPJJLxuQITIwIwDr2J/qxKXLddIhIa05HEp2d\n",
       "nZgxYwbM5p5Nb7755iG9cd8LsXx8fIb0muPHj2Pu3LlD2tbbufoTksFgwE/mj8W/bz2J7G8asSQ5\n",
       "wqX7H4zYnoRcNx3iJ2cVc6ENpyMJo9GIqKgoREREICIiAvX19UN6Y6tVPW3SMMTGXnt7u31UQfIJ\n",
       "9O3pT/y/f5zDmeZ20eFIQbZTYIm05nQkUVNTg/Xr19tHEuXl5fjNb37j9I3b2toA9Iwoer8GgNLS\n",
       "UhiNRqSkpPTb3mazDekajL7zjL3nQXvj477ngLt6/0/Onoq1OVVYNeYifIzi83FtTly5/9arAfaR\n",
       "hAzHR0lJCX70ox9JE4/Ix++++y7S0tKkiUf045EyKE4W6Kmrq0NMTIz9cX19vcNlxPuqra3F/v37\n",
       "oSgKli5dau81vP/++zAYDNedwVRdXQ2bzYYJEyY4fM/s7GzMmjXL6b69gcimnKIoeC23GsG+Jvx0\n",
       "wfV3L3Q1kbl4fEMpfv9PkxE9avC+m6uwWatiLlRFRUVYsmTJiF7rtEhc69qi4UosEvJo7bTix1tO\n",
       "4snZsbhzYrjocIR57JNSvPPgZIwJkqNIEA3kRorEsM9l/Mc//jGiHZFnCfI14ZX0JKzLP4tzl7y3\n",
       "PyHbxXREWnNYJBoaGtDd3Y2GhoZ+/7W2troyPnJAhnVpkscE4olZMXg1pxqd3TZhcQhfu0mis5tk\n",
       "OC5kwVxow2GRyMzMRFNTE/72t7+hrKzM/t9Qz24i77DspjGIC/HDe4fPiQ5FCNkupiPSmsOzm555\n",
       "5hkAQHJycr/7WvOmQ3KQpSFnMBjwizvG4ZnN5ThQ2YSFE1zfnxB7PwlAphohy3EhA+ZCG057Eteu\n",
       "+nrt0uFEQb4mvJw+Hu8cOovayx2iw3EpG0cS5OGcFolrl9S4dulwEkO2+dbJkYH43oxorM2pQqfV\n",
       "tf0J4T0JiRrXsh0XIjEX2nBaJP7617+ipqYGBQUF+OSTT5h4cmh5aiQig3zxl4Ja0aG4hE1RYJNs\n",
       "uolIa06LxJgxY5CYmAiLxYLvfe97sFgsroiLnJBxvtVgMOC5heOQX3MJedWu612JyoVNAUyGoS87\n",
       "4woyHheiMBfacFokbLaeqYPeZTl4+1IazCg/M15KT8Kf8s7g/BXP7k/wzCbyBk7/4re0tOD06dMY\n",
       "PXo0ALk+NXkzmaf9booKwqrp0XgtpxpdLuhPiMqFjEVC5uPC1ZgLbTgtEvPnz0dpaSluvfVWfP31\n",
       "1zh//rwr4iI398i0SIQHmPHhV57bn5CtaU2kh2Gv3SQS125yL5fbu/HMlnL8eN5YzEsMFR2O5prb\n",
       "uvD0pnJkPp4mOhSiQbl07SaioQrxN+PXdybh7YOnYWnpFB2O5qzfNa6JPBmLhJtyl/nW1OhgrEiL\n",
       "wms51ei26TNoFdmTMLInIS3mQhssEqS7FTdHIcjXhP8+4ln9CfYkyBuwSLgpdzoH3Ggw4IXFicj5\n",
       "tgmHT1/S/P2FXSch4dlN7nRc6I250AaLBLlEqL8ZL92ZhD8cPI2GVs/oT1ht7EmQ52ORcFPuON86\n",
       "LSYYy1Mj8VpONawa9ieE9SQku5cE4J7HhV6YC22wSJBLrZoejQAfIz4qdP/rbWS8mI5IaywSbspd\n",
       "51uNBgN+uSgReysaceTsZU3eU1QuZGxcu+txoQfmQhssEuRy4QE++NWdiXhrfw0utnaJDmfErDbA\n",
       "xH9B5OF4iLspd59vvTl2FO6/aQxez73x/oTQnoRkIwl3Py60xFxog0WChHlsRgxMRuB/vq4THcqI\n",
       "sCdB3oBFwk15wnyryWjArxYnYc/Jiyg6N/L+hLCehE2BUbKRhCccF1phLrTBIkFChQf64IVFifjd\n",
       "/ho0XnWv/kTPKbCioyDSFw9xN+VJ860z40fhvilj8Ma+kfUnxK3dBPYkJMZcaINFgqSwZmYMFAVY\n",
       "X+w+/QkZL6Yj0hqLhJvytPnW3v7EjhMXcLT2yrBey7WbVJ52XNwI5kIbLBIkjdFBPnh+USJ+u68G\n",
       "TW3y9yd6ToEVHQWRvlgk3JSnzrfekhCCuyZF4Hf7amAb4k0ThfYkJBtJeOpxMRLMhTZYJEg6/zw7\n",
       "Fh1WGz49Wi86lEHJeDEdkdZYJNyUJ8+3mowG/PrOJGwpa0BJXYvT7UVeJyHbSMKTj4vhYi60wSJB\n",
       "UooM8sVzC8fh9dxqXGrvFh3OgKw2jiTI87FIuClvmG+9bWwo0ieGO+1PiFu7Sb4F/rzhuBgq5kIb\n",
       "kh3iRP19/5Y4tHZasfGYRXQo17EpCoySTTcRaY1Fwk15y3yr2WjAS+lJ2FhiQVn9wP0JoT0Jyaab\n",
       "vOW4GArmQhssEiS9qGBf/PyOnv7EZYn6E7zimryBLkWirq4OH3/8MTZs2IDz553fprKyshKZmZnY\n",
       "tm0bOjs79QjJ43jbfOu8xFDckRSGtw7UQLmmPyHyOgnZaoS3HReDYS60oUuRKCgowJo1a7B69Woc\n",
       "Pnx40G2bm5tx/vx5rFy5Eg888AB8fX31CIk8wA9ujUNTWzc2lTaIDgWAnNNNRFrTpUgEBgbav3b2\n",
       "R7+4uBhBQUH4/PPPcerUKT3C8UjeON/qYzLi5fQkfHq0Hicsrfbnhd7jWrKhhDceF44wF9rQpUj0\n",
       "nQ7w8fEZdFuLxYLm5mY8/PDDqKiogM1m0yMk8hAxo/zwswVj8VpONa50iO1P9CzwJzQEIt3pcohb\n",
       "rVb714YhDMcXLlwIAIiPj0djY+Og2/adZ8zLy/Pax71fyxKPKx/PTwrDvMRQvLT5axw8eH1OXBVP\n",
       "zdlzOF1dLTwffR+/++67UsUj8vG7774rVTyiH4+UQbm2C6iBzZs346GHHoKiKNixYweWLVsGACgt\n",
       "LYXRaERKSop92+LiYgQHByM5ORm5ublYsGCBw9FHdnY2Zs2apXW4bikvL8+rh9OdVht+vv0UliZH\n",
       "ILL5lJBcvJt/FtGjfPHwtCiX79sRbz8u+mIuVEVFRViyZMmIXmvWOBYAwJw5c7B+/XooioKlS5fa\n",
       "n8/Pz4fBYOhXJGbMmIGNGzeipKQEkZGRTqenqIe3H/y+JiNeSR+Pn2w7hbX3iPngIOMCf95+XPTF\n",
       "XGhDlyLd70nYAAAQKElEQVQRFxeHxx577Lrnn3766QG3X7FihR5hkIeLDfHDs/MT8GpOFd59aCqC\n",
       "fE0u3b+MC/wRaY1tNzelxVyjJ1g4PhwJplb84eDp666f0FvPPa5dukuneFyomAttsEiQ27s7qhO1\n",
       "lzuw/cQFl+5XxlNgibSmy3QT6Y/zrarFCxdg0qV2/Gx7BVKigpA8JtD5izRgtSkwsichLeZCGxxJ\n",
       "kEeID/XHM/MS8GpONVo7rc5foAGOJMgbsEi4Kc63qnpzcefEcMyIC8af8lzTn+i5x7XuuxkWHhcq\n",
       "5kIbkh3iRDfmR3MTcLq5HbtOXtR9XzKeAkukNRYJN8X5VlXfXPiZjXg5fTz++8h5fHvxqq77tUl4\n",
       "CiyPCxVzoQ0WCfI4Y8P88W9z4rE2pxpXdexPcCRB3oBFwk1xvlU1UC6WTopAanQQ/vPLM7r1J6wS\n",
       "LvDH40LFXGhDskOcSDs/vn0svm1sw55Tgy8aOVI9F9NxJEGejUXCTXG+VeUoF/5mI15JT8KHX9Wi\n",
       "qrFN8/3KeAosjwsVc6ENFgnyaInhAXj6tjiszalGW5e2/Qmu3UTegEXCTXG+VeUsF3dPHo3JkYF4\n",
       "59BZTfcrY+Oax4WKudAGiwR5hWdvT8BJSyuyTml3/YSMF9MRaY2HuJvifKtqKLkI8DHhlSXj8V+H\n",
       "z6GmSZv+hFXh2k0yYy60wSJBXmN8RAD+5dY4vJpTjfbuG7+XOnsS5A1YJNwU51tVw8lFxpTRmBAR\n",
       "gD8fOnPD+7WxJyE15kIbLBLkVQwGA346fyzK6luxt+LGrp9gT4K8AQ9xN8X5VtVwcxHoa8LL6Ul4\n",
       "7/A5nG5uH/F+ZZxu4nGhYi60wSJBXmni6EA8OTsWa7Or0DHC/oSMp8ASaY1Fwk1xvlU10lz809TR\n",
       "GBfuj3f/MbLrJ2QcSfC4UDEX2mCRIK9lMBjwswXjUFzbgtxvm4b9eqsCmOSqEUSaY5FwU5xvVd1I\n",
       "LoJ8TXglPQnr8s/i3KXh9SdkHEnwuFAxF9pgkSCvlzwmEE/MisGrOdXoHEZ/gj0J8gYsEm6K860q\n",
       "LXKx7KYxiAvxw38VnBvya2QcSfC4UDEX2mCRIEJPf+IXd4zDV2cu40CV8/6EoiiwKYBkNYJIcywS\n",
       "borzrSqtchHka8LL6ePxzpdncf5yx6Db9hYIg2TTTTwuVMyFNlgkiPqYHBmI782Ixqs5Vei0Ou5P\n",
       "yDjVRKQHFgk3xflWlda5WJ4aicggX/yloNbhNrI2rXlcqJgLbbBIEF3DYDDguYXjkF9zCXnVzQNu\n",
       "w5EEeQsWCTfF+VaVHrkY5WfGS+lJ+FPeGdRdub4/IeuFdDwuVMyFNlgkiBy4KSoIq6ZHY21ONbqu\n",
       "6U9wJEHegkXCTXG+VaVnLh6ZFonwADM+/Kp/f4I9CfkxF9pgkSAahMFgwPMLE3Gwuhn5NZfsz3Mk\n",
       "Qd6CRcJNcb5VpXcuQvzN+PWdSXj74GlYWjoByHvDIR4XKuZCGxIe5kTySY0Oxoq0KLyWU41umwKr\n",
       "osAo4XQTkdZ0KRJ1dXX4+OOPsWHDBpw/f37Qbbdv344tW7Zgy5YtKCkp0SMcj8T5VpWrcrHi5igE\n",
       "+Zrw30dqpZ1u4nGhYi60YdbjTQsKCrBmzRoAwJYtW7B8+XKH2/r7++Ouu+7SIwwiTRkNBrywOBE/\n",
       "2lyOIF+TlI1rIq3pUiQCAwPtX/v6+g66rdVqxeeffw5FUTB+/HjMmjVLj5A8DudbVa7MReh3/Ylf\n",
       "7foGSRH+LtvvUPG4UDEX2tClSCiKYv/ax8dn0G0zMjLsX+/evVuPcIg0lRYTjMdnxaDw7BXRoRDp\n",
       "TpeehNVqtX89nFUynRUUUnG+VSUiF6unR+P/3DPB5ft1hseFirnQhi4jiba2NgA9I4rerwGgtLQU\n",
       "RqMRKSkp9udqamqQmJgIAGhvH/z2kWFhYSgqKtIhYvcTGBjIXHyHuVAxFyrmQhUWFjbi1+pSJObM\n",
       "mYP169dDURQsXbrU/nx+fj4MBsN1RaKgoAAAMGPGjEHfd/bs2XqES0REDhiUvg0EIiKiPngxHRER\n",
       "OcQiQUREDrFIEBF5AJvN1u/MUq3o0rjWWl1dHbKzs2EymbBo0SLExsaKDsnlysrKcPLkSdhsNsyd\n",
       "OxcJCQlem5e2tjb88Y9/xJNPPom4uDgA3nuMVFZWorCwEH5+fsjIyEBjY6NX5qGqqgqFhYWw2WyY\n",
       "N28exo4d61XHxJ49e1BZWYnly5c7/Tcx7LwobmDr1q32rzdv3iwwEnH2799v/3rnzp2KonhvXnbv\n",
       "3q0UFhYq586dsz/njbloampS8vLy+j3njXlQFEXZtWuX/Wtv/fdRVlY2pH8Tw82LW0w3DWeZD0+1\n",
       "cOHC657zxrw0NTUhMDAQ/v79l8TwxlwUFxcjKCgIn3/+OU6dOgXAO/MA9FzA2zvdonx3wqa35qKX\n",
       "o59/uHlxiyKhDGOZD0/397//HbfddhsA78xLXl7egGvyeGMuLBYLmpub8fDDD6OiogI2m80r8wAA\n",
       "06ZNw5tvvom33noLM2fOBOCdx0Rfjn7+4ebFLXoSI13mw9Ps378fkyZNwpgxYwB4Z17q6+uxbds2\n",
       "WCwWJCUl2edfvTEXgDrCjI+PR2Njo9fm4ejRo3jxxRdhs9mwY8cOPPDAA16bi16Ofv7h5sUtioSj\n",
       "ZT68ycGDBxEdHY2kpCT7c96Yl6eeegoAcPz48X5LDXhjLiZPnozKykokJyejqakJqampXpkHQJ02\n",
       "MRqN9k/H3pqLXo5+/uHmxS2uuK6trcX+/fvty3xERUWJDsmlLBYLPvzwQ0ydOhUAcOXKFTzxxBNe\n",
       "m5fGxkZs3LgRSUlJuPvuuwF47zGyceNGmEwmREZGYsGCBV6bh/Lychw/fhwAkJqaiilTpnhVLvbu\n",
       "3YvKykr4+/sjKSkJCxcudPjzDzcvblEkiIhIDLdoXBMRkRgsEkRE5BCLBBEROcQiQUREDrFIEBGR\n",
       "QywSRETkEIsEAQAaGhqwbt26Ab+3Y8eOQV+7bt06NDQ06BHWiBQWFmLjxo3YsWMHsrKyXLrvL774\n",
       "Aps2ber33GC57erqwieffIJt27Zh586dqKmp6ff9G81tYWEh3nvvvRG/XrQvv/wSTU1NosPwam5x\n",
       "xTXpLzw8HCtXrhzwe86uyly5ciXCw8P1CGtEKisrHf4servnnnvw+eef93tusNx+++23SEtLQ1pa\n",
       "2oDfv9Hczp49+7rC4066urrQ3d0tOgyvxiLhJo4cOYIDBw4gJiYGgYGB6OrqQlhYGO666y4AQHt7\n",
       "O3bs2AEfHx9YrVaMGjXK/j0A2Lx5MxRFgY+PD+rr67F48WIkJycDAEpLS/HNN9/g0qVLePLJJ+2v\n",
       "6e7uxu7du1FeXo4tW7YAACZNmoTU1FQAQGdnJ/bs2YNvvvkGTzzxBCIjI/vFnJWVhZaWFphMJnR1\n",
       "dWHZsmXw8/NDVVUVNmzYgLFjxyI4OBgdHR249957ERIS4jQPg/2cvfH0jXfevHmIjo4e9D137tyJ\n",
       "r776CmlpaWhqaoKfnx86Ojrw4IMPIjIyctB9dnd3Y/PmzTAajVAU5bq1+R3ltvd7hw4dAtBTLMLD\n",
       "w7Fo0SKnue3u7sa2bdtgNBphMBhgMBhw//33w2jsmRjYu3cvGhsbYTabYTKZYLPZnOYV6FnTZ9eu\n",
       "XfYF4FpbWzFu3DjMnz8fNpsNmzZtgtlshqIoCA4Otl/tDvTcz6CqqgozZ87E6dOnAQAZGRkICQlB\n",
       "aWkpTpw4AR8fH7S0tCAjI6Pf+mOO9nn8+HEUFRXh3LlzCAoKgtFoxH333QezuefP1oEDB2CxWODr\n",
       "64v29nb7/oCefy+7d+/GE088gUOHDsHX1xfTp0/HpEmThpQL6mOoa5WTeK+//rrS0NBgf3z48GGl\n",
       "rKxMURRFyczMVFpaWuzfO3XqlJKfn68oiqJYrVblgw8+ULq6uhRFUZSLFy8qly9fvu79P/vsswH3\n",
       "6+j5Xrm5uYrFYun33JdffqmcPHnS/vjKlSvKpk2b7I//8pe/2ONpa2vrt8b9YAb7OYca77UsFouS\n",
       "lZWlKIqifPzxx/bncnJynO5z+/bt1/1OMjMzr9uHo5jKysrsv8OBDJTbrVu3KnV1dfbH9fX1yt69\n",
       "e+3v1zcfDQ0NyhtvvOHw/fvavXu3cvHiRfvjCxcuKCdOnBhw208//fS6595++23l2LFjg+6js7Oz\n",
       "3z0MnO0zNze3X357lZWVKQcPHuz3vtfm/bPPPlP27NkzaDzkHEcSbiQ+Pt7+CQwAZsyYgS+++AIp\n",
       "KSlQFAVBQUH2702aNAklJSUAehY9W7ZsGfbt24fu7m5cvXq136dAPZw7dw633367/XFwcHC/74eE\n",
       "hNg/Efr7+w95SmGwn/NG9C4K13ufCpPJZP90O9g+W1parvud9H6S1ovFYkF+fv6A8VdUVOCee+6x\n",
       "Pz9mzBgkJCQM6X1bWloQERFhfzx69GiMHj0aANDR0YGsrCxYrVYYjUZ8++23170+Pj5+wGmz8vJy\n",
       "lJaWwsfHB0ajsd8qpIPts5cywMpBlZWVaG9vt48YgZ5RyLX65oJGhkXCjZw7dw4XLlyw/1EqLi7G\n",
       "lClTAPQUgpaWFvsf41OnTtmX0T579iz8/f2xdOlSAEBzczMOHDiA++67T7dYExIScOrUKUyePBlA\n",
       "zx8DLQz0c97obSkH+iPkbJ+9uQ0KCur3OykqKnL6ftfue7jLWE+YMAHTpk3rtzBbb5GdNGkSiouL\n",
       "MXfuXAA9TfMzZ84M6X39/f3R2Nho/6Nts9nsq8zu2rULS5YssU/nDPQHeSDt7e04evQoVq1aBaBn\n",
       "Gq3viRCD7RMAzGbzgPdtnjZtGurq6uw/Z98ckLa4wJ8b2bBhA8xms/2PyujRo7F48WIA6ly92WyG\n",
       "zWZDUFCQ/VNUUVERjh8/juDgYBgMBrS2tuL+++9HSEiIfe7bZrOhpKQEaWlpCAsLs78v0DP329jY\n",
       "CKPRiO7ubtx+++2IiYmxz7dXVlYiOjoaQUFBmDt3LmJiYgCoPQmj0Yiuri488MAD8PPzQ2lpKTZv\n",
       "3oxHHnkEKSkpOHLkCLKysvDss89i1KhRg+ZgsJ/z8uXLyM3NxbFjx5CWlgaDwYAlS5ZcN4q51q5d\n",
       "u/DNN9/gmWeewYYNGzBr1izExMTgo48+wrPPPovu7m6H++zu7sbGjRvtn5KDg4Px1VdfYc2aNYiN\n",
       "jR00twUFBSguLgYAREVFISEhAbfccgsADCm37e3tAHo+5cfHx9tHbn//+9/R1NQEf39/tLe3w2Kx\n",
       "YO7cufb3dqS7uxtbt2619zGsVivuuOMOxMTEoKysDMePH4ePjw+6u7tRUVGBmTNnIiMjY8C8p6en\n",
       "23+XGzZsgL+/PxRFgaIoOHHiBNasWYOkpKRB9wn0rHi8fft2++8wODgY6enpAHqO69OnT/cbnTz0\n",
       "0EP232lhYaF9ZDN9+nSMHz9+0J+fBsYi4UYyMzOFnbVDRN6J10m4iSNHjqC8vBxbt27F5cuXRYdD\n",
       "RF6CIwkiInKIIwkiInKIRYKIiBxikSAiIodYJIiIyCEWCSIicohFgoiIHPr/DSffI6roES0AAAAA\n",
       "SUVORK5CYII=\n"
      ],
      "text/plain": [
       "<matplotlib.figure.Figure at 0x103754c90>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "n = 100\n",
    "step = 1\n",
    "s1 = u'a'*n\n",
    "r = lambda x : ratio(x, s1)\n",
    "\n",
    "def modified(i):\n",
    "    \"\"\" return the string s1, where the i-th is replaced by -\"\"\"\n",
    "    return s1[:i-1]+u'-'+s1[i+1:]\n",
    "\n",
    "xx = range(1, n, step)\n",
    "\n",
    "\n",
    "print(s1[:10]),'...'\n",
    "for i in range(10):\n",
    "    print(modified(i)[:10]),'...'\n",
    "print('..............')\n",
    "distance = map( r, [modified(i) for i in xx])\n",
    "\n",
    "plt.plot(xx, distance)\n",
    "plt.ylabel('similarity')\n",
    "plt.xlabel('position of modified caracter')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "WWWHHHHAAAAAT ???"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hum..let's look with some other string, basically same as before, but with repeating sequence `ababab..`, `abcabcabcabc...`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.legend.Legend at 0x103b97ed0>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": [
       "iVBORw0KGgoAAAANSUhEUgAAA7QAAAHuCAYAAACvTUAWAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\n",
       "AAALEgAACxIB0t1+/AAAIABJREFUeJzt3X1wleWd//FPnmN4FJGQYDEqD/54UsBFa12xQGPaQUul\n",
       "IQhE11nUVSodpet2sNuZZWq7q9iuyxbXJe3++ttpISoPPhRialToKVQQoggpVUrBVg3BBirYBEjO\n",
       "/fuDySkBkpMr5D4nV77v10ynuU/uO+cib6J+zzlXTkoQBIEAAAAAAPBMarIXAAAAAABAZzDQAgAA\n",
       "AAC8xEALAAAAAPASAy0AAAAAwEsMtAAAAAAAL4U20EajUTU3N4f15QEAAAAAxqWH8UUrKiq0b98+\n",
       "zZgxQ/n5+e2eW1tbq6qqKqWlpWny5MnKy8sLY0kAAAAAgB4mJaz3oa2pqVH//v3jDrQvvPCCbr31\n",
       "VknSunXrNGPGjDCWAwAAAADoYZK+hzYnJyf2cWZmZhJXAgAAAADwSdIH2tOfIM7IyEjiSgAAAAAA\n",
       "PgllD62L039xVEpKSrvnVlZWKi0tLewlAQAAAACSoH///po4cWKHz0/oQLtr1y6lpqZq1KhRsdsa\n",
       "GhoknXqmtuXjtqSlpWnChAmhrhEAAAAAkBw7duxwOj+Ulxy/8sorikQieuWVV7Rp06bY7Vu2bNHm\n",
       "zZtbnXvttddq5cqVWrlypa699towloMeIhKJJHsJSBLa20Z/u2hvG/3toj1chPIM7bRp0855+913\n",
       "333Wbfn5+br99tvDWAYAAAAAoAcL7W17wlBVVcVLjgEAAACgh9qxY4emTp3a4fOT/luOAQAAAADo\n",
       "DAZaeIP9FHbR3jb620V72+hvF+3hgoEWAAAAAOAl9tACAAAAALoF9tACAAAAAExgoIU32E9hF+1t\n",
       "o79dtLeN/nbRHi4YaAEAAAAAXmIPLQAAAACgW2APLQAAAADABAZaeIP9FHbR3jb620V72+hvF+3h\n",
       "goEWAAAAAOAl9tACAAAAALoF9tACAAAAAExgoIU32E9hF+1to79dtLeN/nbRHi4YaAEAAAAAXmIP\n",
       "LQAAAACgW3DdQ5se4lq6hVHLn072EgAACdY3K0u//vu/6/D5k578oY5l9Ph/JQIAukDN/fcmewk4\n",
       "TY//t3dn/sIVllWrcv74Dp9fMfh6FdVudr6f7mr2YxO16uHtyV7GWSKRiG644YZkLyNpDsy6T5c+\n",
       "81Syl5EU1ttb15n+rg9mHstI5z9QuiF+9m2jv120hwv20AIAAAAAvMRAC2/wSJ1dtLeN/nbR3jb6\n",
       "20V7uGCgBQAAAAB4iYEW3uA9yeyivW30t4v2ttHfLtrDBQMtAAAAAMBLDLTwBvsp7KK9bfS3i/a2\n",
       "0d8u2sMFAy0AAAAAwEsMtPAG+ynsor1t9LeL9rbR3y7awwUDLQAAAADASwy08Ab7KeyivW30t4v2\n",
       "ttHfLtrDBQMtAAAAAMBLDLTwBvsp7KK9bfS3i/a20d8u2sMFAy0AAAAAwEvpyV5Ad9QnK02FZdUd\n",
       "Pv+hENeCv2I/hV20t43+dtHeNvrbRXu4YKA9h9Wl45zOr/hWSAsBAAAAALSJlxzDG+ynsIv2ttHf\n",
       "LtrbRn+7aA8XDLQAAAAAAC8x0MIb7Kewi/a20d8u2ttGf7toDxcMtAAAAAAALzHQwhvsp7CL9rbR\n",
       "3y7a20Z/u2gPFwy0AAAAAAAvMdDCG+ynsIv2ttHfLtrbRn+7aA8XDLQAAAAAAC8x0MIb7Kewi/a2\n",
       "0d8u2ttGf7toDxcMtAAAAAAALzHQwhvsp7CL9rbR3y7a20Z/u2gPFwy0AAAAAAAvpSd7AT1BU1a2\n",
       "KgZfn+xldJ2Hkr2Ac4tEIjxiZxTtbaO/XbS3jf520R4uGGi7wPQDrzpfU1hWrcr5452uWbq4Qt/4\n",
       "bpHzfbn6v49NDP0+AAAAAOB88ZJjeINH6uyivW30t4v2ttHfLtrDBQMtAAAAAMBLDLTwBu9JZhft\n",
       "baO/XbS3jf520R4uGGgBAAAAAF5ioIU32E9hF+1to79dtLeN/nbRHi4YaAEAAAAAXmKghTfYT2EX\n",
       "7W2jv120t43+dtEeLhhoAQAAAABeYqCFN9hPYRftbaO/XbS3jf520R4uGGgBAAAAAF5ioIU32E9h\n",
       "F+1to79dtLeN/nbRHi4YaAEAAAAAXkpP9gKs6pOVpsKyaqdrCkNaiy/YT2EX7W2jv120t43+dtEe\n",
       "Lhhok2R16Tjna5YurghhJQAAAADgJ15yDG+wn8Iu2ttGf7tobxv97aI9XDDQAgAAAAC8xEALb7Cf\n",
       "wi7a20Z/u2hvG/3toj1cMNACAAAAALzEQAtvsJ/CLtrbRn+7aG8b/e2iPVww0AIAAAAAvMRAC2+w\n",
       "n8Iu2ttGf7tobxv97aI9XDDQAgAAAAC8xEALb7Cfwi7a20Z/u2hvG/3toj1cMNACAAAAALzEQAtv\n",
       "sJ/CLtrbRn+7aG8b/e2iPVww0AIAAAAAvJSe7AWg45pSU7R0cUX4d9Q//LvojEgkwiN2RtHeNvrb\n",
       "RXvb6G8X7eGCgdYj3/zOzc7XFJZVq3L+eKdrZj/2iPP9AAAAAECi8ZJjeINH6uyivW30t4v2ttHf\n",
       "LtrDBQMtAAAAAMBLDLTwBu9JZhftbaO/XbS3jf520R4uGGgBAAAAAF5ioIU32E9hF+1to79dtLeN\n",
       "/nbRHi5C+S3HtbW1qqqqUlpamiZPnqy8vLw2z62rq9Orr76qCy64QGPHjtXll18expIAAAAAAD1M\n",
       "KM/Qbt26VXPnztXs2bP1xhtvtHtudXW1Zs+erS9/+cv68MMPw1gOegj2U9hFe9vobxftbaO/XbSH\n",
       "i1AG2pycnNjHmZmZ7Z6blZWlhoYGNTc366233tKJEyfCWBIAAAAAoIcJ5SXHQRDEPs7IyGj33Btu\n",
       "uEEVFRU6ceKERowYoU8//TTuEAyb2E9hF+1to79dtLeN/nbRHi5CGWibm5tjH6ekpLS/gPR0TZ8+\n",
       "XZK0bt069erVK4wlAQAAAAB6mFBectzQ0CDp1DO1LR9L0q5du1RTU3POa44cOaJjx47FfXb29NfU\n",
       "RyIRjuMcn647rOd8jp966qlutZ5EH7fc1l3Wk8jjlo+7y3o47v79W24L63yOE3N85t+BZK+H48Qe\n",
       "09/u8VNPPdWt1sNxYo9dpQSnvz64i3z44YfauHGjgiDQtGnTNGjQIEnSihUrlJKSovnz58fOfeed\n",
       "d7Rnzx4FQaAZM2a0O9BWVVVpwoQJXb3cHq2wrFqV88c7XTP7sYla9fD2kFbUeZFIxPRLUA7Muk+X\n",
       "PvNU/BN7IOvtretM/1HLn1bN/feGdj4Sg5992+hvF+1t27Fjh6ZOndrh89PDWER+fr5uv/32s26/\n",
       "++67z7pt7NixGjt2bBjLgKQ+WWkqLKt2umZASGs5X/yDzS7a20Z/u2hvG/3toj1chDLQovtYXTrO\n",
       "+ZrZj4WwEAAAAADoYqHsoQXC0JnX1KNnoL1t9LeL9rbR3y7awwUDLQAAAADASwy08Ab7KeyivW30\n",
       "t4v2ttHfLtrDBQMtAAAAAMBLDLTwBvsp7KK9bfS3i/a20d8u2sMFAy0AAAAAwEsMtPAG+ynsor1t\n",
       "9LeL9rbR3y7awwUDLQAAAADASwy08Ab7KeyivW30t4v2ttHfLtrDBQMtAAAAAMBLDLTwBvsp7KK9\n",
       "bfS3i/a20d8u2sMFAy0AAAAAwEvpyV4Aup/MxhTNfmxispeBM/ybJiV7CUkTiUR4tNYw+ttFe9vo\n",
       "bxft4YKBFmf5f99+0+n8wrJqVc4f73TN0sUV+sZ3i5yu6cw/3CoGX6+i2s1O13RXB2bdl+wlAAAA\n",
       "AN0KLzmGN3ikzi7a20Z/u2hvG/3toj1cMNACAAAAALzEQAtv8J5kdtHeNvrbRXvb6G8X7eGCgRYA\n",
       "AAAA4CUGWniD/RR20d42+ttFe9vobxft4YKBFgAAAADgJQZaeIP9FHbR3jb620V72+hvF+3hgoEW\n",
       "AAAAAOAlBlp4g/0UdtHeNvrbRXvb6G8X7eGCgRYAAAAA4CUGWniD/RR20d42+ttFe9vobxft4YKB\n",
       "FgAAAADgpfRkLwD+65OVpsKyaqdrCjtxP+ynsIv2ttHfLtrbRn+7aA8XDLQ4b6tLxzlfs3RxRQgr\n",
       "AQAAAGAJLzmGN9hPYRftbaO/XbS3jf520R4uGGgBAAAAAF5ioIU32E9hF+1to79dtLeN/nbRHi4Y\n",
       "aAEAAAAAXmKghTfYT2EX7W2jv120t43+dtEeLhhoAQAAAABeYqCFN9hPYRftbaO/XbS3jf520R4u\n",
       "GGgBAAAAAF5ioIU32E9hF+1to79dtLeN/nbRHi4YaAEAAAAAXmKghTfYT2EX7W2jv120t43+dtEe\n",
       "LhhoAQAAAABeSk/2AmBTU2qKli6uCP1+xoR+D0iESCTCo7WG0d8u2ttGf7toDxcMtEiKb37nZudr\n",
       "CsuqVTl/vNM1FT9e4nw/AAAAAPzAS44BdHs8Smsb/e2ivW30t4v2cMFACwAAAADwEgMtgG6P96Oz\n",
       "jf520d42+ttFe7hgoAUAAAAAeImBFkC3x14a2+hvF+1to79dtIcLBloAAAAAgJcYaAF0e+ylsY3+\n",
       "dtHeNvrbRXu4YKAFAAAAAHiJgRZAt8deGtvobxftbaO/XbSHCwZaAAAAAICXGGgBdHvspbGN/nbR\n",
       "3jb620V7uGCgBQAAAAB4KT3ZCwA6qk9WmgrLqp2ueSiktSCx2EtjG/3tor1t9LeL9nDBQAtvrC4d\n",
       "53xNxbdCWAgAAACAboGXHMMb7Kewi/a20d8u2ttGf7toDxcMtAAAAAAALzHQwhvsp7CL9rbR3y7a\n",
       "20Z/u2gPFwy0AAAAAAAvMdDCG+ynsIv2ttHfLtrbRn+7aA8XDLQAAAAAAC8x0MIb7Kewi/a20d8u\n",
       "2ttGf7toDxcMtAAAAAAALzHQwhvsp7CL9rbR3y7a20Z/u2gPFwy0AAAAAAAvMdDCG+ynsIv2ttHf\n",
       "LtrbRn+7aA8XDLQAAAAAAC+lJ3sBQEdFIhHnR+yasrJVMfj6kFaUWP/nxquSvYSk6Ux79Bz0t4v2\n",
       "ttHfLtrDBQMterTpB151Or+wrFqV88c7XbN0cYW+8d0ip2s648Cs+0K/DwAAAMAnvOQY3uCROrto\n",
       "bxv97aK9bfS3i/ZwwUALAAAAAPASAy28wXuS2UV72+hvF+1to79dtIcLBloAAAAAgJcYaOEN9lPY\n",
       "RXvb6G8X7W2jv120hwsGWgAAAACAlxho4Q32U9hFe9vobxftbaO/XbSHCwZaAAAAAICXGGjhDfZT\n",
       "2EV72+hvF+1to79dtIcLBloAAAAAgJcYaOEN9lPYRXvb6G8X7W2jv120h4v0ML5obW2tqqqqlJaW\n",
       "psmTJysvL6/Nc3//+99r+/btikaj+uxnP6vPfOYzYSwJAAAAANDDhDLQbt26VXPnzpUkrVu3TjNm\n",
       "zGjz3D179uirX/2qJGn9+vUMtGhTIvZT9MlKU2FZtdM1hSGtBX/FXhrb6G8X7W2jv120h4tQBtqc\n",
       "nJzYx5mZme2e29zcrGg0qiAIFARBGMsBOmx16Tjna5YurghhJQAAAADiCWUP7emDaUZGRrvnjhkz\n",
       "Ro8//riWLl2q8ePHh7Ec9BDsp7CL9rbR3y7a20Z/u2gPF6EMtM3NzbGPU1JS2j337bff1j/90z/p\n",
       "H//xH/Xmm2/G/dqn/wWPRCIcGzp+5513utV6En3cclt3WQ/HHHfn45bbwjqfY4455pjj8I7feeed\n",
       "brUejhN77ColCOF1vmvXrtVXvvIVBUGgl156SbfccoskadeuXUpNTdWoUaNi527YsEFf/OIXz/r4\n",
       "XKqqqjRhwoSuXi5wXpYurtA3vlsU+v0cmHWfLn3mqdDvB+gJRi1/WjX33xva+QAAIBw7duzQ1KlT\n",
       "O3x+ehiLuPbaa7Vy5UoFQaBp06bFbt+yZYtSUlJaDbSXXXaZ1qxZI0kaPXp0GMsBAAAAAPRAoQy0\n",
       "+fn5uv3228+6/e677z7rtiuvvFJXXnllGMtADxOJRPitd0bR3jb620V72+hvF+3hIpQ9tAAAAAAA\n",
       "hI2BFt7gkTq7aG8b/e2ivW30t4v2cMFACwAAAADwEgMtvNGZX+ONnoH2ttHfLtrbRn+7aA8XDLQA\n",
       "AAAAAC8x0MIb7Kewi/a20d8u2ttGf7toDxdxB9oTJ04kYh0AAAAAADiJ+z60S5cu1d///d8rNzc3\n",
       "EesB2tRd35OsKTVFSxdXhH4/xaHfQ/fVXdsjMehvF+1to79dtIeLuAPtddddp927d2vTpk36/Oc/\n",
       "r4EDByZiXYA3vvmdm52vKSyrVuX88U7XHJj1vPP9AAAAAD1Z3IF2ypQpkqSTJ0/qtdde08cff6yi\n",
       "oiJ99NFHGj16dOgLBFrwSJ1dtLeN/nbR3jb620V7uIi7h7apqUmS9Mc//lH19fUaOXKktm7dquee\n",
       "ey70xQEAAAAA0Ja4A+2PfvQjrVy5UrW1tZo9e7YmTpyooqIiXXXVVYlYHxDDe5LZRXvb6G8X7W2j\n",
       "v120h4u4Lznu16+fZs2apdTU1rPvgAEDQlsUAAAAAADxxB1oZ8+efc7bb7zxxi5fDNAe9lPYRXvb\n",
       "6G8X7W2jv120h4u4Lzk+U21tbRjrAAAAAADASdyBdvfu3a2ON2/eHNpigPawn8Iu2ttGf7tobxv9\n",
       "7aI9XMQdaN97771Wx+npcV+lDAAAAABA6JxfchyNRsNYBxAX+ynsor1t9LeL9rbR3y7aw0WbT7e+\n",
       "9NJLamho0J49e3Ty5MnY7bm5uQlZGAAAAAAA7WnzGdrp06eruLhYV199tYqLi2P/47cbI1nYT2EX\n",
       "7W2jv120t43+dtEeLuK+5PiLX/xiItYBAAAAAICTuL/hiV8Che6iJ+2n6JOVpsKyaqdrVoS0Fh/0\n",
       "pPZwR3+7aG8b/e2iPVw4T6uvv/66brrpphCWAtixunSc8zUHKkNYCAAAAOAx599yfOTIkTDWAcTF\n",
       "fgq7aG8b/e2ivW30t4v2cNHmM7TLly9XcXGx1q9fr5ycnNjte/bs0YwZMxKyOAAAAAAA2tLmQFtc\n",
       "XKwLL7xQ/fr1azXArlu3LiELA87Efgq7aG8b/e2ivW30t4v2cNHmQHvxxRdLkoYNG9bq9tRU51cp\n",
       "AwAAAADQ5eJOp2PGjGl1XFRUFNpigPawn8Iu2ttGf7tobxv97aI9XDg/3ZqZmRnGOgAAAAAAcBJ3\n",
       "oF27dm0i1gHExX4Ku2hvG/3tor1t9LeL9nARd6CNRqOtjjds2BDaYgAAAAAA6Ki4A21mZqbq6upi\n",
       "x8ePHw91QUBb2E9hF+1to79dtLeN/nbRHi7a/C3HLT799FP94Ac/0IQJEyTxPrQAAAAAgO4h7kB7\n",
       "wQUX6Hvf+17smPehRbKwn8Iu2ttGf7tobxv97aI9XMR9yfHUqVNbHY8bNy60xQAAAAAA0FFxn6Ht\n",
       "3bt3q+PLL788tMUA7YlEIqYfsftLWpMOzLov2csA/HDT1cleAbqA9X/uW0d/u2gPF3EH2jNt375d\n",
       "EydODGMtANrxf1aucDq/sKxalfPHO12zdHGFvvHdIqdrOqNi8PUqqt3c4fO787/YZj82Uase3p7s\n",
       "ZfRoneq//OlwFgMAALqVuAPtzp07tWfPHh05ckR9+/bV/v37GWiRFN11oEH4aG8b/e2ivW30t4v2\n",
       "cBF3D+2ePXs0a9Ys5eXlafbs2briiisSsS4AAAAAANrVofehlaTm5mZJUkZGRrgrAtrAe5LZRXvb\n",
       "6G8X7W2jv120h4u4A+2JEyckSdFoVM3NzQqCIPRFAQAAAAAQT9yB9qabbpJ06rXsK1euVN++fcNe\n",
       "E3BO7Kewi/a20d8u2ttGf7toDxdxfynUoEGDYv8/b9680BcEAAAAAEBHxH2G9kwtL0EGEo39FHbR\n",
       "3jb620V72+hvF+3hwnmgraioCGMdAAAAAAA4cR5oo9FoGOsA4mI/hV20t43+dtHeNvrbRXu4aHMP\n",
       "7RNPPKGhQ4eedfuePXs0Y8aMUBcFAAAAAEA8bT5De8UVV6i4uPis/40dOzaR6wNi2E9hF+1to79d\n",
       "tLeN/nbRHi7aHGg/+9nPnvP2/v37h7YYAAAAAAA6qs2XHOfm5p7z9pb3pQUSjf0UbvpkpamwrNrp\n",
       "msKQ1nK+aG8b/e2ivW30t4v2cBH3fWgB+Gl16Tjna5Yu5reYAwAAwB/Ov+X49ddfD2EZQHzsp7CL\n",
       "9rbR3y7a20Z/u2gPF84D7ZEjR8JYBwAAAAAATtp8yfHy5ctVXFys9evXKycnJ3Y7b9uDZGE/hV20\n",
       "t43+dtHeNvrbRXu4aHOgLS4u1oUXXqh+/fq1GmDXrVuXkIUBAAAAANCeNl9yfPHFFys9PV3Dhg1r\n",
       "fUGq86uUgS7Bfgq7aG8b/e2ivW30t4v2cBF3Oh0zZkyr46KiotAWAwAAAABARzk/3free++FsQ4g\n",
       "LvZT2EV72+hvF+1to79dtIeLuO9D+8ILL6ixsVEpKSmSpIaGBo0ePTr0hQEAAAAA0J64z9A2NjZq\n",
       "1qxZKi4uVnFxsebMmZOIdQFnYT+FXbS3jf520d42+ttFe7iI+wztiRMnVFlZqczMTEnS22+/ra9/\n",
       "/euhLwwAAAAAgPZ0aKC9+uqrlZ5+6tRx48aFvijgXNhPYRftbaO/XbS3jf520R4u4r7kODU1VYMG\n",
       "DdKAAQM0YMAAHTx4MBHrAgAAAACgXXGfoT1w4IBWrlwZe4Z2z549+ud//ufQFwacKRKJ8IhdyJpS\n",
       "U7R0cUXo9zMm/imt0N42+ttFe9vobxft4SLuQHvvvfdq8ODBsWOeoQV6rm9+52bnawrLqlU5f7zT\n",
       "NRU/XuJ8PwAAAMCZ4r7k+PRhVpKCIAhtMUB7eKTOLtrbRn+7aG8b/e2iPVzEHWjP9Otf/zqMdQAA\n",
       "AAAA4KTNgfbQoUNqamrSoUOHWv3v008/TeT6gBjek8wu2ttGf7tobxv97aI9XLS5h/bZZ59VcXGx\n",
       "/vd//1cTJkyI3c4eWgAAAABAd9DmQHv//fdLkoYNG6abbropdvuRI0dCXxRwLuynsIv2ttHfLtrb\n",
       "Rn+7aA8XcffQFhUVtToeNmxYaIsBAAAAAKCj4g60mZmZrY7HjHF9B0mga7Cfwi7a20Z/u2hvG/3t\n",
       "oj1cxH0f2v/5n//RlClTdPDgQe3du1dDhw7lZQAAAAAAgKSL+wztwIEDdemll6qurk5z5sxRXV1d\n",
       "ItYFnIUHUuyivW30t4v2ttHfLtrDRdyBNhqNSpLS0089mZua6vzWtQAAAAAAdLm40+mxY8f0/vvv\n",
       "66KLLpIkpaSkhL4o4FzYT2EX7W2jv120t43+dtEeLuIOtJ/73Oe0a9cu/c3f/I2qq6v10UcfJWJd\n",
       "AAAAAAC0K+4vhSooKFBBQYEkafz48Ro/fnzYawLOif0UdtHeNvrbRXvb6G8X7eEi7kALAO3pk5Wm\n",
       "wrJqp2seCmktAAAAsIWBFt6IRCI8YtcNrS4d53xNxbfczqe9bfS3i/a20d8u2sMFv7IYAAAAAOCl\n",
       "0J6hra2tVVVVldLS0jR58mTl5eW1ee7jjz+u4cOHS5I+/vhjzZ8/P6xlwWM8UmcX7W2jv120t43+\n",
       "dtEeLkIbaLdu3aq5c+dKktatW6cZM2a0ee4DDzyg7OxsSVJFRUVYSwIAAAAA9CChveQ4Jycn9nFm\n",
       "Zma757YMs3V1dRo0aFBYS4LneE8yu2hvG/3tor1t9LeL9nAR2kAbBEHs44yMjA5dU1NTo1GjRoW1\n",
       "JAAAAABADxLaQNvc3Bz7OCUlpUPXNDY2xp6tbcvpj9hEIhGODR233NZd1sNx4o5vuOGGbrUejrt/\n",
       "/5bbwjqf48Qct+yj6y7r4Tixx/S3e3y67rAejpPXvyNSgtOfSu1Ca9eu1Ve+8hUFQaCXXnpJt9xy\n",
       "iyRp165dSk1NPeuZ2Gg0qldeeUWFhYVtfs2qqipNmDAhjOUCSKCKwderqHZzspfRJWY/NlGrHt6e\n",
       "7GXgDKOWP62a++8N7XwAABCOHTt2aOrUqR0+P7RnaK+99lqtXLlSK1eu1LXXXhu7fcuWLdq8+ez/\n",
       "kH3//fc1bNiwsJaDHqAzj9igZ6C9bfS3i/a20d8u2sNFelhfOD8/X7fffvtZt999993nPL+goCCs\n",
       "pQAAAAAAeqDQnqEFuhrvSWYX7W2jv120t43+dtEeLhhoAQAAAABeYqCFN9hPYRftbaO/XbS3jf52\n",
       "0R4uQttDCwBtacrKVsXg652uqQhpLeftoWQvAAAAwC4GWniD/RQ9x/QDrzqdX1hWrcr5452uWbq4\n",
       "Qt/4bpHTNZ3xfx+bGPp9WMfPvl20t43+dtEeLnjJMQAAAADASwy08Ab7KQCb+Nm3i/a20d8u2sMF\n",
       "Ay0AAAAAwEsMtPAG+ykAm/jZt4v2ttHfLtrDBQMtAAAAAMBLDLTwBvspAJv42beL9rbR3y7awwUD\n",
       "LQAAAADASwy08Ab7KQCb+Nm3i/a20d8u2sMFAy0AAAAAwEsMtPAG+ykAm/jZt4v2ttHfLtrDBQMt\n",
       "AAAAAMBLDLTwBvspAJv42beL9rbR3y7aw0V6shcAAPH0yUpTYVm10zWFIa0FAAAA3QcDLbwRiUR4\n",
       "xM6oBy/7xLn90sUVIa0GicbPvl20t43+dtEeLnjJMQAAAADASwy08AaP1NlFe9vobxftbaO/XbSH\n",
       "CwZaAAAAAICXGGjhDd6TzC7a20Z/u2hvG/3toj1cMNACAAAAALzEQAtvsJ/CLtrbRn+7aG8b/e2i\n",
       "PVww0AIAAAAAvMRAC2+wn8Iu2ttGf7tobxv97aI9XDDQAgAAAAC8xEALb7Cfwi7a20Z/u2hvG/3t\n",
       "oj1cMNACAAAAALzEQAtvsJ/CLtrbRn+7aG8b/e2iPVykJ3sBABCGptQULV1cEf4d9Q//LgAAAHBu\n",
       "DLTwBvsp7OpM+29+52bnawrLqlU5f7zTNbMfe8T5fuCGn327aG8b/e2iPVzwkmMAAAAAgJcYaOEN\n",
       "9lPYRXvb6G8X7W2jv120hwsGWgAAAACAlxho4Q32U9hFe9vobxftbaO/XbSHCwZaAAAAAICXGGjh\n",
       "DfZT2EV72+hvF+1to79dtIcLBloAAAAAgJcYaOEN9lPYRXvb6G8X7W2jv120hwsGWgAAAACAlxho\n",
       "4Q32U9hUrSaqAAAgAElEQVRFe9vobxftbaO/XbSHCwZaAAAAAICXGGjhDfZT2EV72+hvF+1to79d\n",
       "tIeL9GQvAAC6iz5ZaSosq3a6ZkBIawEAAEB8DLTwRiQS4RE7oxLVfnXpOOdrZj8WwkLQCj/7dtHe\n",
       "NvrbRXu44CXHAAAAAAAvMdDCGzxSZxftbaO/XbS3jf520R4uGGgBAAAAAF5ioIU3eE8yu2hvG/3t\n",
       "or1t9LeL9nDBQAsAAAAA8BIDLbzBfgq7aG8b/e2ivW30t4v2cMFACwAAAADwEgMtvMF+Crtobxv9\n",
       "7aK9bfS3i/ZwwUALAAAAAPASAy28wX4Ku2hvG/3tor1t9LeL9nDBQAsAAAAA8BIDLbzBfgq7aG8b\n",
       "/e2ivW30t4v2cJGe7AUAgM8yG1M0+7GJyV5Gj/efmx0v6H1PKOsAAADdCwMtvMF+Cru6c/v/9+03\n",
       "nc4vLKtW5fzxTtcsXVyhb3y3yOmazqgYfL2Kal0nx+5p1PKnk70EdIHu/LOP8NHfLtrDBS85BgAA\n",
       "AAB4iYEW3mA/hV20t43+dtHeNvrbRXu4YKAFAAAAAHiJgRbeYD+FXbS3jf520d42+ttFe7hgoAUA\n",
       "AAAAeImBFt5gP4VdtLeN/nbR3jb620V7uOBtewAAAAAgJEEQqK6uTs3NzcleSreRlpamQYMGKSUl\n",
       "5by/FgMtvMF+Crtobxv97aK9bfS3q6e1r6urU58+fZSTk5PspXQbf/nLX1RXV6fc3Nzz/lq85BgA\n",
       "AAAAQtLc3Mwwe4acnJwue8aagRbeYD+FXbS3jf520d42+ttFe7hgoAUAAAAAeImBFt7oafsp0HG0\n",
       "t43+dtHeNvrbRXs/NDY2JnsJkvilUACQUH2y0lRYVu10TWFIawEAAHaVl5dr586devTRRzt8TWNj\n",
       "o374wx/q8OHDGj16tG6//fYQV9gxDLTwRiQS4RE7o3pS+9Wl45yvWbq4IoSV+KMn9Ycb2ttGf7to\n",
       "nxglJSXav3+/0zXZ2dlatGiR/vCHP3Sbvc4MtAAAAABgWGlpqYYOHao77rhDlZWVikajrT6fn5+v\n",
       "4uLiJK2ufQy08AaP1NlFe9vobxftbaO/Xdbau25Fakvl/PHO1wRBoGXLlumuu+7SlClTJEkjR47s\n",
       "kvUkCgMtAAAAACRJZwbRrrJt2zYNHz5cM2fOlCQ1NDRoxYoVCoKg1Xl5eXmaNWtWMpYYFwMtvMF+\n",
       "Crtobxv97aK9bfS3i/aJM2nSJC1atEhLlizRggULlJubq4ULF8a97syBN5kYaAEAAADAmPLych09\n",
       "elTp6emaN2+e5syZo3vuuUclJSVtXtPY2KgVK1aovr5e+/fvV11dnW699VZddtllCVx5awy08AaP\n",
       "1NlFe9vobxftbaO/XbRPjJKSktjwOmLECFVVVcW9Jjs7Ww888EDYS3MSykBbW1urqqoqpaWlafLk\n",
       "ycrLy2v3/H379mn79u3KyspSUVGRMjMzw1gWAAAAAKAHSQ3ji27dulVz587V7Nmz9cYbb7R77pEj\n",
       "R/TRRx+puLhYt956K8Ms2tRd3usKiUd72+hvF+1to79dtIeLUAbanJyc2MfxBtS33npLvXr10po1\n",
       "a/Tuu++GsRwAAAAAQA8UykB7+m+9ysjIaPfcuro6HTlyRLfddpvee++9s97EF2jBfgq7aG8b/e2i\n",
       "vW30t4v2cBHKQNvc3Bz7OCUlJe75N954oyRpyJAhqq+vD2NJAAAAAIAeJpSBtqGhQdKpZ2pbPpak\n",
       "Xbt2qaamptW5I0aM0L59+yRJhw8fVr9+/dr92qe/pj4SiXBs6Pipp57qVuvhOHHHLR93l/X01OPT\n",
       "dYf1nE//M/9MXX0+x4k5PvPvQLLXw3Fij+lv9/ipp57qVus53+M///nPwrmd6/vlKiUI4V1xP/zw\n",
       "Q23cuFFBEGjatGkaNGiQJGnFihVKSUnR/PnzW53/3HPPKS0tTRdffHG7LzGoqqrShAkTunq58EQk\n",
       "wptsW2W9/b9+62WlR8N/A/MxP16iotrNod+Pq870H7X8adXcf29o5yMxrP/sW0d/u3pa+w8//FD5\n",
       "+fnJXka309b3ZceOHZo6dWqHv04oA21YGGgBoGMKy6pVOX+80zUVg6/vlgNtZzDQAgC6Cwbac+uq\n",
       "gTaUlxwDAAAAABA2Blp4ozOvqUfPQHvb6G8X7W2jv120T4zy8nI98sgjztc9++yzeuKJJ/T9739f\n",
       "zzzzTAgrc8NACwAAAADGlJSUqG/fvk7X7N+/X/369dOiRYv00EMPqbGxUfv37w9ngR2UntR7Bxz0\n",
       "pF8OADe0t43+dtHeNvrbZa390sUVXfJ1vvHdok5fW1paqqFDh+qOO+5QZWWlotFoq8/n5+eruLhY\n",
       "BQUFKigoiN1+4sQJZWdnd/p+uwIDLQAAAAAkyfkMoucrCAItW7ZMd911l6ZMmSJJGjlyZIeuffnl\n",
       "lzVw4EANHjw4zCXGxUuO4Q32U9hFe9vobxftbaO/XbRPnG3btumDDz7QlVdeKUlqaGjQf/zHf+jJ\n",
       "J59s9b8z98r+9Kc/VWpqqmbMmJGMZbfCM7QAAAAAYNCkSZO0aNEiLVmyRAsWLFBubq4WLlzY5vnR\n",
       "aFRPPvmkPve5z2nSpEkJXGnbGGjhDWv7KfBXtLeN/nbR3jb620X7xCgvL9fRo0eVnp6uefPmac6c\n",
       "ObrnnntUUlLS5jVPP/20Dhw4oNTUVG3ZskUfffSRvvrVr+qaa65J4MpbY6AFAAAAAGNKSkpiw+uI\n",
       "ESNUVVUV95r77rsv7GU5Yw8tvMF+Crtobxv97aK9bfS3i/ZwwUALAAAAAPASAy28wX4Ku2hvG/3t\n",
       "or1t9LeL9nDBHloA6IH6ZKWpsKza6ZqHQloLAABAWBho4Y1IJMIjdkbR3t3q0nHO11R8K4SFdAH6\n",
       "20V72+hvF+3hgpccAwAAAAC8xEALb/BInV20t43+dtHeNvrbRXu4YKAFAAAAAHiJgRbe4D3J7KK9\n",
       "bfS3i/a20d8u2idGeXm5HnnkkU5de+LECT344IP6t3/7ty5elTsGWgAAAAAwpqSkRH379u3Utf/9\n",
       "3/+tRYsWdfGKOoffcgxvsJ/CLtrbRn+7aG8b/e2ifeKVlpZq6NChuuOOO1RZWaloNNrq8/n5+Sou\n",
       "LpYk1dTUqF+/frrkkkuSsdSzMNACAAAAQJJUDL6+S75OUe1m52uCINCyZct01113acqUKZKkkSNH\n",
       "tnl+NBpVeXm5/uVf/qXT6+xqDLTwBu9JZhftbaO/XbS3jf52WWvfmUG0q2zbtk3Dhw/XzJkzJUkN\n",
       "DQ1asWKFgiBodV5eXp5mzZqld999V01NTXryySclSW+88YaOHDmi/v37J3ztLRhoAQAAAMCgSZMm\n",
       "adGiRVqyZIkWLFig3NxcLVy4sM3zr7zySj366KOx48bGxqQOsxK/FAoesfRIHVqjvW30t4v2ttHf\n",
       "LtonRnl5uY4ePar09HTNmzdPc+bMUXl5eYeura+v15NPPqmtW7fqyJEjIa+0fTxDCwAAAADGlJSU\n",
       "qKSkRJI0YsQIVVVVdfjaAQMG6Otf/7q+/vWvh7W8DuMZWniD9ySzi/a20d8u2ttGf7toDxc8QwsA\n",
       "kCQ1ZWV32W9a7GoVrhd8+84wlgEAALoZBlp4g/0UdtE+MaYfeNXp/MKyalXOH+90zdLFFfrGd4uc\n",
       "rumMh5Y/Hfp9IHz87NtGf7toDxe85BgAAAAA4CUGWniD/RR20d42+ttFe9vobxft4YKBFgAAAADg\n",
       "JQZaeIP9FHbR3jb620V72+hvF+3hgoEWAAAAAOAlBlp4g/0UdtHeNvrbRXvb6G8X7ROjvLxcjzzy\n",
       "iPN1Gzdu1GOPPaYf/OAH+slPfhLCytww0AIAAACAMSUlJerbt6/zdZs2bdLDDz+sBx98UBdccIF+\n",
       "97vfhbC6juN9aOEN9lPYRXvb6G8X7W2jv120T7zS0lINHTpUd9xxhyorKxWNRlt9Pj8/X8XFxZKk\n",
       "EydOKAgCpaSk6OOPP9YFF1yQjCXHMNACAAAAQJLMfmxil3ydVQ9vd74mCAItW7ZMd911l6ZMmSJJ\n",
       "GjlyZLvXfP7zn9esWbM0ZMgQDRw4UPn5+Z1ab1dhoIU3IpEIj9gZRXvb6G8X7W2jv13W2ndmEO0q\n",
       "27Zt0/DhwzVz5kxJUkNDg1asWKEgCFqdl5eXp1mzZun48ePauHGjnn32WUnSypUrtXPnTo0bNy7h\n",
       "a2/BQAsAAAAABk2aNEmLFi3SkiVLtGDBAuXm5mrhwoVtnt/U1KR+/frFjgsKCvSnP/0pEUttEwMt\n",
       "vGHpkTq0Rnvb6G8X7W2jv120T4zy8nIdPXpU6enpmjdvnubMmaN77rlHJSUlbV7Tq1cvjRgxQk88\n",
       "8YTS09OVlpamr33tawlc9dkYaAEAndInK02FZdVO1xSGtBYAAOCmpKQkNryOGDFCVVVVHbpu+vTp\n",
       "mj59ephLc8JAC29Y20+Bv6J997S61H2/zNLFFc7X0N8u2ttGf7toDxe8Dy0AAAAAwEsMtPAGj9TZ\n",
       "RXvb6G8X7W2jv120hwsGWgAAAACAlxho4Y1IJJLsJSBJaG8b/e2ivW30t4v2cMFACwAAAADwEgMt\n",
       "vMF+Crtobxv97aK9bfS3i/ZwwUALAAAAAPASAy28wX4Ku2hvG/3tor1t9LeL9n5obGxM9hIkSenJ\n",
       "XgAAAAAAILHKy8u1c+dOPfroox2+prGxUT/84Q91+PBhjR49WrfffvtZ5xw8eFA/+9nP1NzcrCFD\n",
       "hpzznK7EQAtvsJ/CLtrbRn+7aG8b/e2ifWKUlJRo//79TtdkZ2dr0aJF+sMf/nDOZ9I/+eQTrVy5\n",
       "UgsXLlRaWloXrbR9DLQAAAAAkCQHZt3XJV/n0mee6vS1paWlGjp0qO644w5VVlYqGo22+nx+fr6K\n",
       "i4vjfp3y8nLdeOONWrp0qS644ALNnz9fOTk5nV5XRzDQwhuRSIRH7IyivW30t4v2ttHfLmvtz2cQ\n",
       "PV9BEGjZsmW66667NGXKFEnSyJEjO/31PvjgA3300Uf69re/rT//+c/6r//6Lz300ENdtdxzYqAF\n",
       "ACRMU2qKli6ucL7u1+sdr7nE+S4AADBn27ZtGj58uGbOnClJamho0IoVKxQEQavz8vLyNGvWrLhf\n",
       "LzMzU3/3d38nSerXr1+Xr/dcGGjhDUuP1KE12vcc3/zOzc7XFJZVq3L+eKdrfrz8aef7QffDz75t\n",
       "9LeL9okzadIkLVq0SEuWLNGCBQuUm5urhQsXxr3uzIG3RWFhoV577TXNnTtXQRCoqampq5d8FgZa\n",
       "AAAAADCmvLxcR48eVXp6uubNm6c5c+bonnvuUUlJSZvXNDY2asWKFaqvr9f+/ftVV1enW2+9VZdd\n",
       "dpkk6ZprrtGbb76pxx9/XI2NjZo3b17ofw4GWnjD2n4K/BXtAZv42beN/nbRPjFKSkpiw+uIESNU\n",
       "VVUV95rs7Gw98MAD7Z7zD//wD12yvo5KTei9AQAAAADQRRho4Q0eqbOL9oBN/OzbRn+7aA8XDLQA\n",
       "AAAAAC8x0MIbkUgk2UtAktAesImffdvobxft4YKBFgAAAADgJQZaeIP9FHbRHrCJn33b6G8X7eGC\n",
       "gRYAAAAA4CUGWniD/RR20R6wiZ992+hvF+3hIj3ZCwAAAAAAJFZ5ebl27typRx991Om6//zP/9TJ\n",
       "kyeVmpqqEydO6MEHH1R6+qmxcuvWrXr99deVnZ2tkydP6sEHH1RqarjPoTLQwhvsp7CL9oBN/Ozb\n",
       "Rn+7aJ8YJSUl2r9/v/N1X/va12IfP/PMM9q7d6+uvPJKSVJ1dbUefvhhSdLevXu1atUqzZkzp0vW\n",
       "2xYGWgBAt9YnK02FZdXJXgYAAD1WaWmphg4dqjvuuEOVlZWKRqOtPp+fn6/i4uLYcU1NjcrKynTh\n",
       "hRdq1qxZsdvvvffe2MdHjx5Vnz59Ql87Ay28EYlEeMTOKNrb9uBlnzj3H7V8a0irQSLxs28b/e2y\n",
       "1n7U8qe75OvU3H9v/JPOEASBli1bprvuuktTpkyRJI0cOTLudaNGjdL3v/99LVu2TL/97W/Pumbv\n",
       "3r167bXX9NBDDzmvyRUDLQAAAAAkSWcG0a6ybds2DR8+XDNnzpQkNTQ0aMWKFQqCoNV5eXl5rZ6J\n",
       "bXH33XerrKys1UD761//Wjt27EjIMCsx0MIjlh6pQ2u0t43+dtHeNvrbRfvEmTRpkhYtWqQlS5Zo\n",
       "wYIFys3N1cKFC9s8/9ChQ7rgggvUu3dvSdLmzZs1fvz42Oeff/55ffrpp7r//vtDX3sLBloAAAAA\n",
       "MKa8vFxHjx5Venq65s2bpzlz5uiee+5RSUlJm9dkZGToySefVEZGhjIyMjRgwADdeeedkqS3335b\n",
       "P/nJTzR58mQ9+eSTkqTMzEzdd999of45GGjhDWv7KfBXtLeN/nbR3jb620X7xCgpKYkNryNGjFBV\n",
       "VVXca/r3769HHnnknJ+76qqrtGbNmi5dY0eE+6ZAAAAAAACEhIEW3uCROrtobxv97aK9bfS3i/Zw\n",
       "wUALAAAAAPASAy28EYlEkr0EJAntbaO/XbS3jf520R4uGGgBAAAAICRBEJz1vq7WdeX3hIEW3mA/\n",
       "hV20t43+dtHeNvrb1dPa9+vXT/X19cleRrdSX1+vfv36dcnX4m17AAAAACAkvXv31vHjx/Xhhx8m\n",
       "eyndRlZWlnr37t0lX4uBFt7gPcnsor1t9LeL9rbR366e2P6iiy5K9hJ6rFAG2traWlVVVSktLU2T\n",
       "J09WXl5em+e++OKLam5uliRdccUVGjt2bBhLAgAY0vtkk0Ytf9rpfAAA4J+UIIQdyi+88IJuvfVW\n",
       "SdK6des0Y8aMNs/9xS9+oS984Qsd+rpVVVWaMGFCl6wRAAAAANC97NixQ1OnTu3w+aE8Q5uTkxP7\n",
       "ODMzs91zm5ubtWbNGgVBoMsuu4yBFQAAAADQIaH8luPTn/TNyMho99yioiLddtttmjlzpg4ePBjG\n",
       "ctBD8J5kdtHeNvrbRXvb6G8X7eEilGdoW/bESlJKSkqHr4s3/Pbv3187duzo9Lrgt5ycHPobRXvb\n",
       "6G8X7W2jv120t61///5O54cy0DY0NEg69Uxty8eStGvXLqWmpmrUqFGx2w4cOKBLL71UktTY2Nju\n",
       "1504cWIIqwUAAAAA+CiUgfbaa6/VypUrFQSBpk2bFrt9y5YtSklJOWug3bp1qyTp6quvDmM5AAAA\n",
       "AIAeKJTfcgwAAAAAQNhC+aVQAAAAAACEjYEW3VY0Gm31C8YAAAAA4HSh7KHtarW1taqqqlJaWpom\n",
       "T56svLy8ZC8JIauoqNC+ffs0Y8YM5efnS+LvgSW7d+/Wb3/7W0WjUV133XW65JJL6G/I5s2bY2/j\n",
       "NnToUE2cOJH+RjQ0NOjf//3fdeedd/LPfmNefPHF2IPYV1xxhcaOHSuJ/pbs27dP27dvV1ZWloqK\n",
       "ilRfX097Ax5//HENHz5ckvTxxx9r/vz5khx/9gMPPP/887GP165dm8SVIJF2794dfPDBB7Fj/h7Y\n",
       "sXHjxtjHP//5z4MgoL9VL7/8chAE9Ldiw4YNwfbt2/lnv0GVlZXnvJ3+Nhw+fDiIRCKtbqO9DQ0N\n",
       "DbGPN2zYEPvYpb8XLznOycmJfZyZmZnElSCZ+Htgx4033njWbfS3Zf/+/XriiSc0bNgwSfS34PDh\n",
       "w8rJyVF2dnar22lvQ3Nzs9asWaPVq1e3ev9R+tvw1ltvqVevXlqzZo3effddSbS3ouWf+XV1dRo0\n",
       "aFDsdpf+Xgy0wWm/iDkjIyOJK0Ey8ffAnl/84heaNGmSJPpbU1BQoAULFmjbtm2S6G9BJBLRDTfc\n",
       "cNbttLehqKhIt912m2bOnBnbciDR34q6ujodOXJEt912m9577z1Fo1HaG1NTU9PqrV1d+nuxh/b0\n",
       "XwyUkpKSxJUgmfh7YMvGjRs1fPhwDRw4UBL9LcrOzlafPn0k0d+CgwcP6oUXXlBdXZ0KCgpie2hp\n",
       "b8/p//FKfztaXp01ZMgQ1dfX096YxsbGVq/QcenvxUDb0NAg6dSk3vIx7OHvgR2//OUvlZubq4KC\n",
       "gtht9Lejvr5eAwYMkPTXR2jp3/O1/CKQmpoa9e/fP3Y77W04cOCALr30Ukmn/sO2Bf1tGDFihPbt\n",
       "26dhw4bp8OHDGj16NO0NiUajSk1t/cJhl/4pwenP53ZTH374oTZu3KggCDRt2rRWr69Gz/TKK69o\n",
       "3759ys7OVkFBgW688Ub+HhhRV1enH//4x7ryyislSUePHlVpaSn9DXnxxRd1/PhxSdI111yjgoIC\n",
       "+htRX1+v5557TgUFBSosLJTEfwNYsWnTpthLja+++urYbz2lvx3PPfec0tLSdPHFF+uGG26gvSH7\n",
       "9+9XNBrV5ZdfHrvNpb8XAy0AAAAAAGfy4pdCAQAAAABwJgZaAAAAAICXGGgBAAAAAF5ioAUAAAAA\n",
       "eImBFgAAAADgJQZaAAAAAICXGGgBAKE5dOiQli9ffs7PvfTSS+1eu3z5ch06dCiMZXXK9u3b9dxz\n",
       "z+mll15SZWVlQu/75Zdf1urVq1vd1t739uTJk/rZz36mF154QT//+c914MCBVp8/3+/t9u3b9fTT\n",
       "T3f6+mT71a9+pcOHDyd7GQCALpCe7AUAAHquCy+8UMXFxef8XENDQ7vXFhcX68ILLwxjWZ2yb9++\n",
       "Nv8sYbv55pu1Zs2aVre197393e9+p7Fjx2rs2LHn/Pz5fm8nTpx41pDsk5MnT6qpqSnZywAAdAEG\n",
       "WgAw7M0339SmTZs0ePBg5eTk6OTJk+rfv7++8IUvSJIaGxv10ksvKSMjQ83NzerTp0/sc5K0du1a\n",
       "BUGgjIwMHTx4UDfddJOGDRsmSdq1a5f27t2rP//5z7rzzjtj1zQ1NWnDhg3as2eP1q1bJ0kaPny4\n",
       "Ro8eLUk6ceKEKioqtHfvXpWWluriiy9utebKykodO3ZMaWlpOnnypG655RZlZWXp97//vVatWqXP\n",
       "fOYz6t27t44fP64vfvGL6tu3b9zvQ3t/zpb1nL7ez372s8rNzW33a/785z/Xtm3bNHbsWB0+fFhZ\n",
       "WVk6fvy4vvzlL+viiy9u9z6bmpq0du1apaamKggC5eXltfrabX1vWz63efNmSacG2wsvvFCTJ0+O\n",
       "+71tamrSCy+8oNTUVKWkpCglJUXTp09XauqpF3O98sorqq+vV3p6utLS0hSNRuN+XyWpublZ69ev\n",
       "VxAEkqRPP/1UQ4cO1ec+9zlFo1GtXr1a6enpCoJAvXv3VmFhYezaiooK/f73v9f48eP1/vvvS5KK\n",
       "iorUt29f7dq1S7/5zW+UkZGhY8eOqaioSAMHDox7nzU1NdqxY4c++OAD9erVS6mpqfrSl76k9PRT\n",
       "/0m0adMm1dXVKTMzU42NjbH7k079vGzYsEGlpaXavHmzMjMzddVVV2n48OEd+l4AAEIQAABM+973\n",
       "vhccOnQodvzGG28Eu3fvDoIgCJ599tng2LFjsc+9++67wZYtW4IgCILm5ubgRz/6UXDy5MkgCILg\n",
       "T3/6U/DJJ5+c9fWfeeaZc95vW7e3eO2114K6urpWt/3qV78Kfvvb38aOjx49GqxevTp2XFZWFltP\n",
       "Q0ND8Pzzz7d7Hy3a+3N2dL1nqqurCyorK4MgCIKf/vSnsdteffXVuPf54osvntXk2WefPes+2lrT\n",
       "7t27Yw3P5Vzf2+effz6ora2NHR88eDB45ZVXYl/v9O/HoUOHgn/9139t8+ufbsOGDcGf/vSn2PHH\n",
       "H38c/OY3vznnueXl5Wfd9oMf/CDYuXNnu/dx4sSJYO3atR2+z9dee63V97fF7t27g1/+8petvu6Z\n",
       "3/dnnnkmqKioaHc9AIDE4RlaADBuyJAhsWe2JOnqq6/Wyy+/rFGjRikIAvXq1Sv2ueHDh+udd96R\n",
       "JKWmpuqWW27R66+/rqamJv3lL39p9exaGD744ANdf/31sePevXu3+nzfvn1jz7RlZ2d3+GWl7f05\n",
       "z0dGRkZsLZKUlpYWe9awvfs8duzYWU1anqEMS11dnbZs2XLO9b/33nu6+eabY7cPHDhQl1xySYe+\n",
       "7rFjxzRgwIDY8UUXXaSLLrpIknT8+HFVVlaqublZqamp+t3vfnfW9UOGDDnnS6f37NmjXbt2KSMj\n",
       "Q6mpqWpubu7QfbZo6XC6ffv2qbGxMfZMvHTq2d0znf69AAAkFwMtABj3wQcf6OOPP44NUG+99ZZG\n",
       "jhwp6dTQeuzYsdjg+O677yo/P1+S9Mc//lHZ2dmaNm2aJOnIkSPatGmTvvSlL4W21ksuuUTvvvuu\n",
       "RowYIenU4NIVzvXnPPNlvq7ONTDFu8+W722vXr1aNdmxY0fcr3fmfaekpDit9/LLL9eYMWM0aNCg\n",
       "2G0tDwgMHz5cb731lq677jpJp34h1R/+8IcOfd3s7GzV19fHBsxoNKp9+/Zp2LBhWr9+vaZOnRp7\n",
       "Se+5hsdzaWxs1Ntvv62SkhJJp15KffovGWvvPiUpPT291QDcYsyYMaqtrY39OU//HgAAuqeUwOXf\n",
       "kACAHmfVqlVKT0+PDUAXXXSRbrrpJkl/3Vuanp6uaDSqXr16xZ6d2rFjh2pqatS7d2+lpKTo008/\n",
       "1fTp09W3b9/YXs1oNKp33nlHY8eOVf/+/WNfVzq1V7G+vl6pqalqamrS9ddfr8GDB8f2h+7bt0+5\n",
       "ubnq1auXrrvuOg0ePFjSX/fQpqam6uTJk7r11luVlZWlXbt2ae3atZo5c6ZGjRqlN998U5WVlXrg\n",
       "gQfUp0+fdr8H7f05P/nkE7322mvauXOnxo4dq5SUFE2dOvWsZ4fPtH79eu3du1f333+/Vq1apQkT\n",
       "Jmjw4MH6yU9+ogceeEBNTU1t3mdTU5Oee+652LOPvXv31rZt2zR37lzl5eW1+73dunWr3nrrLUnS\n",
       "oEGDdMkll+iaa66RpA59bxsbGyWdevZ0yJAhsWfEf/GLX+jw4cPKzs5WY2Oj6urqdN1118W+dlua\n",
       "mpr0/PPPx/bdNjc362//9m81ePBg7d69WzU1NcrIyFBTU5Pee+89jR8/XkVFRef8vk+ZMiXWctWq\n",
       "VWNRCvkAAAC+SURBVMrOzlYQBAqCQL/5zW80d+5cFRQUtHufknT06FG9+OKLsYa9e/fWlClTJJ36\n",
       "e/3++++3etb3K1/5Sqzp9u3bY88YX3XVVbrsssva/fMDAMLFQAsAxj377LNJ++29AAAA54P3oQUA\n",
       "w958803t2bNHzz//vD755JNkLwcAAMAJz9ACAAAAALzEM7QAAAAAAC8x0AIAAAAAvMRACwAAAADw\n",
       "EgMtAAAAAMBLDLQAAAAAAC8x0AIAAAAAvPT/ActW+S28O4vzAAAAAElFTkSuQmCC\n"
      ],
      "text/plain": [
       "<matplotlib.figure.Figure at 0x103754410>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def test_rep(k=1, n=128):\n",
    "    s1 = string.letters[:k]*int(n/k*2)\n",
    "    s1 = s1[:n]\n",
    "    r = lambda x : ratio(x, s1)\n",
    "    \n",
    "    def modified(i):\n",
    "        \"\"\" return the string s1, where the i-th is replaced by -\"\"\"\n",
    "        return s1[:i-1]+u'-'+s1[i+1:]\n",
    "    \n",
    "    xx = range(1, n, step)\n",
    "    distance = map( r, [modified(i) for i in xx])\n",
    "    return xx,distance\n",
    "\n",
    "fig,ax = plt.subplots(1,1)\n",
    "fig.set_figwidth(16)\n",
    "fig.set_figheight(8)\n",
    "\n",
    "for k in [1,2,4,8,16,32]:\n",
    "    xx, distance = test_rep(k, n=64)\n",
    "    plt.step(xx, distance, where='post', label='k={k}'.format(k=k))\n",
    "    \n",
    "\n",
    "plt.ylabel('similarity')\n",
    "plt.xlabel('position of modified caracter')\n",
    "plt.legend(loc=4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(bottom of the graph is at 0.5, not 0.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Huummm... this definitively does not look at what I was expecting (mainly something constant), but looks more like a [Sierpinski triangle](http://en.wikipedia.org/wiki/Sierpinski_triangle) to me."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bottom line, even if difflib make some pretty looking diff, I cannot trust it for giving me proximity of two sequences."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Still Some good sides..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Anyway, I knew what [levenstein distance](http://en.wikipedia.org/wiki/Levenshtein_distance) was, but not really\n",
    "what the efficient algorithme where. I played around a little bit with them, and recoded them in pure python.\n",
    "I'll post the link soon, just time to clean things up im make them as pure python module. Below is how it looks like.\n",
    "\n",
    "Thing is, as far as I can tell, libdiff stays an order of magnitude faster in some cases, as well as computes the matches at the same time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def lcs_len3(Seq1 , Seq2):\n",
    "    \"\"\" Compute the LCS len 2 sequences\n",
    "    \n",
    "    Do not calculate the matrix and try to be as efficient as possible \n",
    "    in storing only the minimal ammount of elelment in memory, mainly the previous\n",
    "    matrix row + 1 element.\n",
    "    \"\"\"\n",
    "    LL1 = len(Seq1)+1\n",
    "    LL2 = len(Seq2)+1\n",
    "\n",
    "    ## we will do the big loop over the longest sequence (L1)\n",
    "    ## and store the previous row of the matrix (L2+1)\n",
    "    if LL2 > LL1 : \n",
    "        Seq2, Seq1 = Seq1, Seq2\n",
    "        LL2, LL1 = LL1, LL2\n",
    "\n",
    "    \n",
    "    previousrow = [0]*(LL2)\n",
    "    cindex = 0\n",
    "\n",
    "    for Seq1ii in Seq1:\n",
    "        for jj in range(1,LL2):\n",
    "            cindex = (cindex+1) % LL2\n",
    "\n",
    "            if Seq1ii == Seq2[jj-1]:\n",
    "                if jj == 1:\n",
    "                    previousrow[cindex] = 1\n",
    "                else :\n",
    "                    previousrow[cindex]+=1\n",
    "            if Seq1ii != Seq2[jj-1] :\n",
    "                up = previousrow[(cindex+1) % LL2]\n",
    "                \n",
    "                if jj != 1 :\n",
    "                    left = previousrow[(cindex-1) % LL2]\n",
    "                    if left > up :\n",
    "                        previousrow[cindex] = left\n",
    "                        continue    \n",
    "                previousrow[cindex] = up\n",
    "\n",
    "\n",
    "    return previousrow[cindex]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import difflib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "random x 4 8\n",
      "sorted \u221a 23 23\n",
      "random x 4 9\n",
      "sorted \u221a 26 26\n",
      "random x 6 10\n",
      "sorted \u221a 25 25\n",
      "random x 4 12\n",
      "sorted \u221a 27 27\n",
      "random x 5 7\n",
      "sorted \u221a 27 27\n",
      "random x 7 10\n",
      "sorted \u221a 30 30\n",
      "random x 6 13\n",
      "sorted \u221a 33 33\n",
      "random x 9 10\n",
      "sorted \u221a 25 25\n",
      "random x 2 7\n",
      "sorted \u221a 28 28\n",
      "random x 5 10\n",
      "sorted \u221a 27 27\n"
     ]
    }
   ],
   "source": [
    "def compare(s1,s2):\n",
    "    m0 = difflib.SequenceMatcher(None, s1, s2, autojunk=False).get_matching_blocks()\n",
    "    m1 = lcs_len3(s1,s2)\n",
    "    a,b = sum([x.size for x in m0]),m1\n",
    "    return a,b \n",
    "\n",
    "for k in range(10):\n",
    "    s1 = np.random.randint(0,250, 100)\n",
    "    s2 = np.random.randint(0,250, 100)\n",
    "    a,b = compare(s1,s2)\n",
    "    print 'random',u'\u221a' if a == b else 'x',a,b\n",
    "    a,b = compare(sorted(s1),sorted(s2))\n",
    "    print 'sorted',u'\u221a' if a == b else 'x',a,b\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Except on the sorted case, SequenceMatcher from stdlib give the wrong matches length almost all the time (sometime it is right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000 loops, best of 3: 402 \u00b5s per loop\n",
      "100 loops, best of 3: 9.38 ms per loop\n",
      "--------- sorted ----------\n",
      "1000 loops, best of 3: 734 \u00b5s per loop\n",
      "100 loops, best of 3: 9.33 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit difflib.SequenceMatcher(None, s1, s2, autojunk=False).get_matching_blocks()\n",
    "%timeit lcs_len3(s1,s2)\n",
    "print '--------- sorted ----------'\n",
    "s1.sort()\n",
    "s2.sort()\n",
    "%timeit difflib.SequenceMatcher(None, s1, s2, autojunk=False).get_matching_blocks()\n",
    "%timeit lcs_len3(s1,s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On both sorted and unsorted arrays, SequenceMatcher is way faster (10 to 20 times) than I am, but wrong."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 26 ms per loop\n",
      "10 loops, best of 3: 30.8 ms per loop\n"
     ]
    }
   ],
   "source": [
    "s1 = 'a'*251\n",
    "i = 124\n",
    "s2 = 'a'*(i)+'b'+'a'*(250-i)\n",
    "%timeit MySequenceMatcher(s1, s2).get_matching_blocks()        \n",
    "%timeit lcs_len3(s1,s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "126"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(x.size for x in MySequenceMatcher(s1, s2).get_matching_blocks())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But in the cases where `SequenceMatcher` is clearly wrong for the **optimal** sequence, we are around the same time to execute."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Not that I don't like current python libdiff, but I hope to be able to build a lower lever library (pure python of course) without any surprise behavior, on which maby one can rebuild the current libdiff and avoid to rely on [regular expression](http://hg.python.org/cpython/file/0872257752c2/Lib/difflib.py#l1371) to parse the output of another function. \n",
    "\n",
    "I'll be happy to get any tips to make it faster, of course it is not possible in all the cases but I'm sure we can figure it out."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "As usual comments, typo and PRs welcommed on the [repo that host thoses notebooks](https://github.com/Carreau/posts/issues). I should probably learn how to use [Pelican](http://docs.getpelican.com/en/3.2/) now that it [support notebooks](https://github.com/getpelican/pelican-plugins/pull/21).\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Edit**:  At the request of some person, I opened a place to **[comment on this post](https://github.com/Carreau/posts/issues/2)** until I turn it into a real blogpost."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "IPython (Python 3)",
   "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}