{ "cells": [ { "cell_type": "markdown", "id": "c4ea1623", "metadata": {}, "source": [ "# Decomposing the Capacitated p-Median Problem\n", "The capacitated p-median problem (CPMP) is a known and well-studied problem from the literature. Given\n", "$n \\in \\mathbb{N}$ locations, the task is to select $p \\in \\mathbb{N}$ *median* locations with $p \\leq n$ and to\n", "assign each location to exactly one median. For any two locations $i,j \\in [n]$, the distance between them is given\n", "by $d_{ij} \\in \\mathbb{R}$. The distance between the locations and their assigned medians is minimized. Every\n", "location $i \\in [n]$ has a *demand* $q_i \\in \\mathbb{R}$ and a maximum *capacity* $Q_i \\in \\mathbb{R}$. For every\n", "selected median, the sum of the demands of the locations assigned to it must not exceed its capacity.\n", "\n", "The CPMP can be formulated as a MIP. Here is a classical compact formulation of problem:\n", "\n", "$$\n", "\\begin{alignat*}{3}\n", "z^{\\star}_{IP}\\,\\,\\,=\\,\\,\\,\\min{} &\\sum_{i=1}^n \\sum_{j=1}^n d_{ij} x_{ij} \\hspace{-2em} &&&&\\\\\n", " \\text{s. t.} &\\sum_{j=1}^n x_{ij} &&= 1 \\quad &\\forall i &\\in [n]\\\\\n", " &\\sum_{i=1}^{n} q_i x_{ij} &&\\leq Q_j y_j \\quad &\\forall j &\\in [n] \\\\\n", " &\\sum_{j=1}^n y_j &&= p && \\\\\n", " &x_{ij} \\in \\{0,1\\}, y_j \\in \\{0,1\\} \\hspace{-6em} &&\\hspace{6em}\\quad& \\forall i,j &\\in [n].\n", "\\end{alignat*}\n", "$$\n", "\n", "There are different approaches to solve the CPMP. As it has a structure, we can try to solve using a\n", "Branch-Cut-and-Price approach. For that we want to use the `PyGCGOpt` interface to interact with GCG. We will consider three\n", "use-cases: (1) The Automatic Mode, (2) Exploring different Decompositions, and (3) Building a custom Decomposition.\n", "\n", "To follow along with this tutorial interactively, please download the Jupyter notebook from the [examples folder](https://github.com/scipopt/PyGCGOpt/tree/master/examples/cpmp)." ] }, { "cell_type": "markdown", "id": "c7bfbf84", "metadata": {}, "source": [ "## Reading in the Instance\n", "The `PyGCGOpt` interface offers two methods to specify a problem. The first is to load the model from a standardized file format (e.g., `.lp` or `.mps`) that is supported by `SCIP` using `Model.readProb()`. Optionally, one can also read in a decomposition from a `.dec` file in the same manner. In this example, we will use the second method: Modeling a problem directly in Python.\n", "\n", "Execute the following cell which includes a trivial test instance and function to load more instances from a custom `JSON` file format." ] }, { "cell_type": "code", "execution_count": 1, "id": "joint-colony", "metadata": {}, "outputs": [], "source": [ "import json\n", "\n", "def get_simple_instance():\n", " n = 5\n", " p = 2\n", " d = {0: {0: 0, 1: 25, 2: 46, 3: 43, 4: 30}, 1: {1: 0, 2: 22, 3: 20, 4: 22}, 2: {2: 0, 3: 22, 4: 40}, 3: {3: 0, 4: 22}, 4: {4: 0}}\n", " q = {0: 14, 1: 13, 2: 9, 3: 15, 4: 6}\n", " Q = {i: 33 for i in range(5)}\n", " return n, p, d, q, Q\n", "\n", "def read_instance_json(path):\n", " with open(path) as f:\n", " instance = json.load(f)\n", " d = {int(k): {int(kk): vv for kk, vv in v.items()} for k, v in instance[\"d\"].items()}\n", " q = {int(k): v for k, v in instance[\"q\"].items()}\n", " Q = {int(k): v for k, v in instance[\"Q\"].items()}\n", " return instance[\"n\"], instance[\"p\"], d, q, Q\n", "\n", "n_locations, n_clusters, distances, demands, capacities = read_instance_json(\"instances/p550-01.json\")" ] }, { "cell_type": "markdown", "id": "a2ffb130", "metadata": {}, "source": [ "## Setting up the Model\n", "Now, we want to build the model based on the above formulation. Please note that this part is *not* specific to GCG but is identical to how one would build the same model with `PySCIPOpt`. In technical terms, `Model` in `PyGCGOpt` is a subclass of `Model` in `PySCIPOpt` and, therefore, you can use all methods of `PySCIPOpt` `Model` to build your problem.\n", "\n", "In order to recreate the model multiple times during this example, we create a method that will return the model. The method also returns the different constraints added to the model grouped by type. This will be important later in use-case 3." ] }, { "cell_type": "code", "execution_count": 2, "id": "2ffa8aa2", "metadata": {}, "outputs": [], "source": [ "from pygcgopt import Model, quicksum\n", "\n", "def build_model(n_locations, n_clusters, distances, demands, capacities):\n", " m = Model()\n", "\n", " m.printVersion()\n", " m.redirectOutput()\n", "\n", " m.setMinimize()\n", "\n", " x = {}\n", " y = {}\n", "\n", " for j in range(n_locations):\n", " y[j] = m.addVar(f\"y_{j}\", vtype=\"B\")\n", " for i in range(n_locations):\n", " x[i, j] = m.addVar(f\"x_{i}_{j}\", vtype=\"B\", obj=distances[min(i,j)][max(i,j)])\n", "\n", " # Hold different constraint types\n", " conss_assignment = []\n", " conss_capacity = []\n", " cons_pmedian = None\n", "\n", " # Create the assignment constraints\n", " for i in range(n_locations):\n", " conss_assignment.append(\n", " m.addCons(quicksum(x[i, j] for j in range(n_locations)) == 1)\n", " )\n", "\n", " # Create the capacity constraints\n", " for j in range(n_locations):\n", " conss_capacity.append(\n", " m.addCons(quicksum(demands[i] * x[i, j] for i in range(n_locations)) <= capacities[j] * y[j])\n", " )\n", "\n", " # Create the p-median constraint\n", " cons_pmedian = m.addCons(quicksum(y[j] for j in range(n_locations)) == n_clusters)\n", "\n", " return m, conss_assignment, conss_capacity, cons_pmedian" ] }, { "cell_type": "markdown", "id": "1b1dd31f", "metadata": {}, "source": [ "## Use-Case 1: The Automatic Mode\n", "With the model built, we can now simply call the `optimize()` function and let GCG do its magic." ] }, { "cell_type": "code", "execution_count": 3, "id": "selected-ticket", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "GCG version 3.5.0 [GitHash: 202908425-dirty]\n", "Copyright (C) 2010-2021 Operations Research, RWTH Aachen University\n", " Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)\n", "\n", "SCIP version 8.0.0 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 6.0.0] [GitHash: 8441670cd5-dirty]\n", "Copyright (C) 2002-2021 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)\n", "presolving:\n", "(round 1, exhaustive) 0 del vars, 0 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 100 upgd conss, 0 impls, 50 clqs\n", " (0.0s) probing: 51/2550 (2.0%) - 0 fixings, 0 aggregations, 0 implications, 0 bound changes\n", " (0.0s) probing aborted: 50/50 successive totally useless probings\n", "presolving (2 rounds: 2 fast, 2 medium, 2 exhaustive):\n", " 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients\n", " 0 implications, 2550 cliques\n", "presolved problem has 2550 variables (2550 bin, 0 int, 0 impl, 0 cont) and 101 constraints\n", " 50 constraints of type \n", " 50 constraints of type \n", " 1 constraints of type \n", "transformed objective value is always integral (scale: 1)\n", "Presolving Time: 0.04\n", " Consclassifier \"nonzeros\" yields a classification with 2 different constraint classes \n", " Consclassifier \"constypes\" yields a classification with 3 different constraint classes \n", " Consclassifier \"constypes according to miplib\" yields a classification with 3 different constraint classes \n", " Conspartition \"constypes according to miplib\" is not considered since it offers the same structure as \"constypes\" conspartition\n", " Consclassifier \"gamsdomain\" yields a classification with 1 different constraint classes \n", " Consclassifier \"gamssymbols\" yields a classification with 1 different constraint classes \n", " Conspartition \"gamssymbols\" is not considered since it offers the same structure as \"gamsdomain\" conspartition\n", " Varclassifier \"gamsdomain\" yields a classification with 1 different variable classes \n", " Varclassifier \"gamssymbols\" yields a classification with 1 different variable classes \n", " Varpartition \"gamssymbols\" is not considered since it offers the same structure as \"gamsdomain\"\n", " Varclassifier \"vartypes\" yields a classification with 1 different variable classes\n", " Varpartition \"vartypes\" is not considered since it offers the same structure as \"gamsdomain\"\n", " Varclassifier \"varobjvals\" yields a classification with 116 different variable classes\n", " Varclassifier \"varobjvalsigns\" yields a classification with 2 different variable classes\n", " the current varclass distribution includes 116 classes but only 18 are allowed for GCGconshdlrDecompCalcCandidatesNBlocks()\n", " in dec_consclass: there are 3 different constraint classes \n", " the current constraint classifier \"nonzeros\" consists of 2 different classes \n", " the current constraint classifier \"constypes\" consists of 3 different classes \n", " the current constraint classifier \"gamsdomain\" consists of 1 different classes \n", " dec_consclass found 11 new partialdecs \n", "dec_densemasterconss found 1 new partialdec \n", "dec_neighborhoodmaster found 1 new partialdec \n", " the current varclass distribution includes POSTPROCESSING of decompositions. Added 0 new decomps. \n", "Found 11 finished decompositions.\n", "Measured running time per detector:\n", "Detector consclass worked on 7 finished decompositions and took a total time of 0.000\n", "Detector neighborhoodmaster worked on 1 finished decompositions and took a total time of 0.000\n", "Detector connectedbase worked on 10 finished decompositions and took a total time of 0.007\n", "Detector varclass worked on 2 finished decompositions and took a total time of 0.001\n", "Detection Time: 0.02\n", "\n", "A Dantzig-Wolfe reformulation is applied to solve the original problem.\n", "Chosen structure has 50 blocks and 51 linking constraints.\n", "This decomposition has a maxwhite score of 0.485149.\n", "Matrix has 50 blocks, using 50 pricing problems.\n", "\n", " time | 116 classes but only 9 are allowed for propagatePartialdec() of var class detector\n", "node | left |SLP iter|MLP iter|LP it/n| mem |mdpt |ovars|mvars|ocons|mcons|mcuts| dualbound | primalbound | deg | gap \n", "p 0.2s| 1 | 0 | 0 | 0 | - | 34M| 0 |2550 | 0 | 101 | 0 | 0 | 0.000000e+00 | 2.711000e+03 | -- | Inf \n", "p 0.2s| 1 | 0 | 0 | 0 | - | 33M| 0 |2550 | 0 | 101 | 0 | 0 | 0.000000e+00 | 1.785000e+03 | -- | Inf \n", "p 0.3s| 1 | 0 | 0 | 0 | - | 33M| 0 |2550 | 0 | 101 | 0 | 0 | 0.000000e+00 | 1.102000e+03 | -- | Inf \n", " 0.3s| 1 | 0 | 0 | 0 | - | 33M| 0 |2550 | 0 | 101 | 0 | 0 | 0.000000e+00 | 1.102000e+03 | -- | Inf \n", " \n", " 0.3s| \n", " 1 | 0 | 0 | 0 | - | 34M| 0 |2550 | 50 | 102 | 102 | 0 | 0.000000e+00 | 1.102000e+03 | 0.00%| Inf 0.3s\n", "| 1 | 0 | 0 | 0 | - | 34M| 0 |2550 | 150 | 102 | 102 | 0 | 0.000000e+00 | 1.102000e+03 | 0.00%| Inf \n", "Starting reduced cost pricing...\n", " 0.5s| 1 | 0 | 2081 | 2081 | - | 41M| 0 |2550 |1699 | 102 | 102 | 0 | 7.050000e+02 | 1.102000e+03 | 36.95%| 56.31%\n", "d 1.1s| 1 | 0 | 3055 | 3055 | - | 57M| 0 |2550 |1749 | 102 | 102 | 0 | 7.050000e+02 | 1.016000e+03 | 36.95%| 44.11%\n", "X 1.4s| 1 | 0 | 3055 | 3055 | - | 57M| 0 |2550 |1799 | 102 | 102 | 0 | 7.050000e+02 | 7.730000e+02 | 36.95%| 9.65%\n", "Y 1.5s| 1 | 0 | 3055 | 3055 | - | 57M| 0 |2550 |1849 | 102 | 102 | 0 | 7.050000e+02 | 7.580000e+02 | 36.95%| 7.52%\n", " 1.5s| 1 | 0 | 3055 | 3055 | - | 57M| 0 |2550 |1849 | 102 | 102 | 0 | 7.050000e+02 | 7.580000e+02 | 36.95%| 7.52%\n", " 1.6s| 1 | 0 | 3055 | 3055 | - | 57M| 0 |2550 |1849 | 102 | 102 | 0 | 7.050000e+02 | 7.580000e+02 | 36.95%| 7.52%\n", " 1.6s| 1 | 2 | 3055 | 3055 | - | 57M| 0 |2550 |1849 | 102 | 102 | 0 | 7.050000e+02 | 7.580000e+02 | 36.95%| 7.52%\n", "*r 1.6s| 2 | 1 | 3063 | 3063 | 316.0 | 58M| 1 |2550 |1849 | 102 | 102 | 0 | 7.050000e+02 | 7.140000e+02 | -- | 1.28%\n", "*r 2.3s| 16 | 5 | 6962 | 6962 | 281.0 | 61M| 5 |2550 |2305 | 102 | 102 | 0 | 7.102222e+02 | 7.130000e+02 | -- | 0.39%\n", "\n", "SCIP Status : problem is solved [optimal solution found]\n", "Solving Time (sec) : 2.62\n", "Solving Nodes : 21\n", "Primal Bound : +7.13000000000000e+02 (13 solutions)\n", "Dual Bound : +7.13000000000000e+02\n", "Gap : 0.00 %\n" ] } ], "source": [ "m, *conss = build_model(n_locations, n_clusters, distances, demands, capacities)\n", "m.optimize()" ] }, { "cell_type": "markdown", "id": "cee4b2a1", "metadata": {}, "source": [ "## Use-Case 2: Exploring different Decompositions\n", "Above, we have seen GCG in its fully automatic mode. If we want to dig deeper, we can inspect the different decompositions that GCG detects. For that, we recreate the model and manually execute `presolve()` and `detect()` for the model. At this stage it is possible to list and visualize the found decompositions." ] }, { "cell_type": "code", "execution_count": 4, "id": "satisfactory-convertible", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "GCG version 3.5.0 [GitHash: 202908425-dirty]\n", "Copyright (C) 2010-2021 Operations Research, RWTH Aachen University\n", " Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)\n", "\n", "SCIP version 8.0.0 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 6.0.0] [GitHash: 8441670cd5-dirty]\n", "Copyright (C) 2002-2021 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)\n", "presolving:\n", "(round 1, exhaustive) 0 del vars, 0 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 100 upgd conss, 0 impls, 50 clqs\n", " (0.0s) probing: 51/2550 (2.0%) - 0 fixings, 0 aggregations, 0 implications, 0 bound changes\n", " (0.0s) probing aborted: 50/50 successive totally useless probings\n", "presolving (2 rounds: 2 fast, 2 medium, 2 exhaustive):\n", " 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients\n", " 0 implications, 2550 cliques\n", "presolved problem has 2550 variables (2550 bin, 0 int, 0 impl, 0 cont) and 101 constraints\n", " 50 constraints of type \n", " 50 constraints of type \n", " 1 constraints of type \n", "transformed objective value is always integral (scale: 1)\n", "Presolving Time: 0.04\n", "starting detection\n", " Consclassifier \"nonzeros\" yields a classification with 2 different constraint classes \n", " Consclassifier \"constypes\" yields a classification with 3 different constraint classes \n", " Consclassifier \"constypes according to miplib\" yields a classification with 3 different constraint classes \n", " Conspartition \"constypes according to miplib\" is not considered since it offers the same structure as \"constypes\" conspartition\n", " Consclassifier \"gamsdomain\" yields a classification with 1 different constraint classes \n", " Consclassifier \"gamssymbols\" yields a classification with 1 different constraint classes \n", " Conspartition \"gamssymbols\" is not considered since it offers the same structure as \"gamsdomain\" conspartition\n", " Varclassifier \"gamsdomain\" yields a classification with 1 different variable classes \n", " Varclassifier \"gamssymbols\" yields a classification with 1 different variable classes \n", " Varpartition \"gamssymbols\" is not considered since it offers the same structure as \"gamsdomain\"\n", " Varclassifier \"vartypes\" yields a classification with 1 different variable classes\n", " Varpartition \"vartypes\" is not considered since it offers the same structure as \"gamsdomain\"\n", " Varclassifier \"varobjvals\" yields a classification with 116 different variable classes\n", " Varclassifier \"varobjvalsigns\" yields a classification with 2 different variable classes\n", " the current varclass distribution includes 116 classes but only 18 are allowed for GCGconshdlrDecompCalcCandidatesNBlocks()\n", " in dec_consclass: there are 3 different constraint classes \n", " the current constraint classifier \"nonzeros\" consists of 2 different classes \n", " the current constraint classifier \"constypes\" consists of 3 different classes \n", " the current constraint classifier \"gamsdomain\" consists of 1 different classes \n", " dec_consclass found 11 new partialdecs \n", "dec_densemasterconss found 1 new partialdec \n", "dec_neighborhoodmaster found 1 new partialdec \n", "POSTPROCESSING of decompositions. Added 0 new decomps. \n", "Found 11 finished decompositions.\n", "Measured running time per detector:\n", "Detector consclass worked on 7 finished decompositions and took a total time of 0.000\n", "Detector neighborhoodmaster worked on 1 finished decompositions and took a total time of 0.000\n", "Detector connectedbase worked on 10 finished decompositions and took a total time of 0.006\n", "Detector varclass worked on 2 finished decompositions and took a total time of 0.001\n", "Detection Time: 0.02\n", "GCG found 11 finnished decompositions.\n", " the current varclass distribution includes 116 classes but only 9 are allowed for propagatePartialdec() of var class detector\n" ] } ], "source": [ "m, *conss = build_model(n_locations, n_clusters, distances, demands, capacities)\n", "m.presolve()\n", "m.detect()\n", "\n", "decomps = m.listDecompositions()\n", "\n", "print(\"GCG found {} finnished decompositions.\".format(len(decomps)))" ] }, { "cell_type": "markdown", "id": "ed8ab777", "metadata": {}, "source": [ "### Inspecting Decompositions\n", "\n", "The call to `listDecompositions()` returns a list of `PartialDecomposition` objects. We can print a decomposition using the Python `print()` function to get a summary or access different fields directly.\n", "\n", "For a full overview of available methods, take a look at the online documentation for the `PartialDecomposition` class, or execute `help(d)` where `d` is a decomposition object." ] }, { "cell_type": "code", "execution_count": 5, "id": "accepting-magnet", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[, , , , , , , , , , ]\n", "Decomp scores: d.classicScore=-1.0000, d.borderAreaScore=-1.0000, d.maxWhiteScore=0.4851, d.maxForWhiteScore=0.4851\n" ] } ], "source": [ "print(decomps)\n", "\n", "d = decomps[2]\n", "\n", "print(\n", " f\"Decomp scores: {d.classicScore=:.04f}, {d.borderAreaScore=:.04f}, {d.maxWhiteScore=:.04f}, {d.maxForWhiteScore=:.04f}\"\n", ")" ] }, { "cell_type": "markdown", "id": "166c54bd", "metadata": {}, "source": [ "### Visualizing Decompositions\n", "In addition, GCG can create graphical visualizations of decompositions. They can easily be displayed in a Jupyter nodebook like so:" ] }, { "cell_type": "code", "execution_count": 6, "id": "b04b2964", "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAoAAAAHgCAIAAAC6s0uzAAAABmJLR0QA/wD/AP+gvaeTAAAgAElEQVR4nO3df3BU1f3/8bP8EENDTdJKGqFqE7SSNfwwjRUIJNDCgE5RwNqp1hasY51GHYWvTGs7Gp1kRIlGZxxtHbGxMyiWtjrIjzJiIECsNP4gMSkVLeqYhLAzsBlqGsgC+/1j2/1sQ7j3yrl733fPfT7+cJLdV27eOST79tz33d1QPB5XAADAW8OkCwAAIIhowAAACKABAwAggAYMAIAAGjAAAAJowAAACKABAwAggAYMAIAAGjAAAAJowAAACKABAwAggAYMAIAAGjAAAAJowAAACKABAwAggAYMAIAAGjAAAAJ814AjkcjNN9+cl5eXnZ09f/78ffv2SVcEAID7QvF4XLqG/xOLxcrKyiKRSE1NTXZ2dm1tbU9PT1tbW35+vvUXZmVlHTt2zJsiAQABkdYWOSJ9hz4LL774Ymtra2Nj4+zZs5VS06dPLyoqWr16dV1dnfUXHjt2zFf/J5FxQiF//a9YZmH1dLB6mlhAHdarFwqF0vvdffUvt2TJkj179nR2diZvWbBgwYcffvjRRx9ZfyG/gppYQB2sng5WTxMLqMO2Aad1bf01A+7o6AiHw6m3lJSUHDhwoL+/X6okAADSwV+noI8cOTJlypTUW3Jzc+PxeG9vb1ZWlvXXpvtcgfFYQB2sng5WTxMLqENw9fzVgOPx+FmvxVcq/+puMQCAIDu8Y1paj++vU9B5eXnRaDT1lmg0GgqFcnJybL/2aNvdOgHNL8+IgHgB+gHxAvQD4gXoB8QL0A+IF6AfEC9APyBegJNAWvlrer948eKWlpbPPvssecvVV1+9f/9+JxdhsQMGALjo8I5pAboIa+HChZ2dnU1NTYlPu7q6Ghsbr732WtmqAABwnb92wLFYrLS09PDhw8kX4uju7m5tbS0oKLD+QnbAAAB3BWsHPHLkyNdff72ysnL58uVLly7Nz8/fsWOHbfdNEJ8WiBegHxAvQD8gXoB+QLwA/YB4AR4ExAuwDYgX4EGAGbAvsAMGALgrWDtgAAACggYMAIAAGjAAAALMacDilwPYBsQL0A+IF+BBQLwA24B4AR4ExAvQD4gXoB8QL0A/wEVYXuAiLACAu7gICwAAA9GAAQAQYE4DFh826AfEC/AgIF6AfkC8AP2AeAH6AfEC9APiBegHxAvQDzADdgEzYACAu5gBAwBgIBowAAACjGrAxo8rbAPiBegHxAvQD4gXoB8QL0A/IF6ABwHxAmwD4gW4EkgfZsAAAAyBGTAAAAaiAQMAIMCoBsw8wzYgXoB+QLwA/YB4AfoB8QI8CIgXoB8QL0A/IF5AWjEDBgBgCMyAAQAwEA0YAAABRjVg8WmBeAH6AfECPAiIF2AbEC/Ag4B4AfoB8QL0A+IF6AeYActjBgwAcBczYAAADEQDBgBAgFENWHwaYRsQL8CDgHgB+gHxAvQD4gXoB8QL0A+IF6AfEC9AP8AMOO2YAQMA3MUMGAAAA9GAAQAQYFoDZp7h/4B4AfoB8QL0A+IF6AfEC/AgIF6AbUC8AG8CacIMGACAITADBgDAQDRgAAAEmNaAmWeIF6AfEC/Ag4B4AbYB8QI8CIgXoB8QL0A/IF6Ak0CaMAMGAGAIzIABADAQDRgAAAE0YAAABJjWgLlewDYgXoAHAfEC9APiBegHxAvQD4gXoB8QL0A/IF5A+nARFgAAQ+AiLAAADEQDBgBAgGkNWHxaIF6ABwHxAvQD4gXoB8QL0A+IF6AfEC/Ag4B4AbYBZsDCmAEDANzFDBgAAAPRgAEAEGBaAxafRugHxAvQD4gXoB8QL0A/IF6AfkC8AA8C4gXYBsQL8CDADFgLM2AAgLuYAQMAYCAaMAAAAgxswMbPM8QL0A+IF+BBQLwA24B4AR4ExAvQD4gXoB8QL8CVQDowAwYAYAjMgAEAMBANGAAAAQY2YOYZ4gV4EBAvQD8gXoB+QLwA/YB4AfoB8QL0A+IFOAmkAzNgAACGwAwYAAAD0YABABBgYAMWnxaIF6AfEC9APyBegH5AvAD9gHgB+gHxAjwIiBdgGxAvIE2YAQMAMARmwAAAGIgGDACAAAMbsB+mBf6fZ/AjiBfgQUC8ANuAeAEeBMQL0A+IF6AfYAacRsyAAQDuYgYMAICBaMAAAAigAQMAIMDABiw+7dcPiBegHxAvwIOAeAH6AfEC9APiBegHxAvQD4gXoB/gIqyzx0VYAAB3cREWAAAGogEDACDA6wa8ffv2ZcuWXXLJJaNHjy4qKqqqqopEIqmBSCRy88035+XlZWdnz58/f9++fWfxXYyfZ4gX4EFAvAD9gHgB+gHxAvQD4gXoB8QL0A+IF+BKwHVez4ArKyuPHj26aNGiCy+88O9///tTTz2Vn5/f2to6ZswYpVQsFisrK4tEIjU1NdnZ2bW1tT09PW1tbfn5+daHZQYMAHBXumfAI9J36CE9++yzl156afLTyZMn33TTTevXr7/llluUUi+++GJra2tjY+Ps2bOVUtOnTy8qKlq9enVdXZ3HdQIAkFZen4JO7b5KqcrKSqVUV1dX4tMNGzaMGzcu0X2VUuPHj58zZ86rr77qbY0AAKSd8EVYzc3NSqmSkpLEpx0dHeFwODVQUlJy4MCB/v7+L3RY5hm2AfEC9APiBegHxAvQD4gXoB8QL8CDgHgBtgHxApwEXCf5POAjR45cccUVeXl5LS0tw4cPV0qNHTt2zpw569atS2Yefvjh++67r7u7u6CgwOJQzIABAO4ybQac1N/fv3jx4r6+vm3btiW6r1IqHo+HQiGpkgAA8IxMAz5+/PiiRYv27t27ffv2CRMmJG/Py8uLRqOpyWg0GgqFcnJyPK8RAIA0EpgBx2Kx66+/vrm5ecuWLVOnTk29KxwOd3R0pN7S3t5eWFiYlZX1hb6F+LRAvAD9gHgB+gHxAjwIiBdgGxAvwIOAeAH6AfEC9APMgO2dOHHihhtu+Mtf/rJly5aKiopB9zY0NCxbtmzHjh2Ju7q6uhIv1vHYY49ZH5YZMADAXemeAXvdgG+99dY1a9bcdtttc+fOTd44YcKEKVOmKKVisVhpaenhw4eTL8TR3d3d2tpqfQWWogEDANxmWgO+/PLLB51kVkpVVVU99dRTiY8PHTq0fPnyzZs3DwwMlJeX19fXFxcX2x6WBgwAcJdp74bU3t4eP02y+yql8vPz165dG41G+/r6tm7d6qT7nk58GqEfEC/ANiBegAcB8QL0A+IF6AfEC9APiBegHxAvQD/ADDhd2AEDANxl2g4YAAAoGjAAACKMbcDMM/wfEC9APyBegH5AvAD9gHgB+gHxAjwIiBdgG2AGfJaYAQMA3MUMGAAAA9GAAQAQYGwDNn5cYRsQL0A/IF6AfkC8AP2AeAH6AfECPAiIF6AfEC/AScBdzIABABgCM2AAAAxEAwYAQICxDZhxhW1AvAD9gHgBHgTEC7ANiBfgQUC8AP2AeAH6AfECXMcMGACAITADBgDAQDRgAAAE0IABABBgbAP2w7je/xcUZHqF+gHxAvQD4gXoB8QL0A+IF6AfEC9AP8BFWDK4CAsA4C4uwgIAwEA0YAAABBjbgMWnEfoB8QL0A+IF6AfEC9APiBegHxAvQD8gXoAHAfECbAPMgNOCGTAAwF3MgAEAMBANGAAAASY34EwfV9gGxAvQD4gXoB8QL8CDgHgBtgHxAjwIiBegHxAvwJWAi5gBAwAwBGbAAAAYiAYMAIAAkxsw4wrxAvQD4gV4EBAvQD8gXoB+QLwA/YB4AfoB8QKcBFzEDBgAgCEwAwYAwEA0YAAABJjcgMWnBeIF2AbEC/AgIF6AfkC8AP2AeAH6AfEC9APiBXgQYAYsgBkwAMBdzIABADAQDRgAAAEmN2DxaYRtQLwA/YB4AfoB8QL0A+IF6AfEC9APiBfgQUC8AP0AM2D3MQMGALiLGTAAAAaiAQMAIIAGDACAAJMbsPi0Xz8gXoB+QLwA/YB4AR4ExAuwDYgX4EFAvAD9gHgB+gEuwvrCuAgLAOAuLsICAMBANGAAAAQY3oCNH1fYBsQLsA2IF+BBQLwA/YB4AfoB8QL0A+IF6AfEC3Al4BZmwAAADIEZMAAABqIBAwAgwPAGzDzDNiBegH5AvAD9gHgB+gHxAvQD4gXoB8QL8CAgXoCLmAEDADAEZsAAABiIBgwAgADDG7D4tEC8AP2AeAH6AfEC9APiBXgQEC/ANiBegAcB8QL0A8yAvcYMGADgLmbAAAAYiAYMAIAAwxuw+DTCNiBegH5AvAD9gHgBHgTEC9APiBegHxAvQD8gXoB+gBmwy5gBAwDcxQwYAAAD0YABABBgeAMWHzZ4EBAvwDYgXoAHAfEC9APiBegHxAvQD4gXoB8QL8CbgCuYAQMAMARmwAAAGIgGDACAAPMbMPMM8QL0A+IF6AfEC9APiBegHxAvQD8gXoAHAfECnARcwQwYAIAhMAMGAMBANGAAAASY34AZV9gGxAvQD4gXoB8QL8CDgHgBtgHxAjwIiBegHxAvwC2SM+AlS5b8+c9//slPftLQ0JC8MRKJrFixYtOmTQMDA+Xl5fX19RMnTrQ9FDNgAIC7jJ0Bv/baazt27DjnnHNSb4zFYvPmzXvjjTfq6uqef/75gwcPVlZWHjp0SKpIAADSRKYBf/7551VVVY888sjIkSNTb3/xxRdbW1vXrl17yy233HDDDZs2bert7V29erVIkQAApI9MA/71r389fvz4n/70p4Nu37Bhw7hx42bPnp34dPz48XPmzHn11Vc9LxAAgPQSaMBvv/32b37zm2eeeSYUCg26q6OjIxwOp95SUlJy4MCB/v7+s/524uN68QI8CIgXYBsQL8CDgHgB+gHxAvQD4gXoB8QL0A9wEdbQTp48WVZWVllZ+fjjjyulsrOzr7/++uRFWGPHjp0zZ866deuS+Ycffvi+++7r7u4uKCiwOCwXYQEA3GXaRVj19fWRSOTBBx8c8t54PH76thgAAPOM8PKbHTx4sLq6+sknnzx58mRvb2/ixoGBgd7e3uzs7BEjRuTl5UWj0dQviUajoVAoJyfHyzoBAEg3T3fAn376aV9f36233pr7X319fS+99FJubu62bduUUuFwuKOjI/VL2tvbCwsLs7Kyzvqbik8j9APiBegHxAvQD4gXoB8QL0A/IF6AfkC8AP2AeAEeBAycAR89evTdd99NvWXBggUVFRW/+MUvJk2alJeX19DQsGzZsh07dlRUVCilurq6ioqKqqqqHnvsMesjMwMGALgr3TNg4XdDGnQRViwWKy0tPXz4cE1NTXZ2dm1tbXd3d2trq/UVWIoGDABwm2kXYVkbOXLk66+/XllZuXz58qVLl+bn5+/YscO2+wIAkHGEG/Dnn3+e+kLQSqn8/Py1a9dGo9G+vr6tW7cWFxfrfxfj5xniBegHxAvQD4gXoB8QL8CDgHgBtgHxAjwIiBfgSkCf8Clot3AKGgDgrmCdggYAICBowAAACAhEA2ZcIV6AfkC8AP2AeAEeBMQL0A+IF6AfEC9APyBegJOAPmbAAAAMgRkwAAAGogEDACAgEA2YcYV+QLwA24B4AR4ExAvQD4gXoB8QL0A/IF6AfkC8AFcwAwYAYAjMgAEAMBANGAAAAYFowH6YFvh/nsGPIF6AfkC8AP2AeAH6AfEC9APiBXgQYAbsGmbAAAB3MQMGAMBANGAAAAQEogGLDxv0A+IF6AfEC9APiBegHxAvwIOAeAG2AfECPAiIF6AfYAbsFDNgAIC7mAEDAGAgGjAAAAJowAAACAhKA+Z6AQMC4gXYBsQL8CAgXoB+QLwA/YB4AfoB8QKcBNKNi7AAABgCF2EBAGAgGjAAAAKC0oCDMK7gZxQvQD8gXoB+QLwA/YB4AfoB8QL0A+IFeIAZMAAAQ2AGDACAgWjAAAAICEoDFh8niBegHxAvQD8gXoB+QLwA/YB4AR4ExAuwDYgX4EGAGbBHmAEDANzFDBgAAAPRgAEAEBCUBiw+jbANiBegHxAvQD8gXoB+QLwADwLiBegHxAvQD4gXoB9gBuwOZsAAAHcxAwYAwEA0YAAABJjTgBlXGBAQL8A2IF6ABwHxAvQD4gXoB8QL0A+IF+BKIK2YAQMAMIR0z4DNacDSJQAATJPWFjkifYf22D11H1rcW///LjHjfzUAAN5I99bOqB1wKPSfHyf5QerHZvykAABvpLaSdAjQDtizSgAAsGXUDliTGUsBAHAFO2CnrJcpFAqxRQYA+Ic5O2DbBpyMDTkhVuyAAQAp2AG7hh0wAMA/grIDnlFe8WbzTs3vYsZaAQCcSPcOOCgN2MkReCYxACAp3Q3YnNeCBgAgg7AD/r8jWF+ipTgFDQBBwkVY3rl79X6Le7lKCwDgInbA/1FRUblzZ5NmGWYsJgBAcRGWQ+leJsVVWgAQMDRgR7xpwIO+1+nTYjMWEwCgmAH7Ci/lAQBwCztgp8pnVjTv5qU8ACAoOAXtiAcN2EkNDIkBwBg0YEd80oBTixny+cTiRQIAHGIGnEkYEgMAHJLfOLrCDzvgb0+b9be3dmkeRPynAAAkcAraET80YFsMiQEgg9CAHcmUBqwsJ8SKHTAA+AYzYKMwJAYAJGTAxtGJjNgBX1E28723d+scwf8/IwAYg1PQjmREA7ZlPSRmQgwAXqIBO2JMAz79haaZEAOACGbAwWLxnsRMiAHAJCZsHJUpO+DwpBl/f/9NnSMYsAgA4BOcgnbEjAZsjacRA4CXaMCOBKQBn/7s4UE/uPGLAACeMXMGvHnz5lWrVr377rvDhw8vLi5etWpVRUVF4q5IJLJixYpNmzYNDAyUl5fX19dPnDhRpEgfspgQK4bEAJBRBBrwb3/729tvv33u3Lk1NTWjR49ua2vr6elJ3BWLxebNmxeJROrq6rKzs2traysrK9va2vLz872v029mlM+ybbHJd2Q6E7bIAOATXp+5/eSTTyZOnPizn/3siSeeOP3eF154YenSpY2NjbNnz1ZKdXZ2FhUV3XnnnXV1ddaHDcIpaFsMiQHARabNgO+///5HHnnk0KFDOTk5p06dGjZsWOq9S5Ys2bNnT2dnZ/KWBQsWfPjhhx999JH1YWnA6n+3v2d6PjGrBAAOmTYD3r1796RJk9auXbtq1arOzs6LLrrorrvuuueeexLNo6OjIxwOp+ZLSkq2bt3a39+flZXlcamZiNeaBoBM4XUD7u7u7u7urq6urq2tvfjii9etW7dixYrjx4//8pe/VEodOXJkypQpqfnc3Nx4PN7b22vbgIccfz7wwAPV1dXule9rZd+eyZAYAM5CdXX1gw8+6PE39boBnzp16l//+tfvf//76667Tik1b968Tz755NFHH125cuXw4cMTz6s5uyPTOf721k7rgJMhsasVAUBmqK6uPn23dtb9yKFh9hFXfeUrX1FKffe7303eMnfu3N7e3k8//VQplZeXF41GU/PRaDQUCuXk5HhcJwAAaeX1DjgcDr/11lunv3ZE4mqscDjc0tKSmm9vby8sLGQA7JbEHtf2BT0AAOnmdQNetGjRmjVrtmzZcsMNNyRu2bx589ixYy+88EKl1MKFC1955ZWmpqbE63J0dXU1NjZWVVV5XKTBOAUNAD7h9b4nHo9/5zvfee+99+6///6LLrpo3bp169evf+aZZ26//XalVCwWKy0tPXz4cE1NTeKFOLq7u1tbWwsKCqwPywbOiYrKyp1NTZoHYZ0BBIRpzwNWSh09evS+++774x//GI1GL7300nvvvffHP/5x8t5Dhw4tX7588+bNyZeiLC4utj0mDdgVvJQHACQZ2IDTgQbsisQlf9YTYtYZQECY9kIc8DmGxADgDUM2juyAXVE+s6J5t82TiW3xDwHADJyCdoQG7A2GxACCgwbsCA3YG6FQ6PQJsfrf9ecfAoAZmAHDX+5evd/iXobEAOCQIRtHdsDeuPKqWS17dukcgX8mAJmCU9CO0IB9wnpIzIQYQAahATtCA/aJ1DcPGXJazD8TgEzBDBgZxnoH7GUlAOBnhmwc2QH7xOQrytvea9Y5Av+OAHyCU9CO0IAzAk8jBpBBaMCO0IAzgvWEOPFf/h0B+AQzYBiF15oGgARDNo7sgDPCrFmVu3bxhsQAMgOnoB2hAZuBITEA/6ABO0IDNkNySGzxitP8QwPwBjNgBAtDYgABYcjGkR2wGabNmPXWm1qvNa0YEgNwCaegHaEBBwRDYgCeoQE7QgMOiMSQeMgJsWJIDMBVzICB/8GQGIAZDNk4sgMOiCvKyt97W+u1phVDYgDOcAraERowEhgSA3ALDdgRGjASQqGQ9YRYsQMG4AwzYOCLuXv1fot7GRID8Ilh0gUAABBEhpy55RQ0EioqKnfu5P0eALiAGbAjNGA4xFVaAByiATtCA4ZDyfd7UGd+QQ9+lwAoLsICXMdLeQDwA0M2juyA4dCM8oo3m3fqHIHfNCAgOAXtCA0YbrEeEjMhBoKDBuwIDRhuSQ6JmRADAccMGPCa9Q7Yy0oAGMyQjSM7YLjlyqtmtezZpXMEfhUBM3AK2hEaMLzB04iB4KABO0IDhjeSb/ZwpgmxYgcMmIIZMOAvvNkDAFcYsnFkBwxv8FrTQHBwCtoRGjB8giExYAwasCM0YPhE4mnEZ5oQJz7mdxXICMyAgQzDa00DcMKQjSM7YPiE/mtNK4bEgD9wCtoRGjAyBUNiIFPQgB2hASNTDBoSDzkt5pcZ8ANmwIBpGBIDUOyAAY9dedXMlj27NQ/CbzvgAU5BO0IDhjEYEgM+QQN2hAYMY6QOiXlPYkAQM2AgcBgSA0FgyMaRHTCMMWlq+ft7mzUPwp8DoI9T0I7QgBEcDIkBb9CAHaEBIzh4T2LAG8yAAQzGexIDBhgmXQAAAEFkyJlbTkEjOCorK5uamnSOwB8L4AQzYEdowECS9VVaXKIFOEQDdoQGDCQlXspDneEtHxQ7YMAZLsIC8IVZ74C9rATAmRiycWQHDCTNKK94s3mnzhH4awIUp6AdogEDDvE6HoBDNGBHaMCAQ8kJsTrzWz7w1wQoZsAAXMebPQB+YMjGkR0w4JD+04gVQ2IEA6egHaEBA25hSAwk0IAdoQEDbrF4GnHyA/7cEATMgAF4jSEx4AFDNo7sgAG3zJxZsXu31tOIFVtkGIFT0I7QgAHPMCRGQNCAHaEBA55JDIlPf/Zw6i38PcIABs6Ad+3a9dBDD+3du/f48ePf/OY3ly9f/sMf/jB5byQSWbFixaZNmwYGBsrLy+vr6ydOnOh9kQAsMCQG9Hm9cXzvvfemTZtWUlJyzz33nHvuuQ0NDa+99tratWtvvPFGpVQsFisrK4tEIjU1NdnZ2bW1tT09PW1tbfn5+daHZQcMeOaq6bP2/HWX5kH4g4X/mXYKeuXKlXV1dT09PWPHjlVKnThxorCwMBwOb9myRSn1wgsvLF26tLGxcfbs2Uqpzs7OoqKiO++8s66uzvqwNGDAPxgSwwymnYIeGBgYPnz4eeed959vP2LEeeedd+rUqcSnGzZsGDduXKL7KqXGjx8/Z86cV1991bYBA/CVJ+691GJCDEB534CXLVv27LPP3nHHHffff/+oUaN+97vf/eMf/3jkkUcS93Z0dITD4dR8SUnJ1q1b+/v7s7KyPC4VwFm7e/V+i3sZEgPK+wY8efLkxsbGJUuWPPfcc0qp0aNHv/TSS1dffXXi3iNHjkyZMiU1n5ubG4/He3t7bRtw6nu8JD3wwAPV1dXulA7AmanfKrdtsUP+waZiuwwvVVdXP/jggx5/U68b8AcffPD973+/uLj46aefHjVq1Msvv3zTTTeNGDHiuuuuU0olzlOd3ZH5cwV84t0Wm0u0nAyJXa0IsFFdXX36bu2s+5FDXjfglStXhkKhjRs3jho1Sik1f/78zs7OqqqqRAPOy8uLRqOp+Wg0GgqFcnJyPK4TQFolW+yQrzgtWRngFa8bcGtr6+WXX57ovgnf+ta3tm3b1tvbm5OTEw6HW1paUvPt7e2FhYUMgAHDsAMGvG7AX/va19ra2o4dO3buuecmbnnrrbfGjBkzZswYpdTChQtfeeWVpqamiooKpVRXV1djY2NVVZXHRQJIq+JJ0zWHxIycYACvnxiwdu3aH/3oRzNnzrz99ttHjRq1fv36l19++Ve/+lVNTY1SKhaLlZaWHj58OPlCHN3d3a2trQUFBdaH5RkOgEmsh8Q8jRjeMO2FOJRSr7322qOPPrpv376BgYEJEyb8/Oc/v+WWW4YNG5a499ChQ8uXL9+8eXPypSiLi4ttj0kDBkxy+nsSq/99PjF/7/CAgQ04HWjAgEnYAcMPaMCO0IABkxRedtXHH+zROQIPCNBHA3aEBgwEB681DW+ku7MMS9+hAQDAmRiycWQHDASH7SVailPQcINp74YEAPp4HQ8YwJCNIztgIDgqKyubmpo0D8IjBmxxEZYjNGAASVylBVfQgB2hAQNISgyJT58Qp37AIwZsMQMGgC+MITH8z5CNIztgAEmzKip37WRIDF2cgnaEBgzAOYbEcIIG7AgNGIBzoVBoyAmxYkiMFMyAAcB9d6/eb3EvQ2J4wJCNIztgAM7NKK94s3mn5kF4zDEep6AdoQEDcBFDYigasEM0YAAuSr7ctDrzK07zmGM8ZsAAIIBnEiPdDNk4sgMG4KKyb898+2+7NQ/Cg1Km4xS0IzRgAF5iSBwENGBHaMAAvGTxnsTJD3hQynTMgAHAjxgSQ5MhG0d2wAC8NKW0vPXdZp0j8JDlf5yCdoQGDMBXrIfETIgzAg3YERowAF+xeE/iBB6y/I8ZMABkJOsdsJeVwJ8M2TiyAwbgK5eVTP+g/a86R+AxTRynoB2hAQPIIDyNOCPQgB2hAQPIINYTYp5G7BPMgAHAQDyNGIZsHNkBA8ggsyoqd+1s0jwID3rpxiloR2jAAEzCkNgP0t1ZhqXv0AAA4EwM2TiyA4qnhLAAAAmuSURBVAZgklAoZH2JluIUdPpxERYABNHdq/db3MtVWgYwZOPIDhiASSoqK3c2cZWWMC7CcoQGDCBQuErLAzRgR2jAAAIldUh8pmkxj4qamAEDAIbAkDjTGbJxZAcMIFBmzarctYshcXpxCtoRGjAApGJIrI8G7AgNGABSJYfEZ5oQK3bAdpgBAwDOBkNinzNk48gOGABSTZ9R8dc3d2oeJOCPq5yCdoQGDABfCENiWzRgR2jAAPCFhEIhdebnECc+DvjjKjNgAEBa2O6APaskmAzZOLIDBoAv5FtXznynZbfOEYx/1OUUtCM0YABwl/WQOAgTYhqwIzRgAHBXYkis/vsAG8AJMTNgAIAM6x2wl5UYyZCNIztgAHDX5VNmdLS+qXOETH9Y5hS0IzRgAPBSEJ5GTAN2hAYMAF6ynRArdsB2mAEDAM4GTyPWZMjGkR0wAHipsrKyqcnwNyTmFLQjNGAA8BUDhsQ0YEdowADgK4Nea/r0D1Tgd8DMgAEAacGQ2JohG0d2wADgKzPKK95szuw3JOYUtCM0YADILP4fEtOAHaEBA0BmCYVCpz97eNCDudkNmBkwAEDG3av3W9xr/JB4mHQBAAAEkSFnbjkFDQCZxf8v5cEM2BEaMAAYRvwqLRqwIzRgADBM8v0e1Jnf8iGjGzAXYQEAfMrsl/IwZOPIDhgADDNzZsXu3ZIv5cEpaEdowAAQNOkeEmdeA+7u7l61alVLS8vevXuPHTv28ccfX3zxxamBSCSyYsWKTZs2DQwMlJeX19fXT5w40eG9Z/wxaMAAEDDJIbHFWz4EqwHv3r17yZIlZWVl//73v7dv3z6oAcdisbKyskgkUlNTk52dXVtb29PT09bWlp+fb3uv1Y9BAwaAgMn0HbCKu+3kyZOJD+rr65VSH3/8ceq9DQ0NSqnGxsbEp5999tk555yzYsUKJ/daSMcPAgDws6umz0xrE0x3Z0lje3/iiSfuueeeQTvgJUuW7Nmzp7OzM3nLggULPvzww48++sj2XgvsgDVVV1dXV1dLV5GpWD0drJ4mFtCC5hY5805BJw3ZgC+77LKLLrpo69atyVtWrlxZV1fX19eXlZVlfa/F96IBa2IBdbB6Olg9TSyghcSQ2PotHwQbsNfPAz5y5MiUKVNSb8nNzY3H4729vVlZWdb3elspACDj+fmZxF434MT/epzdvdaG/MIHHniAkzMAEExXlJXbttizbjr6vG7AeXl50Wg09ZZoNBoKhXJycmzvtcZJGABAqnf+tss6YD0kTvf+2OsGHA6HW1paUm9pb28vLCxMnGG2vhcAAHc9ce+lFhPitPK6AS9cuPCVV15pamqqqKhQSnV1dTU2NlZVVTm5FwAAd929ev+Z7kr7hNj1JzadOnVq/fr169evX7p0qVLq6aefXr9+/e7duxP3DgwMlJSUXHDBBc8///wf/vCHyZMnn3/++d3d3U7utZDeNQIABJLrLTKV+xvtEydOjBw5ctCN11xzzcaNGxMfHzp0aPny5Zs3b06+2GRxcXEyaX0vAABm4AlkAAAIGCZdAAAAQUQDBgBAAA0YAAABNGAAAATQgAEAEEADBgBAAA0YAAABNGAAAATQgAEAEEADBgBAAA0YAAABhjTgSCRy88035+XlZWdnz58/f9++fdIV+cu2bdtC/+urX/1qasB6AYO2vN3d3Xfddde0adOysrJCodAnn3wyKKCzXMYvpvXqaf4qOglktO3bty9btuySSy4ZPXp0UVFRVVVVJBJJDWiuT8BXz3ePhGl9ryVvDAwMTJ48uaCgYM2aNS+//PKkSZPGjh3b09MjXZePvP7660qpxx9/fP1/bdiwIXmv9QIGcHl37do1duzYa665Zvbs2Uqpjz/+OPVeneUKwmJar57Or6KTQKarqKiYOnXqQw891NDQsHLlytGjR3/jG984evRo4l7N9Qn46sX990hoQgNuaGhQSjU2NiY+/eyzz84555wVK1bIVuUriV+7999/f8h7rRcwgMt78uTJxAf19fWntxCd5QrCYlqvns6vopNApvvggw9SP127dq1Sas2aNYlPNdcn4KsX998joQkNePHixePGjUu9Zf78+UVFRVL1+FDy166vr+/UqVOD7rVewCAv75AtRGe5ArWY1g34LH4VnQQM09XVpZR66KGHEp9qrk/AVy/uv0dCE2bAHR0d4XA49ZaSkpIDBw709/dLleRP5eXlX/rSl7KzsxcvXvzPf/4zebv1ArK8g+gsF4uZcHa/ik4ChmlublZKlZSUJD7VXJ+Ar16Sfx4JTWjAR44cyc3NTb0lNzc3Ho/39vZKleQ3X/7yl++4445nn31248aNK1eufOONN6ZPn37w4MHEvdYLyPIOorNcLKbOr6KTgEmOHDly7733Tp069Xvf+17yFp31CfjqKf89Eo4466/0j3g8HgqFpKvwtSuvvPLKK69MfJy4OqaiouLJJ59ctWqVsltAlncQneViMXV+FZ0EjNHf37948eK+vr5t27YNHz48caPm+gR89ZT/HglNaMB5eXnRaDT1lmg0GgqFcnJypEryuVmzZl144YUtLS2JT60XkOUdRGe5WMxBvtCvopOAGY4fP75o0aK9e/du3759woQJyds11yfgq3c68UdCE05Bh8Phjo6O1Fva29sLCwuzsrKkSvK/EydOJP9vznoBWd5BdJaLxTyd819FJwEDxGKx66+/vrm5ecuWLVOnTk29S3N9Ar56Q5J9JDShAS9cuLCzs7OpqSnxaVdXV2Nj47XXXitbla+cOHEi9dNNmzZ1d3dfddVViU+tF5DlHURnuVhMnV9FJ4FMd+LEiR/84AdvvPHGxo0bp02bNuhezfUJ+Oop/z0ShuLxuM7X+0EsFistLT18+HBNTU12dnZtbW13d3dra2tBQYF0aX4xf/78Cy64YPLkyWPGjHnnnXeee+65/Pz8d9555/zzz1d2CxjA5Y3H43/605+UUps2bWpoaHj66afPP//8goKCGTNmKL3lCsJiWq+ezq+ik0Cmu/XWW9esWXPbbbfNnTs3eeOECROmTJmitNcn4KunfPhIqPMcJv/o6em58cYbc3JyRo8ePW/evI6ODumK/KWurq60tDQnJ2fEiBFf//rXb7vttoMHD6YGrBcwaMsbi8VO/0u55pprkgGd5TJ+Ma1XT/NX0Ukgow16oktCVVVVMqC5PgFfPb89EpqwAwYAIOOYMAMGACDj0IABABBAAwYAQAANGAAAATRgAAAE0IABABBAAwYAQAANGAAAATRgAAAE0IABABBAAwYAQAANGAAAAf8fA6+u3bnzbYcAAAAASUVORK5CYII=", "image/svg+xml": "\n\n\nGnuplot\nProduced by GNUPLOT 5.4 patchlevel 1 \n\n\n\n\n\n\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t \n\t \n\t\n\t\n\t \n\t \n\t\n\n\n\n\n\t\t\n\t\t 0\n\t\n\n\n\t\t\n\t\t 20\n\t\n\n\n\t\t\n\t\t 40\n\t\n\n\n\t\t\n\t\t 60\n\t\n\n\n\t\t\n\t\t 80\n\t\n\n\n\t\t\n\t\t 100\n\t\n\n\n\t\t\n\t\t 0\n\t\n\n\n\t\t\n\t\t 500\n\t\n\n\n\t\t\n\t\t 1000\n\t\n\n\n\t\t\n\t\t 1500\n\t\n\n\n\t\t\n\t\t 2000\n\t\n\n\n\t\t\n\t\t 2500\n\t\n\n\n\n\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\t\n\t\t\n\t\n\t\n\n\n\tgnuplot_plot_1\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\t\n\n\n\t\n\n\n\n\n\n\n\n\t\n\n\n\n\n\n", "text/plain": [ "" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "d" ] }, { "cell_type": "markdown", "id": "7fb3d799", "metadata": {}, "source": [ "### Selecting Decompositions\n", "After this investigation, we decide that we like this particular decomposition. The following code orders GCG to select our decomposition instead of an automatic one. Then, the optimization process is started." ] }, { "cell_type": "code", "execution_count": 7, "id": "further-curtis", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "A Dantzig-Wolfe reformulation is applied to solve the original problem.\n", "Chosen structure has 50 blocks and 51 linking constraints.\n", "This decomposition has a maxwhite score of 0.485149.\n", "Matrix has 50 blocks, using 50 pricing problems.\n", "\n", " time | node | left |SLP iter|MLP iter|LP it/n| mem |mdpt |ovars|mvars|ocons|mcons|mcuts| dualbound | primalbound | deg | gap \n", "p 0.2s| 1 | 0 | 0 | 0 | - | 34M| 0 |2550 | 0 | 101 | 0 | 0 | 0.000000e+00 | 2.711000e+03 | -- | Inf \n", "p 0.2s| 1 | 0 | 0 | 0 | - | 33M| 0 |2550 | 0 | 101 | 0 | 0 | 0.000000e+00 | 1.785000e+03 | -- | Inf \n", "p 0.3s| 1 | 0 | 0 | 0 | - | 33M| 0 |2550 | 0 | 101 | 0 | 0 | 0.000000e+00 | 1.102000e+03 | -- | Inf \n", " 0.3s| 1 | 0 | 0 | 0 | - | 33M| 0 |2550 | 0 | 101 | 0 | 0 | 0.000000e+00 | 1.102000e+03 | -- | Inf \n", " \n", " 0.3s| 1 | 0 | 0 | 0 | - | 34M| 0 |2550 | 50 | 102 | 102 | 0 | 0.000000e+00 | 1.102000e+03 | 0.00%| Inf 0.3s| 1 | 0 | 0 | 0 | - | 34M| 0 |2550 | 150 | 102 | 102 | 0 | 0.000000e+00 | 1.102000e+03 | 0.00%| Inf \n", "\n", "\n", "Starting reduced cost pricing...\n", " 0.5s| 1 | 0 | 2081 | 2081 | - | 41M| 0 |2550 |1699 | 102 | 102 | 0 | 7.050000e+02 | 1.102000e+03 | 36.95%| 56.31%d 1.0s| 1 | 0 | 3055 | 3055 | - | 57M| 0 |2550 |1749 | 102 | 102 | 0 | 7.050000e+02 | 1.016000e+03 | 36.95%| 44.11%\n", "X 1.4s\n", "| 1 | 0 | 3055 | 3055 | - | 57M| 0 |2550 |1799 | 102 | 102 | 0 | 7.050000e+02 | 7.730000e+02 | 36.95%| 9.65%\n", "Y 1.5s| 1 | 0 | 3055 | 3055 | - | 57M| 0 |2550 |1849 | 102 | 102 | 0 | 7.050000e+02 | 7.580000e+02 | 36.95%| 7.52%\n", " 1.5s| 1 | 0 | 3055 | 3055 | - | 57M| 0 |2550 |1849 | 102 | 102 | 0 | 7.050000e+02 | 7.580000e+02 | 36.95%| 7.52%\n", " 1.5s| 1 | 0 | 3055 | 3055 | - | 57M| 0 |2550 |1849 | 102 | 102 | 0 | 7.050000e+02 | 7.580000e+02 | 36.95%| 7.52%\n", " 1.5s| 1 | 2 | 3055 | 3055 | - | 57M| 0 |2550 |1849 | 102 | 102 | 0 | 7.050000e+02 | 7.580000e+02 | 36.95%| 7.52%\n", "*r 1.5s| 2 | 1 | 3063 | 3063 | 316.0 | 58M| 1 |2550 |1849 | 102 | 102 | 0 | 7.050000e+02 | 7.140000e+02 | -- | 1.28%\n", "*r 2.2s| 16 | 5 | 6962 | 6962 | 281.0 | 61M| 5 |2550 |2305 | 102 | 102 | 0 | 7.102222e+02 | 7.130000e+02 | -- | 0.39%\n", "\n", "SCIP Status : problem is solved [optimal solution found]\n", "Solving Time (sec) : 2.55\n", "Solving Nodes : 21\n", "Primal Bound : +7.13000000000000e+02 (13 solutions)\n", "Dual Bound : +7.13000000000000e+02\n", "Gap : 0.00 %\n" ] } ], "source": [ "d.isSelected = True\n", "\n", "m.optimize()" ] }, { "cell_type": "markdown", "id": "f846322a", "metadata": {}, "source": [ "## Use-Case 3: Building a custom Decomposition\n", "In the previous use-cases we run GCG with automatically detected decompositions. This is useful if we do not know the exact structure of a model but still want to exploit GCG's decomposition approach.\n", "\n", "However, for our model we *do* know its structure. If you take another look at our `build_model()` method, you will notice that we store the created constraints in different variables based on their type. This is a typical approach when we want to specify a custom decomposition after building the model using the Python interface.\n", "\n", "In the following code, we recreate our model and use the different constraint types fo select constraints for reformulation and constraints for the Dantzig-Wolfe master problem." ] }, { "cell_type": "code", "execution_count": 8, "id": "technical-syracuse", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "GCG version 3.5.0 [GitHash: 202908425-dirty]\n", "Copyright (C) 2010-2021 Operations Research, RWTH Aachen University\n", " Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)\n", "\n", "SCIP version 8.0.0 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 6.0.0] [GitHash: 8441670cd5-dirty]\n", "Copyright (C) 2002-2021 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)\n", " added complete decomp for original problem with 50 blocks and 51 masterconss, 0 linkingvars, 0 mastervars, and max white score of 0.485149 \n", "there is an original decomposition and problem is not presolved yet -> disable presolving and start optimizing (rerun with presolve command before detect command for detecting in presolved problem) \n", "presolving:\n", "presolving (0 rounds: 0 fast, 0 medium, 0 exhaustive):\n", " 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients\n", " 0 implications, 0 cliques\n", "presolved problem has 2550 variables (2550 bin, 0 int, 0 impl, 0 cont) and 101 constraints\n", " 101 constraints of type \n", "transformed objective value is always integral (scale: 1)\n", "Presolving Time: 0.00\n", " calculated translation; number of missing constraints: 0; number of other partialdecs: 1 \n", "Preexisting decomposition found. Solution process started...\n", "\n", "A Dantzig-Wolfe reformulation is applied to solve the original problem.\n", "Chosen structure has 50 blocks and 51 linking constraints.\n", "This decomposition has a maxwhite score of 0.485149.\n", "Matrix has 50 blocks, using 50 pricing problems.\n", "\n", " time | node | left |SLP iter|MLP iter|LP it/n| mem |mdpt |ovars|mvars|ocons|mcons|mcuts| dualbound | primalbound | deg | gap \n", "p 0.1s| 1 | 0 | 0 | 0 | - | 28M| 0 |2550 | 0 | 101 | 0 | 0 | 0.000000e+00 | 2.848000e+03 | -- | Inf \n", " 0.1s| 1 | 0 | 0 | 0 | - | 28M| 0 |2550 | 0 | 101 | 0 | 0 | 0.000000e+00 | 2.848000e+03 | -- | Inf \n", " \n", " 0.1s| 1 | 0 | 0 | 0 | - | 28M| \n", " 0 |2550 | 50 | 102 | 102 | 0 | 0.000000e+00 | 2.848000e+03 | 0.00%| Inf 0.1s| 1 | 0 | 0 \n", "| 0 | - | 28M| 0 |2550 | 50 | 102 | 102 | 0 | 0.000000e+00 | 2.848000e+03 | 0.00%| Inf 0.3s| 1 | 0 | 1839 | 1839 | - | 38M| 0 |2550 |2302 | 102 | 102 | 0 | 0.000000e+00 | 2.848000e+03 | 49.42%| Inf 0.6s| 1 | 0 | 3939 | 3939 | - | 41M| 0 |2550 |2933 | 102 | 102 | 0 | 7.024809e+02 | 2.848000e+03 | 35.22%| 305.42% 0.6s| 1 | 0 | 3939 | 3939 | - | 41M| 0 |2550 |2933 | 102 | 102 | 0 | 7.050000e+02 | 2.848000e+03 | 35.29%| 303.97%d 1.2s| 1 | 0 | 5187 | 5187 \n", "Starting reduced cost pricing...\n", "\n", "\n", "| - | 51M| 0 |2550 |2983 | 102 | 102 | 0 | 7.050000e+02 | 1.016000e+03 | 35.29%| 44.11%\n", "X\n", " 1.6s| 1 | 0 | 5187 | 5187 | - | 51M| 0 |2550 |3033 | 102 | 102 | 0 | 7.050000e+02 | 8.040000e+02 | 35.29%| 14.04%\n", " 1.7s| 1 | 0 | 5187 | 5187 | - | 51M| 0 |2550 |3083 | 102 | 102 | 0 | 7.050000e+02 | 8.040000e+02 | 35.29%| 14.04%\n", " 1.8s| 1 | 0 | 5187 | 5187 | - | 51M| 0 |2550 |3083 | 102 | 102 | 0 | 7.050000e+02 | 8.040000e+02 | 35.29%| 14.04%\n", " 1.8s| 1 | 2 | 5187 | 5187 | - | 51M| 0 |2550 |3083 | 102 | 102 | 0 | 7.050000e+02 | 8.040000e+02 | 35.29%| 14.04%\n", "c 2.1s| 5 | 6 | 6968 | 6968 | 585.0 | 53M| 2 |2550 |3315 | 102 | 102 | 0 | 7.093889e+02 | 7.350000e+02 | -- | 3.61%\n", "*r 2.3s| 7 | 4 | 7395 | 7395 | 461.2 | 54M| 2 |2550 |3362 | 102 | 102 | 0 | 7.093889e+02 | 7.190000e+02 | -- | 1.35%\n", "*r 2.3s| 7 | 2 | 7534 | 7534 | 484.3 | 54M| 2 |2550 |3469 | 102 | 102 | 0 | 7.093889e+02 | 7.130000e+02 | -- | 0.51%\n", "\n", "SCIP Status : problem is solved [optimal solution found]\n", "Solving Time (sec) : 2.54\n", "Solving Nodes : 9\n", "Primal Bound : +7.13000000000000e+02 (9 solutions)\n", "Dual Bound : +7.13000000000000e+02\n", "Gap : 0.00 %\n" ] } ], "source": [ "m, conss_assignment, conss_capacity, cons_pmedian = build_model(\n", " n_locations, n_clusters, distances, demands, capacities\n", ")\n", "\n", "conss_master = conss_assignment + [cons_pmedian]\n", "conss_reform = conss_capacity\n", "\n", "pd = m.createPartialDecomposition()\n", "pd.fixConssToMaster(conss_master)\n", "\n", "for block, c in enumerate(conss_reform):\n", " pd.fixConsToBlock(c, block)\n", "\n", "m.addPreexistingPartialDecomposition(pd)\n", "\n", "m.optimize()" ] }, { "cell_type": "markdown", "id": "33d89973", "metadata": {}, "source": [ "## Summary\n", "\n", "With that, we have seen the most important features to use GCG as a solver through the Python interface. In a different example, we will take a look at how GCG can be extended using Python code." ] } ], "metadata": { "interpreter": { "hash": "f957d0bb3c15b1cedc83fb550c82626212cd1f371f4f3e6cf365a0241acd002e" }, "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.9.8" }, "metadata": { "interpreter": { "hash": "96c411c10837af9498e15621947793a2592cd914a8b21febdb89cd6ff87a6197" } } }, "nbformat": 4, "nbformat_minor": 5 }