1.1 --- a/test/min_cost_flow_test.cc Thu Feb 28 02:57:36 2008 +0000
1.2 +++ b/test/min_cost_flow_test.cc Thu Feb 28 02:58:26 2008 +0000
1.3 @@ -17,112 +17,313 @@
1.4 */
1.5
1.6 #include <iostream>
1.7 +#include <fstream>
1.8 +
1.9 +#include <lemon/list_graph.h>
1.10 +#include <lemon/smart_graph.h>
1.11 +#include <lemon/graph_reader.h>
1.12 +#include <lemon/dimacs.h>
1.13 +#include <lemon/time_measure.h>
1.14 +
1.15 +#include <lemon/cycle_canceling.h>
1.16 +#include <lemon/capacity_scaling.h>
1.17 +#include <lemon/cost_scaling.h>
1.18 +#include <lemon/network_simplex.h>
1.19 +
1.20 +#include <lemon/min_cost_flow.h>
1.21 +#include <lemon/min_cost_max_flow.h>
1.22 +
1.23 #include "test_tools.h"
1.24 -#include <lemon/list_graph.h>
1.25 -#include <lemon/ssp_min_cost_flow.h>
1.26 -//#include <path.h>
1.27 -//#include <maps.h>
1.28
1.29 using namespace lemon;
1.30
1.31 +// Checks the feasibility of a flow
1.32 +template < typename Graph, typename LowerMap, typename CapacityMap,
1.33 + typename SupplyMap, typename FlowMap >
1.34 +bool checkFlow( const Graph& gr,
1.35 + const LowerMap& lower, const CapacityMap& upper,
1.36 + const SupplyMap& supply, const FlowMap& flow )
1.37 +{
1.38 + GRAPH_TYPEDEFS(typename Graph);
1.39 + for (EdgeIt e(gr); e != INVALID; ++e)
1.40 + if (flow[e] < lower[e] || flow[e] > upper[e]) return false;
1.41
1.42 -bool passed = true;
1.43 -/*
1.44 -void check(bool rc, char *msg="") {
1.45 - passed = passed && rc;
1.46 - if(!rc) {
1.47 - std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
1.48 -
1.49 + for (NodeIt n(gr); n != INVALID; ++n) {
1.50 + typename SupplyMap::Value sum = 0;
1.51 + for (OutEdgeIt e(gr, n); e != INVALID; ++e)
1.52 + sum += flow[e];
1.53 + for (InEdgeIt e(gr, n); e != INVALID; ++e)
1.54 + sum -= flow[e];
1.55 + if (sum != supply[n]) return false;
1.56 + }
1.57
1.58 + return true;
1.59 +}
1.60 +
1.61 +// Checks the optimalitiy of a flow
1.62 +template < typename Graph, typename LowerMap, typename CapacityMap,
1.63 + typename CostMap, typename FlowMap, typename PotentialMap >
1.64 +bool checkOptimality( const Graph& gr, const LowerMap& lower,
1.65 + const CapacityMap& upper, const CostMap& cost,
1.66 + const FlowMap& flow, const PotentialMap& pi )
1.67 +{
1.68 + GRAPH_TYPEDEFS(typename Graph);
1.69 + // Checking the Complementary Slackness optimality condition
1.70 + bool opt = true;
1.71 + for (EdgeIt e(gr); e != INVALID; ++e) {
1.72 + typename CostMap::Value red_cost =
1.73 + cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
1.74 + opt = red_cost == 0 ||
1.75 + (red_cost > 0 && flow[e] == lower[e]) ||
1.76 + (red_cost < 0 && flow[e] == upper[e]);
1.77 + if (!opt) break;
1.78 + }
1.79 + return opt;
1.80 +}
1.81 +
1.82 +// Runs a minimum cost flow algorithm and checks the results
1.83 +template < typename MinCostFlowImpl, typename Graph,
1.84 + typename LowerMap, typename CapacityMap,
1.85 + typename CostMap, typename SupplyMap >
1.86 +void checkMcf( std::string test_id,
1.87 + const MinCostFlowImpl& mcf, const Graph& gr,
1.88 + const LowerMap& lower, const CapacityMap& upper,
1.89 + const CostMap& cost, const SupplyMap& supply,
1.90 + bool mcf_result, bool result,
1.91 + typename CostMap::Value total )
1.92 +{
1.93 + check(mcf_result == result, "Wrong result " + test_id);
1.94 + if (result) {
1.95 + check(checkFlow(gr, lower, upper, supply, mcf.flowMap()),
1.96 + "The flow is not feasible " + test_id);
1.97 + check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
1.98 + check(checkOptimality(gr, lower, upper, cost, mcf.flowMap(), mcf.potentialMap()),
1.99 + "Wrong potentials " + test_id);
1.100 }
1.101 }
1.102 -*/
1.103 -
1.104
1.105 int main()
1.106 {
1.107 - typedef ListGraph Graph;
1.108 - typedef Graph::Node Node;
1.109 - typedef Graph::Edge Edge;
1.110 + // Various tests on a small graph
1.111 + {
1.112 + typedef ListGraph Graph;
1.113 + GRAPH_TYPEDEFS(ListGraph);
1.114
1.115 - Graph graph;
1.116 + // Reading the test graph
1.117 + Graph gr;
1.118 + Graph::EdgeMap<int> c(gr), l1(gr), l2(gr), u(gr);
1.119 + Graph::NodeMap<int> s1(gr), s2(gr), s3(gr);
1.120 + Node v, w;
1.121
1.122 - //Ahuja könyv példája
1.123 + std::string fname;
1.124 + if(getenv("srcdir"))
1.125 + fname = std::string(getenv("srcdir"));
1.126 + else fname = ".";
1.127 + fname += "/test/min_cost_flow_test.lgf";
1.128
1.129 - Node s=graph.addNode();
1.130 - Node v1=graph.addNode();
1.131 - Node v2=graph.addNode();
1.132 - Node v3=graph.addNode();
1.133 - Node v4=graph.addNode();
1.134 - Node v5=graph.addNode();
1.135 - Node t=graph.addNode();
1.136 + std::ifstream input(fname.c_str());
1.137 + check(input, "Input file '" << fname << "' not found");
1.138 + GraphReader<Graph>(input, gr).
1.139 + readEdgeMap("cost", c).
1.140 + readEdgeMap("capacity", u).
1.141 + readEdgeMap("lower1", l1).
1.142 + readEdgeMap("lower2", l2).
1.143 + readNodeMap("supply1", s1).
1.144 + readNodeMap("supply2", s2).
1.145 + readNodeMap("supply3", s3).
1.146 + readNode("source", v).
1.147 + readNode("target", w).
1.148 + run();
1.149 + input.close();
1.150
1.151 - Edge s_v1=graph.addEdge(s, v1);
1.152 - Edge v1_v2=graph.addEdge(v1, v2);
1.153 - Edge s_v3=graph.addEdge(s, v3);
1.154 - Edge v2_v4=graph.addEdge(v2, v4);
1.155 - Edge v2_v5=graph.addEdge(v2, v5);
1.156 - Edge v3_v5=graph.addEdge(v3, v5);
1.157 - Edge v4_t=graph.addEdge(v4, t);
1.158 - Edge v5_t=graph.addEdge(v5, t);
1.159 -
1.160 + // Testing CapacityScaling (scaling enabled)
1.161 + {
1.162 + CapacityScaling<Graph> mcf1(gr,u,c,s1); checkMcf("#A1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0);
1.163 + CapacityScaling<Graph> mcf2(gr,u,c,s2); checkMcf("#A2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
1.164 + CapacityScaling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#A3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
1.165 + CapacityScaling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#A4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0);
1.166 + CapacityScaling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#A5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
1.167 + CapacityScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#A6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
1.168 + }
1.169 + // Testing CapacityScaling (scaling disabled)
1.170 + {
1.171 + CapacityScaling<Graph> mcf1(gr,u,c,s1); checkMcf("#B1",mcf1,gr,l1,u,c,s1,mcf1.run(false),true, 0);
1.172 + CapacityScaling<Graph> mcf2(gr,u,c,s2); checkMcf("#B2",mcf2,gr,l1,u,c,s2,mcf2.run(false),true, 5240);
1.173 + CapacityScaling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#B3",mcf3,gr,l1,u,c,s3,mcf3.run(false),true, 7620);
1.174 + CapacityScaling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#B4",mcf4,gr,l2,u,c,s1,mcf4.run(false),false, 0);
1.175 + CapacityScaling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#B5",mcf5,gr,l2,u,c,s2,mcf5.run(false),true, 5970);
1.176 + CapacityScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#B6",mcf6,gr,l2,u,c,s3,mcf6.run(false),true, 8010);
1.177 + }
1.178
1.179 - Graph::EdgeMap<int> length(graph);
1.180 + // Testing CostScaling
1.181 + {
1.182 + CostScaling<Graph> mcf1(gr,u,c,s1); checkMcf("#C1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0);
1.183 + CostScaling<Graph> mcf2(gr,u,c,s2); checkMcf("#C2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
1.184 + CostScaling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#C3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
1.185 + CostScaling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#C4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0);
1.186 + CostScaling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#C5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
1.187 + CostScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#C6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
1.188 + }
1.189
1.190 - length.set(s_v1, 6);
1.191 - length.set(v1_v2, 4);
1.192 - length.set(s_v3, 10);
1.193 - length.set(v2_v4, 5);
1.194 - length.set(v2_v5, 1);
1.195 - length.set(v3_v5, 4);
1.196 - length.set(v4_t, 8);
1.197 - length.set(v5_t, 8);
1.198 + // Testing NetworkSimplex (with the default pivot rule)
1.199 + {
1.200 + NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#D1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0);
1.201 + NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#D2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
1.202 + NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#D3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
1.203 + NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#D4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0);
1.204 + NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#D5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
1.205 + NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#D6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
1.206 + }
1.207 + // Testing NetworkSimplex (with FIRST_ELIGIBLE_PIVOT)
1.208 + {
1.209 + NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::FIRST_ELIGIBLE_PIVOT;
1.210 + NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#E1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0);
1.211 + NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#E2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
1.212 + NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#E3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
1.213 + NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#E4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0);
1.214 + NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#E5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
1.215 + NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#E6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
1.216 + }
1.217 + // Testing NetworkSimplex (with BEST_ELIGIBLE_PIVOT)
1.218 + {
1.219 + NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::BEST_ELIGIBLE_PIVOT;
1.220 + NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#F1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0);
1.221 + NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#F2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
1.222 + NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#F3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
1.223 + NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#F4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0);
1.224 + NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#F5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
1.225 + NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#F6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
1.226 + }
1.227 + // Testing NetworkSimplex (with BLOCK_SEARCH_PIVOT)
1.228 + {
1.229 + NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::BLOCK_SEARCH_PIVOT;
1.230 + NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#G1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0);
1.231 + NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#G2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
1.232 + NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#G3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
1.233 + NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#G4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0);
1.234 + NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#G5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
1.235 + NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#G6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
1.236 + }
1.237 + // Testing NetworkSimplex (with LIMITED_SEARCH_PIVOT)
1.238 + {
1.239 + NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::LIMITED_SEARCH_PIVOT;
1.240 + NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#H1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0);
1.241 + NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#H2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
1.242 + NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#H3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
1.243 + NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#H4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0);
1.244 + NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#H5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
1.245 + NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#H6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
1.246 + }
1.247 + // Testing NetworkSimplex (with CANDIDATE_LIST_PIVOT)
1.248 + {
1.249 + NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::CANDIDATE_LIST_PIVOT;
1.250 + NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#I1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0);
1.251 + NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#I2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
1.252 + NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#I3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
1.253 + NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#I4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0);
1.254 + NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#I5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
1.255 + NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#I6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
1.256 + }
1.257
1.258 - Graph::EdgeMap<int> capacity(graph);
1.259 + // Testing CycleCanceling (with BellmanFord)
1.260 + {
1.261 + CycleCanceling<Graph> mcf1(gr,u,c,s1); checkMcf("#J1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0);
1.262 + CycleCanceling<Graph> mcf2(gr,u,c,s2); checkMcf("#J2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
1.263 + CycleCanceling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#J3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
1.264 + CycleCanceling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#J4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0);
1.265 + CycleCanceling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#J5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
1.266 + CycleCanceling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#J6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
1.267 + }
1.268 + // Testing CycleCanceling (with MinMeanCycle)
1.269 + {
1.270 + CycleCanceling<Graph> mcf1(gr,u,c,s1); checkMcf("#K1",mcf1,gr,l1,u,c,s1,mcf1.run(true),true, 0);
1.271 + CycleCanceling<Graph> mcf2(gr,u,c,s2); checkMcf("#K2",mcf2,gr,l1,u,c,s2,mcf2.run(true),true, 5240);
1.272 + CycleCanceling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#K3",mcf3,gr,l1,u,c,s3,mcf3.run(true),true, 7620);
1.273 + CycleCanceling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#K4",mcf4,gr,l2,u,c,s1,mcf4.run(true),false, 0);
1.274 + CycleCanceling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#K5",mcf5,gr,l2,u,c,s2,mcf5.run(true),true, 5970);
1.275 + CycleCanceling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#K6",mcf6,gr,l2,u,c,s3,mcf6.run(true),true, 8010);
1.276 + }
1.277
1.278 - capacity.set(s_v1, 2);
1.279 - capacity.set(v1_v2, 2);
1.280 - capacity.set(s_v3, 1);
1.281 - capacity.set(v2_v4, 1);
1.282 - capacity.set(v2_v5, 1);
1.283 - capacity.set(v3_v5, 1);
1.284 - capacity.set(v4_t, 1);
1.285 - capacity.set(v5_t, 2);
1.286 + // Testing MinCostFlow
1.287 + {
1.288 + MinCostFlow<Graph> mcf1(gr,u,c,s1); checkMcf("#L1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0);
1.289 + MinCostFlow<Graph> mcf2(gr,u,c,s2); checkMcf("#L2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
1.290 + MinCostFlow<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#L3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
1.291 + MinCostFlow<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#L4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0);
1.292 + MinCostFlow<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#L5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
1.293 + MinCostFlow<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#L6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
1.294 + }
1.295
1.296 - // ConstMap<Edge, int> const1map(1);
1.297 - std::cout << "Mincostflows algorithm test..." << std::endl;
1.298 + // Testing MinCostMaxFlow
1.299 + {
1.300 + MinCostMaxFlow<Graph> mcmf(gr,u,c,v,w);
1.301 + mcmf.run();
1.302 + checkMcf("#M1",mcmf,gr,l1,u,c,s3,true,true,7620);
1.303 + }
1.304 + }
1.305
1.306 - SspMinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.307 - surb_test(graph, length, capacity, s, t);
1.308 + // Benchmark test on a DIMACS network
1.309 + {
1.310 + typedef SmartGraph Graph;
1.311 + GRAPH_TYPEDEFS(SmartGraph);
1.312
1.313 - int k=1;
1.314 + // Reading the test graph
1.315 + Graph graph;
1.316 + Graph::EdgeMap<int> lower(graph), capacity(graph), cost(graph);
1.317 + Graph::NodeMap<int> supply(graph);
1.318
1.319 - surb_test.augment();
1.320 - check( surb_test.flowValue() == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
1.321 + std::string fname;
1.322 + if(getenv("srcdir"))
1.323 + fname = std::string(getenv("srcdir"));
1.324 + else fname = ".";
1.325 + fname += "/test/min_cost_flow_test.net";
1.326
1.327 - check( surb_test.run(k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
1.328 + std::ifstream input(fname.c_str());
1.329 + check(input, "Input file '" << fname << "' not found");
1.330 + readDimacs(input, graph, lower, capacity, cost, supply);
1.331 + input.close();
1.332
1.333 - check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
1.334 -
1.335 - k=2;
1.336 -
1.337 - check( surb_test.run(k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
1.338 + // NetworkSimplex
1.339 + {
1.340 + Timer t;
1.341 + NetworkSimplex<Graph> mcf(graph, lower, capacity, cost, supply);
1.342 + bool res = mcf.run();
1.343 + t.stop();
1.344 + checkMcf("#T3", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
1.345 + std::cout << "NetworkSimplex";
1.346 + std::cout << std::endl << t << std::endl;
1.347 + }
1.348 + // CapacityScaling
1.349 + {
1.350 + Timer t;
1.351 + CapacityScaling<Graph> mcf(graph, lower, capacity, cost, supply);
1.352 + bool res = mcf.run();
1.353 + t.stop();
1.354 + checkMcf("#T1", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
1.355 + std::cout << "CapacityScaling";
1.356 + std::cout << std::endl << t << std::endl;
1.357 + }
1.358 + // CostScaling
1.359 + {
1.360 + Timer t;
1.361 + CostScaling<Graph> mcf(graph, lower, capacity, cost, supply);
1.362 + bool res = mcf.run();
1.363 + t.stop();
1.364 + checkMcf("#T2", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
1.365 + std::cout << "CostScaling";
1.366 + std::cout << std::endl << t << std::endl;
1.367 + }
1.368 + // CycleCanceling
1.369 + {
1.370 + Timer t;
1.371 + CycleCanceling<Graph> mcf(graph, lower, capacity, cost, supply);
1.372 + bool res = mcf.run();
1.373 + t.stop();
1.374 + checkMcf("#T4", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
1.375 + std::cout << "CycleCanceling";
1.376 + std::cout << std::endl << t << std::endl;
1.377 + }
1.378 + }
1.379
1.380 - check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
1.381 -
1.382 - surb_test.augment();
1.383 - surb_test.augment();
1.384 - surb_test.augment();
1.385 - k=4;
1.386 -
1.387 - check( surb_test.run(k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
1.388 -
1.389 - check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
1.390 -
1.391 -
1.392 - std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
1.393 - << std::endl;
1.394 -
1.395 - return passed ? 0 : 1;
1.396 -
1.397 + return 0;
1.398 }
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/test/min_cost_flow_test.lgf Thu Feb 28 02:58:26 2008 +0000
2.3 @@ -0,0 +1,44 @@
2.4 +@nodeset
2.5 +label supply1 supply2 supply3
2.6 +1 0 20 27
2.7 +2 0 -4 0
2.8 +3 0 0 0
2.9 +4 0 0 0
2.10 +5 0 9 0
2.11 +6 0 -6 0
2.12 +7 0 0 0
2.13 +8 0 0 0
2.14 +9 0 3 0
2.15 +10 0 -2 0
2.16 +11 0 0 0
2.17 +12 0 -20 -27
2.18 +
2.19 +@edgeset
2.20 + cost capacity lower1 lower2
2.21 +1 2 70 11 0 8
2.22 +1 3 150 3 0 1
2.23 +1 4 80 15 0 2
2.24 +2 8 80 12 0 0
2.25 +3 5 140 5 0 3
2.26 +4 6 60 10 0 1
2.27 +4 7 80 2 0 0
2.28 +4 8 110 3 0 0
2.29 +5 7 60 14 0 0
2.30 +5 11 120 12 0 0
2.31 +6 3 0 3 0 0
2.32 +6 9 140 4 0 0
2.33 +6 10 90 8 0 0
2.34 +7 1 30 5 0 0
2.35 +8 12 60 16 0 4
2.36 +9 12 50 6 0 0
2.37 +10 12 70 13 0 5
2.38 +10 2 100 7 0 0
2.39 +10 7 60 10 0 0
2.40 +11 10 20 14 0 6
2.41 +12 11 30 10 0 0
2.42 +
2.43 +@nodes
2.44 +source 1
2.45 +target 12
2.46 +
2.47 +@end
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/test/min_cost_flow_test.net Thu Feb 28 02:58:26 2008 +0000
3.3 @@ -0,0 +1,1531 @@
3.4 +c NETGEN flow network generator (C version)
3.5 +c Problem 1 input parameters
3.6 +c ---------------------------
3.7 +c Random seed: 13502460
3.8 +c Number of nodes: 200
3.9 +c Source nodes: 100
3.10 +c Sink nodes: 100
3.11 +c Number of arcs: 1300
3.12 +c Minimum arc cost: 1
3.13 +c Maximum arc cost: 10000
3.14 +c Total supply: 100000
3.15 +c Transshipment -
3.16 +c Sources: 0
3.17 +c Sinks: 0
3.18 +c Skeleton arcs -
3.19 +c With max cost: 0%
3.20 +c Capacitated: 0%
3.21 +c Minimum arc capacity: 0
3.22 +c Maximum arc capacity: 0
3.23 +c
3.24 +c *** Minimum cost flow ***
3.25 +c
3.26 +p min 200 1308
3.27 +n 1 286
3.28 +n 2 671
3.29 +n 3 605
3.30 +n 4 195
3.31 +n 5 1287
3.32 +n 6 497
3.33 +n 7 149
3.34 +n 8 660
3.35 +n 9 676
3.36 +n 10 1338
3.37 +n 11 222
3.38 +n 12 738
3.39 +n 13 1819
3.40 +n 14 1857
3.41 +n 15 1749
3.42 +n 16 1479
3.43 +n 17 154
3.44 +n 18 1897
3.45 +n 19 707
3.46 +n 20 367
3.47 +n 21 917
3.48 +n 22 410
3.49 +n 23 1000
3.50 +n 24 770
3.51 +n 25 1122
3.52 +n 26 1895
3.53 +n 27 1501
3.54 +n 28 514
3.55 +n 29 2227
3.56 +n 30 913
3.57 +n 31 947
3.58 +n 32 2260
3.59 +n 33 996
3.60 +n 34 986
3.61 +n 35 125
3.62 +n 36 362
3.63 +n 37 706
3.64 +n 38 1262
3.65 +n 39 389
3.66 +n 40 1410
3.67 +n 41 758
3.68 +n 42 2189
3.69 +n 43 531
3.70 +n 44 527
3.71 +n 45 2028
3.72 +n 46 1710
3.73 +n 47 1196
3.74 +n 48 832
3.75 +n 49 73
3.76 +n 50 1269
3.77 +n 51 1485
3.78 +n 52 1174
3.79 +n 53 1325
3.80 +n 54 2136
3.81 +n 55 852
3.82 +n 56 301
3.83 +n 57 707
3.84 +n 58 807
3.85 +n 59 1242
3.86 +n 60 1739
3.87 +n 61 1225
3.88 +n 62 94
3.89 +n 63 989
3.90 +n 64 1641
3.91 +n 65 805
3.92 +n 66 236
3.93 +n 67 1520
3.94 +n 68 1421
3.95 +n 69 936
3.96 +n 70 100
3.97 +n 71 952
3.98 +n 72 501
3.99 +n 73 1858
3.100 +n 74 1563
3.101 +n 75 186
3.102 +n 76 1307
3.103 +n 77 626
3.104 +n 78 1032
3.105 +n 79 939
3.106 +n 80 1159
3.107 +n 81 904
3.108 +n 82 1332
3.109 +n 83 1280
3.110 +n 84 2080
3.111 +n 85 1260
3.112 +n 86 512
3.113 +n 87 191
3.114 +n 88 309
3.115 +n 89 1053
3.116 +n 90 1070
3.117 +n 91 656
3.118 +n 92 1155
3.119 +n 93 493
3.120 +n 94 1135
3.121 +n 95 1199
3.122 +n 96 1914
3.123 +n 97 677
3.124 +n 98 192
3.125 +n 99 914
3.126 +n 100 1638
3.127 +n 101 -1827
3.128 +n 102 -1234
3.129 +n 103 -903
3.130 +n 104 -1166
3.131 +n 105 -2594
3.132 +n 106 -10
3.133 +n 107 -710
3.134 +n 108 -1074
3.135 +n 109 -686
3.136 +n 110 -147
3.137 +n 111 -955
3.138 +n 112 -535
3.139 +n 113 -1118
3.140 +n 114 -381
3.141 +n 115 -297
3.142 +n 116 -599
3.143 +n 117 -1534
3.144 +n 118 -160
3.145 +n 119 -114
3.146 +n 120 -1633
3.147 +n 121 -195
3.148 +n 122 -689
3.149 +n 123 -62
3.150 +n 124 -111
3.151 +n 125 -869
3.152 +n 126 -84
3.153 +n 127 -2074
3.154 +n 128 -31
3.155 +n 129 -1851
3.156 +n 130 -1720
3.157 +n 131 -754
3.158 +n 132 -2739
3.159 +n 133 -155
3.160 +n 134 -3154
3.161 +n 135 -572
3.162 +n 136 -2372
3.163 +n 137 -321
3.164 +n 138 -86
3.165 +n 139 -1687
3.166 +n 140 -1346
3.167 +n 141 -2465
3.168 +n 142 -388
3.169 +n 143 -1861
3.170 +n 144 -971
3.171 +n 145 -628
3.172 +n 146 -187
3.173 +n 147 -26
3.174 +n 148 -1975
3.175 +n 149 -2424
3.176 +n 150 -574
3.177 +n 151 -163
3.178 +n 152 -1126
3.179 +n 153 -2865
3.180 +n 154 -233
3.181 +n 155 -2837
3.182 +n 156 -1209
3.183 +n 157 -2017
3.184 +n 158 -2228
3.185 +n 159 -740
3.186 +n 160 -290
3.187 +n 161 -9
3.188 +n 162 -151
3.189 +n 163 -2922
3.190 +n 164 -1405
3.191 +n 165 -374
3.192 +n 166 -880
3.193 +n 167 -47
3.194 +n 168 -865
3.195 +n 169 -728
3.196 +n 170 -103
3.197 +n 171 -616
3.198 +n 172 -318
3.199 +n 173 -2548
3.200 +n 174 -353
3.201 +n 175 -937
3.202 +n 176 -1012
3.203 +n 177 -504
3.204 +n 178 -39
3.205 +n 179 -1897
3.206 +n 180 -1130
3.207 +n 181 -1971
3.208 +n 182 -1941
3.209 +n 183 -1758
3.210 +n 184 -2284
3.211 +n 185 -998
3.212 +n 186 -875
3.213 +n 187 -1083
3.214 +n 188 -257
3.215 +n 189 -2394
3.216 +n 190 -351
3.217 +n 191 -578
3.218 +n 192 -53
3.219 +n 193 -223
3.220 +n 194 -869
3.221 +n 195 -1088
3.222 +n 196 -96
3.223 +n 197 -755
3.224 +n 198 -1577
3.225 +n 199 -131
3.226 +n 200 -124
3.227 +a 1 102 0 100000 8550
3.228 +a 1 171 0 100000 7415
3.229 +a 1 101 0 100000 7178
3.230 +a 1 165 0 100000 4494
3.231 +a 1 151 0 100000 6289
3.232 +a 1 187 0 100000 1281
3.233 +a 1 189 0 100000 6859
3.234 +a 1 166 0 100000 8963
3.235 +a 1 182 0 100000 1704
3.236 +a 1 112 0 100000 6045
3.237 +a 1 154 0 100000 5938
3.238 +a 1 160 0 100000 8099
3.239 +a 1 186 0 100000 3667
3.240 +a 1 126 0 100000 6885
3.241 +a 1 132 0 100000 1207
3.242 +a 1 197 0 100000 7041
3.243 +a 2 181 0 100000 8581
3.244 +a 2 155 0 100000 4218
3.245 +a 2 152 0 100000 9984
3.246 +a 2 166 0 100000 7839
3.247 +a 2 184 0 100000 6509
3.248 +a 2 164 0 100000 4037
3.249 +a 2 167 0 100000 3308
3.250 +a 2 180 0 100000 3719
3.251 +a 2 157 0 100000 2558
3.252 +a 2 120 0 100000 1380
3.253 +a 2 159 0 100000 452
3.254 +a 2 119 0 100000 1576
3.255 +a 2 111 0 100000 9029
3.256 +a 2 146 0 100000 3919
3.257 +a 2 145 0 100000 2355
3.258 +a 3 166 0 100000 9197
3.259 +a 3 180 0 100000 5974
3.260 +a 3 106 0 100000 5746
3.261 +a 3 119 0 100000 7933
3.262 +a 3 145 0 100000 8276
3.263 +a 3 120 0 100000 3279
3.264 +a 3 103 0 100000 5734
3.265 +a 3 130 0 100000 5935
3.266 +a 3 157 0 100000 5403
3.267 +a 3 175 0 100000 730
3.268 +a 4 119 0 100000 4678
3.269 +a 4 134 0 100000 752
3.270 +a 4 199 0 100000 6613
3.271 +a 4 104 0 100000 5132
3.272 +a 4 158 0 100000 6946
3.273 +a 4 139 0 100000 5430
3.274 +a 4 113 0 100000 5236
3.275 +a 4 174 0 100000 6554
3.276 +a 4 179 0 100000 4745
3.277 +a 4 103 0 100000 3365
3.278 +a 4 144 0 100000 2841
3.279 +a 4 169 0 100000 743
3.280 +a 4 130 0 100000 1917
3.281 +a 4 197 0 100000 5331
3.282 +a 4 175 0 100000 2557
3.283 +a 5 158 0 100000 8388
3.284 +a 5 102 0 100000 3231
3.285 +a 5 155 0 100000 4091
3.286 +a 5 125 0 100000 7576
3.287 +a 6 106 0 100000 1759
3.288 +a 6 120 0 100000 3707
3.289 +a 6 192 0 100000 2581
3.290 +a 6 176 0 100000 8376
3.291 +a 6 121 0 100000 5426
3.292 +a 6 102 0 100000 895
3.293 +a 6 167 0 100000 8750
3.294 +a 6 152 0 100000 454
3.295 +a 6 124 0 100000 2864
3.296 +a 6 108 0 100000 3204
3.297 +a 6 184 0 100000 8370
3.298 +a 6 195 0 100000 2914
3.299 +a 6 149 0 100000 9326
3.300 +a 6 140 0 100000 7174
3.301 +a 6 169 0 100000 9346
3.302 +a 6 127 0 100000 6898
3.303 +a 6 134 0 100000 8782
3.304 +a 6 173 0 100000 9386
3.305 +a 6 183 0 100000 9188
3.306 +a 7 198 0 100000 1118
3.307 +a 7 102 0 100000 6098
3.308 +a 7 170 0 100000 5021
3.309 +a 7 199 0 100000 6752
3.310 +a 8 180 0 100000 1271
3.311 +a 8 129 0 100000 4668
3.312 +a 8 170 0 100000 7417
3.313 +a 8 177 0 100000 3773
3.314 +a 8 106 0 100000 7995
3.315 +a 8 134 0 100000 4729
3.316 +a 8 183 0 100000 2999
3.317 +a 8 159 0 100000 7149
3.318 +a 8 164 0 100000 4594
3.319 +a 9 140 0 100000 7422
3.320 +a 9 159 0 100000 1784
3.321 +a 9 182 0 100000 7713
3.322 +a 9 193 0 100000 194
3.323 +a 9 125 0 100000 2095
3.324 +a 9 198 0 100000 7925
3.325 +a 9 169 0 100000 2421
3.326 +a 9 195 0 100000 9863
3.327 +a 9 146 0 100000 7451
3.328 +a 9 126 0 100000 858
3.329 +a 9 197 0 100000 4286
3.330 +a 9 192 0 100000 9168
3.331 +a 9 109 0 100000 6058
3.332 +a 9 106 0 100000 9915
3.333 +a 9 138 0 100000 7024
3.334 +a 9 123 0 100000 3551
3.335 +a 9 163 0 100000 5507
3.336 +a 9 104 0 100000 5826
3.337 +a 9 139 0 100000 787
3.338 +a 10 143 0 100000 6434
3.339 +a 10 175 0 100000 5810
3.340 +a 10 165 0 100000 612
3.341 +a 10 126 0 100000 6095
3.342 +a 10 101 0 100000 1609
3.343 +a 10 153 0 100000 4862
3.344 +a 10 149 0 100000 1918
3.345 +a 10 140 0 100000 782
3.346 +a 10 145 0 100000 9166
3.347 +a 10 141 0 100000 846
3.348 +a 10 176 0 100000 2056
3.349 +a 10 113 0 100000 4056
3.350 +a 11 124 0 100000 4877
3.351 +a 11 176 0 100000 683
3.352 +a 11 177 0 100000 4842
3.353 +a 11 107 0 100000 5609
3.354 +a 11 139 0 100000 7808
3.355 +a 11 188 0 100000 2218
3.356 +a 11 134 0 100000 9467
3.357 +a 11 169 0 100000 5894
3.358 +a 11 109 0 100000 8396
3.359 +a 11 165 0 100000 9248
3.360 +a 11 149 0 100000 889
3.361 +a 11 175 0 100000 9202
3.362 +a 11 130 0 100000 4593
3.363 +a 11 152 0 100000 1837
3.364 +a 11 145 0 100000 9058
3.365 +a 11 138 0 100000 3582
3.366 +a 11 122 0 100000 7516
3.367 +a 11 146 0 100000 719
3.368 +a 11 112 0 100000 9082
3.369 +a 11 160 0 100000 6105
3.370 +a 11 128 0 100000 4323
3.371 +a 11 194 0 100000 8202
3.372 +a 11 168 0 100000 8736
3.373 +a 11 102 0 100000 8382
3.374 +a 11 101 0 100000 9503
3.375 +a 12 117 0 100000 3034
3.376 +a 12 172 0 100000 7033
3.377 +a 12 183 0 100000 7235
3.378 +a 12 105 0 100000 2219
3.379 +a 12 163 0 100000 9998
3.380 +a 12 198 0 100000 6881
3.381 +a 12 114 0 100000 8613
3.382 +a 12 174 0 100000 4456
3.383 +a 12 147 0 100000 4762
3.384 +a 12 101 0 100000 2794
3.385 +a 12 120 0 100000 5705
3.386 +a 12 144 0 100000 9694
3.387 +a 12 191 0 100000 1124
3.388 +a 12 161 0 100000 8140
3.389 +a 12 185 0 100000 8678
3.390 +a 13 163 0 100000 854
3.391 +a 13 141 0 100000 3211
3.392 +a 13 122 0 100000 5557
3.393 +a 13 169 0 100000 4912
3.394 +a 13 151 0 100000 9351
3.395 +a 13 162 0 100000 5018
3.396 +a 13 131 0 100000 6210
3.397 +a 13 167 0 100000 1858
3.398 +a 13 133 0 100000 2148
3.399 +a 13 175 0 100000 4424
3.400 +a 13 112 0 100000 8310
3.401 +a 13 179 0 100000 7491
3.402 +a 13 142 0 100000 3439
3.403 +a 13 199 0 100000 7269
3.404 +a 14 148 0 100000 8480
3.405 +a 14 163 0 100000 2274
3.406 +a 14 143 0 100000 2854
3.407 +a 14 140 0 100000 2177
3.408 +a 14 161 0 100000 5688
3.409 +a 14 146 0 100000 7526
3.410 +a 14 118 0 100000 2712
3.411 +a 14 169 0 100000 552
3.412 +a 14 187 0 100000 9060
3.413 +a 14 166 0 100000 248
3.414 +a 14 155 0 100000 5144
3.415 +a 14 186 0 100000 3864
3.416 +a 14 111 0 100000 6005
3.417 +a 14 193 0 100000 4245
3.418 +a 14 120 0 100000 8330
3.419 +a 14 152 0 100000 7421
3.420 +a 14 126 0 100000 142
3.421 +a 14 165 0 100000 3420
3.422 +a 14 199 0 100000 6522
3.423 +a 14 153 0 100000 5961
3.424 +a 14 130 0 100000 5736
3.425 +a 15 186 0 100000 4114
3.426 +a 15 148 0 100000 9833
3.427 +a 15 187 0 100000 8173
3.428 +a 15 134 0 100000 2495
3.429 +a 15 115 0 100000 4604
3.430 +a 15 146 0 100000 2949
3.431 +a 15 189 0 100000 9903
3.432 +a 15 138 0 100000 8139
3.433 +a 15 184 0 100000 7591
3.434 +a 15 110 0 100000 5914
3.435 +a 15 165 0 100000 5669
3.436 +a 15 103 0 100000 3590
3.437 +a 16 130 0 100000 9385
3.438 +a 16 176 0 100000 9727
3.439 +a 16 199 0 100000 9266
3.440 +a 16 198 0 100000 9129
3.441 +a 16 194 0 100000 6915
3.442 +a 16 155 0 100000 5789
3.443 +a 16 190 0 100000 1965
3.444 +a 16 135 0 100000 7619
3.445 +a 16 195 0 100000 6171
3.446 +a 16 131 0 100000 2529
3.447 +a 16 171 0 100000 5969
3.448 +a 17 144 0 100000 9423
3.449 +a 17 157 0 100000 9156
3.450 +a 17 176 0 100000 2918
3.451 +a 17 158 0 100000 7903
3.452 +a 17 129 0 100000 7213
3.453 +a 17 160 0 100000 4253
3.454 +a 17 156 0 100000 8909
3.455 +a 17 182 0 100000 6735
3.456 +a 17 139 0 100000 9549
3.457 +a 17 162 0 100000 7045
3.458 +a 17 138 0 100000 2554
3.459 +a 17 143 0 100000 4064
3.460 +a 17 173 0 100000 5104
3.461 +a 17 166 0 100000 4292
3.462 +a 17 105 0 100000 1842
3.463 +a 18 158 0 100000 9866
3.464 +a 18 197 0 100000 7354
3.465 +a 18 184 0 100000 6383
3.466 +a 18 161 0 100000 1002
3.467 +a 18 199 0 100000 2172
3.468 +a 18 155 0 100000 7750
3.469 +a 19 158 0 100000 7165
3.470 +a 19 190 0 100000 5440
3.471 +a 19 159 0 100000 3536
3.472 +a 19 117 0 100000 3537
3.473 +a 19 109 0 100000 3991
3.474 +a 19 140 0 100000 3108
3.475 +a 19 128 0 100000 7287
3.476 +a 20 159 0 100000 1035
3.477 +a 20 185 0 100000 535
3.478 +a 20 148 0 100000 9177
3.479 +a 20 171 0 100000 2425
3.480 +a 20 144 0 100000 7990
3.481 +a 20 186 0 100000 2564
3.482 +a 20 187 0 100000 2509
3.483 +a 20 172 0 100000 4673
3.484 +a 20 110 0 100000 6121
3.485 +a 20 149 0 100000 8447
3.486 +a 20 101 0 100000 6134
3.487 +a 20 157 0 100000 8659
3.488 +a 20 178 0 100000 6884
3.489 +a 20 135 0 100000 1567
3.490 +a 20 106 0 100000 8015
3.491 +a 20 128 0 100000 4746
3.492 +a 20 121 0 100000 8069
3.493 +a 20 194 0 100000 1385
3.494 +a 21 111 0 100000 4392
3.495 +a 21 105 0 100000 9561
3.496 +a 21 134 0 100000 1551
3.497 +a 21 108 0 100000 5449
3.498 +a 21 126 0 100000 103
3.499 +a 21 103 0 100000 4043
3.500 +a 21 142 0 100000 8749
3.501 +a 21 183 0 100000 4714
3.502 +a 21 172 0 100000 4855
3.503 +a 21 123 0 100000 9136
3.504 +a 21 117 0 100000 9771
3.505 +a 21 114 0 100000 8472
3.506 +a 21 101 0 100000 299
3.507 +a 21 113 0 100000 1446
3.508 +a 21 165 0 100000 4952
3.509 +a 21 163 0 100000 4478
3.510 +a 21 153 0 100000 5954
3.511 +a 21 170 0 100000 279
3.512 +a 21 129 0 100000 6788
3.513 +a 21 152 0 100000 578
3.514 +a 21 198 0 100000 2459
3.515 +a 22 152 0 100000 8855
3.516 +a 22 142 0 100000 829
3.517 +a 22 176 0 100000 6797
3.518 +a 22 126 0 100000 2513
3.519 +a 22 188 0 100000 7332
3.520 +a 22 177 0 100000 3842
3.521 +a 22 186 0 100000 473
3.522 +a 22 127 0 100000 8075
3.523 +a 22 171 0 100000 924
3.524 +a 22 156 0 100000 4585
3.525 +a 22 130 0 100000 9616
3.526 +a 22 112 0 100000 2078
3.527 +a 22 155 0 100000 79
3.528 +a 23 193 0 100000 7025
3.529 +a 23 129 0 100000 4876
3.530 +a 23 114 0 100000 5073
3.531 +a 23 126 0 100000 1821
3.532 +a 23 199 0 100000 7200
3.533 +a 23 128 0 100000 2940
3.534 +a 23 181 0 100000 9911
3.535 +a 23 155 0 100000 3948
3.536 +a 23 197 0 100000 9522
3.537 +a 23 151 0 100000 5662
3.538 +a 23 111 0 100000 6135
3.539 +a 23 175 0 100000 5329
3.540 +a 23 102 0 100000 8364
3.541 +a 23 139 0 100000 6544
3.542 +a 23 104 0 100000 283
3.543 +a 23 156 0 100000 8369
3.544 +a 23 108 0 100000 3491
3.545 +a 23 110 0 100000 6481
3.546 +a 23 124 0 100000 946
3.547 +a 23 131 0 100000 9861
3.548 +a 23 141 0 100000 4976
3.549 +a 24 183 0 100000 2975
3.550 +a 24 149 0 100000 2843
3.551 +a 24 117 0 100000 3594
3.552 +a 24 166 0 100000 1261
3.553 +a 24 184 0 100000 2514
3.554 +a 24 153 0 100000 2271
3.555 +a 24 114 0 100000 7316
3.556 +a 24 198 0 100000 6092
3.557 +a 24 105 0 100000 7868
3.558 +a 24 139 0 100000 8309
3.559 +a 24 174 0 100000 5131
3.560 +a 24 197 0 100000 1045
3.561 +a 24 195 0 100000 845
3.562 +a 24 176 0 100000 5820
3.563 +a 24 181 0 100000 6085
3.564 +a 24 101 0 100000 7898
3.565 +a 25 152 0 100000 4264
3.566 +a 25 140 0 100000 5481
3.567 +a 25 126 0 100000 8929
3.568 +a 25 196 0 100000 3220
3.569 +a 25 165 0 100000 5562
3.570 +a 25 151 0 100000 5705
3.571 +a 25 112 0 100000 830
3.572 +a 25 191 0 100000 5730
3.573 +a 25 178 0 100000 7717
3.574 +a 25 167 0 100000 4126
3.575 +a 25 163 0 100000 3714
3.576 +a 25 185 0 100000 225
3.577 +a 25 129 0 100000 3369
3.578 +a 25 123 0 100000 3660
3.579 +a 25 177 0 100000 2367
3.580 +a 25 116 0 100000 2469
3.581 +a 25 139 0 100000 9779
3.582 +a 25 125 0 100000 1489
3.583 +a 26 139 0 100000 6155
3.584 +a 26 182 0 100000 7651
3.585 +a 26 189 0 100000 707
3.586 +a 26 190 0 100000 7671
3.587 +a 26 180 0 100000 1178
3.588 +a 26 124 0 100000 6625
3.589 +a 26 184 0 100000 1171
3.590 +a 26 154 0 100000 7505
3.591 +a 27 143 0 100000 423
3.592 +a 27 117 0 100000 5685
3.593 +a 27 180 0 100000 6991
3.594 +a 27 129 0 100000 4564
3.595 +a 27 193 0 100000 2539
3.596 +a 27 173 0 100000 7896
3.597 +a 27 195 0 100000 3690
3.598 +a 27 142 0 100000 8270
3.599 +a 27 131 0 100000 2276
3.600 +a 27 153 0 100000 2689
3.601 +a 28 188 0 100000 8418
3.602 +a 28 111 0 100000 1308
3.603 +a 28 158 0 100000 709
3.604 +a 28 161 0 100000 1968
3.605 +a 28 130 0 100000 6317
3.606 +a 28 168 0 100000 8008
3.607 +a 28 160 0 100000 879
3.608 +a 29 101 0 100000 767
3.609 +a 29 157 0 100000 6845
3.610 +a 29 149 0 100000 9061
3.611 +a 29 112 0 100000 281
3.612 +a 29 164 0 100000 5274
3.613 +a 29 199 0 100000 8463
3.614 +a 29 180 0 100000 9707
3.615 +a 29 165 0 100000 7565
3.616 +a 29 178 0 100000 8621
3.617 +a 29 118 0 100000 7437
3.618 +a 29 169 0 100000 9960
3.619 +a 29 125 0 100000 51
3.620 +a 29 150 0 100000 474
3.621 +a 29 160 0 100000 2568
3.622 +a 29 141 0 100000 4219
3.623 +a 29 187 0 100000 731
3.624 +a 29 158 0 100000 2476
3.625 +a 29 144 0 100000 7245
3.626 +a 29 129 0 100000 7548
3.627 +a 29 190 0 100000 3895
3.628 +a 30 185 0 100000 1822
3.629 +a 30 134 0 100000 9893
3.630 +a 30 122 0 100000 1153
3.631 +a 31 159 0 100000 7778
3.632 +a 31 105 0 100000 4967
3.633 +a 31 153 0 100000 3541
3.634 +a 31 160 0 100000 2677
3.635 +a 31 111 0 100000 3222
3.636 +a 31 136 0 100000 3269
3.637 +a 31 125 0 100000 9717
3.638 +a 31 181 0 100000 2325
3.639 +a 31 119 0 100000 8407
3.640 +a 31 127 0 100000 890
3.641 +a 31 124 0 100000 9168
3.642 +a 31 104 0 100000 6356
3.643 +a 31 179 0 100000 9162
3.644 +a 31 167 0 100000 383
3.645 +a 31 112 0 100000 1886
3.646 +a 31 120 0 100000 5326
3.647 +a 31 114 0 100000 3436
3.648 +a 32 173 0 100000 6787
3.649 +a 32 145 0 100000 1839
3.650 +a 32 113 0 100000 3758
3.651 +a 32 182 0 100000 4761
3.652 +a 32 119 0 100000 9817
3.653 +a 32 196 0 100000 9686
3.654 +a 32 129 0 100000 716
3.655 +a 32 116 0 100000 5747
3.656 +a 32 178 0 100000 1074
3.657 +a 32 167 0 100000 8680
3.658 +a 33 194 0 100000 4684
3.659 +a 33 127 0 100000 8502
3.660 +a 33 174 0 100000 7338
3.661 +a 33 175 0 100000 6420
3.662 +a 33 138 0 100000 9551
3.663 +a 33 115 0 100000 4239
3.664 +a 33 107 0 100000 6930
3.665 +a 33 104 0 100000 2172
3.666 +a 33 190 0 100000 8714
3.667 +a 33 151 0 100000 4263
3.668 +a 33 182 0 100000 2765
3.669 +a 33 161 0 100000 5954
3.670 +a 33 173 0 100000 274
3.671 +a 33 154 0 100000 9371
3.672 +a 33 156 0 100000 75
3.673 +a 33 114 0 100000 8067
3.674 +a 33 153 0 100000 2563
3.675 +a 33 169 0 100000 6915
3.676 +a 33 164 0 100000 8577
3.677 +a 33 110 0 100000 3079
3.678 +a 34 139 0 100000 3061
3.679 +a 34 183 0 100000 7251
3.680 +a 34 178 0 100000 8023
3.681 +a 34 163 0 100000 2993
3.682 +a 34 109 0 100000 9045
3.683 +a 34 172 0 100000 5404
3.684 +a 34 112 0 100000 7608
3.685 +a 34 196 0 100000 5449
3.686 +a 34 148 0 100000 2226
3.687 +a 34 142 0 100000 8808
3.688 +a 34 174 0 100000 9183
3.689 +a 34 123 0 100000 9092
3.690 +a 34 145 0 100000 1530
3.691 +a 34 162 0 100000 1288
3.692 +a 34 166 0 100000 388
3.693 +a 34 133 0 100000 1153
3.694 +a 34 115 0 100000 2210
3.695 +a 34 151 0 100000 979
3.696 +a 34 171 0 100000 1136
3.697 +a 34 137 0 100000 4830
3.698 +a 35 143 0 100000 8167
3.699 +a 35 123 0 100000 2401
3.700 +a 35 112 0 100000 4052
3.701 +a 35 149 0 100000 721
3.702 +a 35 132 0 100000 9237
3.703 +a 35 172 0 100000 9679
3.704 +a 35 117 0 100000 1469
3.705 +a 35 131 0 100000 7061
3.706 +a 35 106 0 100000 8448
3.707 +a 36 175 0 100000 8043
3.708 +a 36 121 0 100000 5151
3.709 +a 36 197 0 100000 7643
3.710 +a 36 116 0 100000 5790
3.711 +a 36 180 0 100000 1932
3.712 +a 36 128 0 100000 2477
3.713 +a 36 151 0 100000 5441
3.714 +a 36 174 0 100000 2204
3.715 +a 36 146 0 100000 7937
3.716 +a 36 193 0 100000 1912
3.717 +a 36 156 0 100000 5652
3.718 +a 36 138 0 100000 297
3.719 +a 36 191 0 100000 5116
3.720 +a 36 167 0 100000 8999
3.721 +a 36 140 0 100000 996
3.722 +a 36 103 0 100000 9577
3.723 +a 36 190 0 100000 1154
3.724 +a 36 165 0 100000 3326
3.725 +a 36 109 0 100000 1374
3.726 +a 36 110 0 100000 4679
3.727 +a 36 199 0 100000 134
3.728 +a 36 133 0 100000 9431
3.729 +a 37 174 0 100000 8274
3.730 +a 37 155 0 100000 4671
3.731 +a 37 114 0 100000 5912
3.732 +a 37 115 0 100000 506
3.733 +a 37 105 0 100000 592
3.734 +a 37 183 0 100000 2115
3.735 +a 37 108 0 100000 4928
3.736 +a 37 151 0 100000 4240
3.737 +a 37 148 0 100000 3234
3.738 +a 37 102 0 100000 8815
3.739 +a 37 109 0 100000 2968
3.740 +a 37 169 0 100000 6360
3.741 +a 37 128 0 100000 2348
3.742 +a 37 131 0 100000 6860
3.743 +a 37 166 0 100000 63
3.744 +a 37 103 0 100000 6161
3.745 +a 37 189 0 100000 4195
3.746 +a 37 147 0 100000 2127
3.747 +a 37 138 0 100000 7864
3.748 +a 37 163 0 100000 8904
3.749 +a 37 173 0 100000 1849
3.750 +a 38 134 0 100000 4026
3.751 +a 38 145 0 100000 2413
3.752 +a 38 165 0 100000 9230
3.753 +a 38 123 0 100000 6347
3.754 +a 38 185 0 100000 7621
3.755 +a 38 176 0 100000 6322
3.756 +a 38 198 0 100000 6454
3.757 +a 38 144 0 100000 5084
3.758 +a 38 121 0 100000 4462
3.759 +a 38 171 0 100000 5174
3.760 +a 38 136 0 100000 7419
3.761 +a 38 197 0 100000 7167
3.762 +a 38 179 0 100000 8980
3.763 +a 38 149 0 100000 7865
3.764 +a 38 178 0 100000 8248
3.765 +a 38 174 0 100000 6791
3.766 +a 38 164 0 100000 2361
3.767 +a 38 112 0 100000 2817
3.768 +a 38 196 0 100000 4887
3.769 +a 38 186 0 100000 9293
3.770 +a 38 106 0 100000 8175
3.771 +a 38 162 0 100000 8814
3.772 +a 38 181 0 100000 6761
3.773 +a 38 118 0 100000 7130
3.774 +a 39 157 0 100000 2168
3.775 +a 39 175 0 100000 5692
3.776 +a 39 178 0 100000 824
3.777 +a 39 142 0 100000 8831
3.778 +a 39 102 0 100000 8242
3.779 +a 39 121 0 100000 4162
3.780 +a 39 120 0 100000 658
3.781 +a 39 115 0 100000 451
3.782 +a 39 187 0 100000 7287
3.783 +a 39 117 0 100000 920
3.784 +a 40 107 0 100000 9440
3.785 +a 40 136 0 100000 9931
3.786 +a 40 103 0 100000 2181
3.787 +a 40 167 0 100000 3325
3.788 +a 40 129 0 100000 2074
3.789 +a 40 112 0 100000 8163
3.790 +a 40 104 0 100000 7518
3.791 +a 40 178 0 100000 8993
3.792 +a 40 116 0 100000 5561
3.793 +a 40 153 0 100000 1486
3.794 +a 40 171 0 100000 2580
3.795 +a 40 120 0 100000 9790
3.796 +a 40 175 0 100000 3030
3.797 +a 40 137 0 100000 7218
3.798 +a 40 177 0 100000 3087
3.799 +a 40 157 0 100000 4168
3.800 +a 41 181 0 100000 2843
3.801 +a 41 195 0 100000 38
3.802 +a 41 188 0 100000 5970
3.803 +a 41 129 0 100000 9147
3.804 +a 41 191 0 100000 6004
3.805 +a 41 116 0 100000 641
3.806 +a 41 122 0 100000 4426
3.807 +a 41 130 0 100000 9454
3.808 +a 41 170 0 100000 6046
3.809 +a 41 190 0 100000 4061
3.810 +a 41 174 0 100000 2125
3.811 +a 41 154 0 100000 5084
3.812 +a 41 160 0 100000 6356
3.813 +a 41 126 0 100000 5929
3.814 +a 41 196 0 100000 5812
3.815 +a 42 192 0 100000 517
3.816 +a 42 132 0 100000 9462
3.817 +a 42 146 0 100000 9442
3.818 +a 42 115 0 100000 897
3.819 +a 42 136 0 100000 1010
3.820 +a 42 143 0 100000 5852
3.821 +a 42 121 0 100000 1511
3.822 +a 42 189 0 100000 8165
3.823 +a 43 173 0 100000 8839
3.824 +a 43 177 0 100000 7059
3.825 +a 43 190 0 100000 5703
3.826 +a 43 106 0 100000 2300
3.827 +a 43 183 0 100000 8036
3.828 +a 43 184 0 100000 3295
3.829 +a 43 149 0 100000 47
3.830 +a 43 138 0 100000 8879
3.831 +a 43 129 0 100000 6876
3.832 +a 43 159 0 100000 2735
3.833 +a 43 191 0 100000 5062
3.834 +a 43 114 0 100000 9343
3.835 +a 43 187 0 100000 7699
3.836 +a 43 101 0 100000 6528
3.837 +a 44 136 0 100000 4162
3.838 +a 44 187 0 100000 2697
3.839 +a 44 163 0 100000 5418
3.840 +a 44 164 0 100000 398
3.841 +a 44 185 0 100000 4266
3.842 +a 44 161 0 100000 1979
3.843 +a 44 108 0 100000 290
3.844 +a 44 142 0 100000 6228
3.845 +a 45 153 0 100000 7269
3.846 +a 45 131 0 100000 9755
3.847 +a 45 143 0 100000 2025
3.848 +a 45 103 0 100000 8690
3.849 +a 45 118 0 100000 2138
3.850 +a 45 197 0 100000 5449
3.851 +a 45 102 0 100000 1992
3.852 +a 45 178 0 100000 8724
3.853 +a 45 145 0 100000 3579
3.854 +a 45 148 0 100000 3401
3.855 +a 45 137 0 100000 6512
3.856 +a 45 101 0 100000 4089
3.857 +a 45 166 0 100000 9039
3.858 +a 45 136 0 100000 3125
3.859 +a 45 156 0 100000 9040
3.860 +a 45 117 0 100000 9017
3.861 +a 45 130 0 100000 7846
3.862 +a 45 167 0 100000 5795
3.863 +a 45 112 0 100000 4049
3.864 +a 45 189 0 100000 5361
3.865 +a 45 110 0 100000 3463
3.866 +a 45 104 0 100000 2703
3.867 +a 45 191 0 100000 4933
3.868 +a 45 199 0 100000 453
3.869 +a 46 105 0 100000 2727
3.870 +a 46 101 0 100000 5811
3.871 +a 46 155 0 100000 4784
3.872 +a 46 118 0 100000 8390
3.873 +a 46 125 0 100000 1868
3.874 +a 46 102 0 100000 1061
3.875 +a 46 116 0 100000 6477
3.876 +a 46 117 0 100000 9105
3.877 +a 46 160 0 100000 8012
3.878 +a 46 111 0 100000 1797
3.879 +a 46 154 0 100000 3602
3.880 +a 46 167 0 100000 7643
3.881 +a 47 183 0 100000 3875
3.882 +a 47 185 0 100000 6570
3.883 +a 47 132 0 100000 4893
3.884 +a 47 110 0 100000 8941
3.885 +a 47 126 0 100000 7755
3.886 +a 47 149 0 100000 2372
3.887 +a 47 148 0 100000 9010
3.888 +a 47 172 0 100000 6363
3.889 +a 47 167 0 100000 8364
3.890 +a 47 188 0 100000 3388
3.891 +a 47 191 0 100000 9257
3.892 +a 47 147 0 100000 5413
3.893 +a 47 195 0 100000 5203
3.894 +a 47 154 0 100000 8479
3.895 +a 48 127 0 100000 4388
3.896 +a 48 184 0 100000 2303
3.897 +a 48 188 0 100000 5084
3.898 +a 48 169 0 100000 7676
3.899 +a 48 105 0 100000 2852
3.900 +a 48 193 0 100000 690
3.901 +a 48 158 0 100000 417
3.902 +a 48 153 0 100000 5
3.903 +a 48 111 0 100000 3129
3.904 +a 48 125 0 100000 2579
3.905 +a 48 166 0 100000 5544
3.906 +a 49 147 0 100000 7701
3.907 +a 49 167 0 100000 1900
3.908 +a 49 114 0 100000 233
3.909 +a 50 136 0 100000 3386
3.910 +a 50 144 0 100000 5104
3.911 +a 50 124 0 100000 3836
3.912 +a 50 103 0 100000 9195
3.913 +a 50 132 0 100000 9972
3.914 +a 50 105 0 100000 9808
3.915 +a 50 109 0 100000 7794
3.916 +a 50 185 0 100000 1427
3.917 +a 50 171 0 100000 861
3.918 +a 50 172 0 100000 8095
3.919 +a 50 137 0 100000 1247
3.920 +a 50 146 0 100000 1390
3.921 +a 50 164 0 100000 7230
3.922 +a 50 128 0 100000 6607
3.923 +a 50 192 0 100000 536
3.924 +a 50 162 0 100000 8900
3.925 +a 50 139 0 100000 4048
3.926 +a 50 168 0 100000 866
3.927 +a 50 163 0 100000 3045
3.928 +a 50 160 0 100000 5860
3.929 +a 50 154 0 100000 3524
3.930 +a 51 198 0 100000 8797
3.931 +a 51 113 0 100000 7824
3.932 +a 51 119 0 100000 6822
3.933 +a 51 121 0 100000 906
3.934 +a 51 126 0 100000 5758
3.935 +a 51 108 0 100000 482
3.936 +a 51 164 0 100000 7309
3.937 +a 51 179 0 100000 140
3.938 +a 51 151 0 100000 3541
3.939 +a 51 152 0 100000 4888
3.940 +a 51 191 0 100000 7396
3.941 +a 51 120 0 100000 450
3.942 +a 51 175 0 100000 164
3.943 +a 51 184 0 100000 2982
3.944 +a 51 109 0 100000 1592
3.945 +a 52 103 0 100000 5867
3.946 +a 52 168 0 100000 9405
3.947 +a 52 166 0 100000 1851
3.948 +a 52 107 0 100000 8869
3.949 +a 52 185 0 100000 8713
3.950 +a 52 105 0 100000 4844
3.951 +a 52 187 0 100000 5453
3.952 +a 52 177 0 100000 663
3.953 +a 52 161 0 100000 5850
3.954 +a 52 183 0 100000 4625
3.955 +a 52 133 0 100000 3978
3.956 +a 52 148 0 100000 9864
3.957 +a 52 155 0 100000 1239
3.958 +a 52 152 0 100000 1119
3.959 +a 52 120 0 100000 7484
3.960 +a 52 198 0 100000 1265
3.961 +a 52 149 0 100000 9158
3.962 +a 52 109 0 100000 8778
3.963 +a 52 181 0 100000 8651
3.964 +a 52 170 0 100000 5148
3.965 +a 52 122 0 100000 6264
3.966 +a 53 127 0 100000 6883
3.967 +a 53 171 0 100000 6015
3.968 +a 53 153 0 100000 1067
3.969 +a 53 184 0 100000 4740
3.970 +a 53 131 0 100000 2021
3.971 +a 53 176 0 100000 3635
3.972 +a 53 141 0 100000 6086
3.973 +a 53 159 0 100000 4074
3.974 +a 54 184 0 100000 9056
3.975 +a 54 137 0 100000 1830
3.976 +a 54 134 0 100000 1633
3.977 +a 54 106 0 100000 7750
3.978 +a 55 158 0 100000 8771
3.979 +a 55 103 0 100000 9981
3.980 +a 55 105 0 100000 4340
3.981 +a 55 141 0 100000 1298
3.982 +a 55 198 0 100000 2025
3.983 +a 55 136 0 100000 7016
3.984 +a 55 111 0 100000 9926
3.985 +a 55 152 0 100000 7367
3.986 +a 55 147 0 100000 7000
3.987 +a 55 133 0 100000 2114
3.988 +a 55 188 0 100000 6509
3.989 +a 55 102 0 100000 7100
3.990 +a 55 140 0 100000 9075
3.991 +a 55 195 0 100000 2705
3.992 +a 55 183 0 100000 3775
3.993 +a 55 199 0 100000 9215
3.994 +a 55 193 0 100000 2312
3.995 +a 56 162 0 100000 3207
3.996 +a 56 104 0 100000 2760
3.997 +a 56 146 0 100000 129
3.998 +a 56 115 0 100000 6086
3.999 +a 56 181 0 100000 8352
3.1000 +a 56 142 0 100000 5707
3.1001 +a 56 164 0 100000 8547
3.1002 +a 56 168 0 100000 2167
3.1003 +a 56 153 0 100000 2387
3.1004 +a 56 151 0 100000 6697
3.1005 +a 56 187 0 100000 3439
3.1006 +a 56 160 0 100000 5918
3.1007 +a 57 173 0 100000 1494
3.1008 +a 57 111 0 100000 3886
3.1009 +a 57 183 0 100000 8402
3.1010 +a 57 169 0 100000 9896
3.1011 +a 57 146 0 100000 376
3.1012 +a 57 192 0 100000 5247
3.1013 +a 58 150 0 100000 9423
3.1014 +a 58 183 0 100000 9465
3.1015 +a 58 148 0 100000 3885
3.1016 +a 58 111 0 100000 4529
3.1017 +a 58 129 0 100000 4093
3.1018 +a 58 196 0 100000 3619
3.1019 +a 58 102 0 100000 4690
3.1020 +a 58 101 0 100000 9365
3.1021 +a 59 120 0 100000 9651
3.1022 +a 59 181 0 100000 1323
3.1023 +a 59 155 0 100000 4233
3.1024 +a 59 156 0 100000 6044
3.1025 +a 59 194 0 100000 7289
3.1026 +a 59 148 0 100000 1133
3.1027 +a 59 198 0 100000 3136
3.1028 +a 59 130 0 100000 4275
3.1029 +a 59 184 0 100000 5271
3.1030 +a 59 132 0 100000 4958
3.1031 +a 59 101 0 100000 705
3.1032 +a 59 186 0 100000 576
3.1033 +a 59 179 0 100000 6456
3.1034 +a 59 188 0 100000 5973
3.1035 +a 59 173 0 100000 3298
3.1036 +a 59 102 0 100000 125
3.1037 +a 59 196 0 100000 6596
3.1038 +a 59 195 0 100000 2748
3.1039 +a 59 182 0 100000 5207
3.1040 +a 59 127 0 100000 2055
3.1041 +a 60 140 0 100000 198
3.1042 +a 60 125 0 100000 5868
3.1043 +a 60 112 0 100000 1114
3.1044 +a 60 139 0 100000 6263
3.1045 +a 60 135 0 100000 7430
3.1046 +a 60 113 0 100000 9681
3.1047 +a 60 173 0 100000 4299
3.1048 +a 60 114 0 100000 3324
3.1049 +a 60 148 0 100000 6396
3.1050 +a 60 105 0 100000 8471
3.1051 +a 60 137 0 100000 6050
3.1052 +a 60 176 0 100000 1898
3.1053 +a 60 144 0 100000 7048
3.1054 +a 60 158 0 100000 1960
3.1055 +a 60 142 0 100000 808
3.1056 +a 60 199 0 100000 6892
3.1057 +a 60 181 0 100000 9745
3.1058 +a 60 183 0 100000 4567
3.1059 +a 60 129 0 100000 8038
3.1060 +a 60 182 0 100000 4638
3.1061 +a 61 189 0 100000 622
3.1062 +a 61 198 0 100000 2853
3.1063 +a 61 124 0 100000 5593
3.1064 +a 61 163 0 100000 5273
3.1065 +a 61 190 0 100000 7555
3.1066 +a 61 176 0 100000 5610
3.1067 +a 61 147 0 100000 3824
3.1068 +a 61 160 0 100000 2776
3.1069 +a 61 164 0 100000 611
3.1070 +a 61 112 0 100000 3067
3.1071 +a 61 156 0 100000 7410
3.1072 +a 62 104 0 100000 2965
3.1073 +a 62 190 0 100000 5531
3.1074 +a 62 162 0 100000 951
3.1075 +a 62 191 0 100000 9851
3.1076 +a 62 108 0 100000 2837
3.1077 +a 62 165 0 100000 9780
3.1078 +a 62 147 0 100000 2541
3.1079 +a 62 169 0 100000 9168
3.1080 +a 62 125 0 100000 3518
3.1081 +a 62 102 0 100000 6357
3.1082 +a 62 117 0 100000 7423
3.1083 +a 62 149 0 100000 6295
3.1084 +a 62 133 0 100000 3556
3.1085 +a 62 172 0 100000 2760
3.1086 +a 62 131 0 100000 1038
3.1087 +a 62 112 0 100000 8003
3.1088 +a 62 196 0 100000 5587
3.1089 +a 62 157 0 100000 7749
3.1090 +a 63 111 0 100000 2883
3.1091 +a 63 195 0 100000 5347
3.1092 +a 63 112 0 100000 5677
3.1093 +a 63 115 0 100000 7834
3.1094 +a 63 174 0 100000 112
3.1095 +a 63 126 0 100000 6624
3.1096 +a 63 117 0 100000 6148
3.1097 +a 64 144 0 100000 6266
3.1098 +a 64 164 0 100000 4807
3.1099 +a 64 171 0 100000 3160
3.1100 +a 64 119 0 100000 1438
3.1101 +a 64 136 0 100000 7963
3.1102 +a 64 197 0 100000 2673
3.1103 +a 64 155 0 100000 5421
3.1104 +a 64 133 0 100000 5839
3.1105 +a 64 138 0 100000 1274
3.1106 +a 64 127 0 100000 1906
3.1107 +a 64 161 0 100000 1934
3.1108 +a 64 118 0 100000 2475
3.1109 +a 64 169 0 100000 6793
3.1110 +a 64 116 0 100000 1502
3.1111 +a 64 158 0 100000 9432
3.1112 +a 64 148 0 100000 5157
3.1113 +a 64 145 0 100000 2663
3.1114 +a 64 174 0 100000 5351
3.1115 +a 64 114 0 100000 390
3.1116 +a 64 181 0 100000 6721
3.1117 +a 64 113 0 100000 521
3.1118 +a 65 132 0 100000 983
3.1119 +a 65 177 0 100000 277
3.1120 +a 65 199 0 100000 8990
3.1121 +a 65 179 0 100000 7885
3.1122 +a 65 136 0 100000 3413
3.1123 +a 65 130 0 100000 751
3.1124 +a 65 168 0 100000 9573
3.1125 +a 65 111 0 100000 1534
3.1126 +a 65 124 0 100000 3928
3.1127 +a 65 106 0 100000 3456
3.1128 +a 66 115 0 100000 3992
3.1129 +a 66 104 0 100000 5112
3.1130 +a 66 130 0 100000 7285
3.1131 +a 66 163 0 100000 3213
3.1132 +a 67 153 0 100000 5367
3.1133 +a 67 164 0 100000 992
3.1134 +a 67 179 0 100000 3091
3.1135 +a 67 193 0 100000 6000
3.1136 +a 67 107 0 100000 2802
3.1137 +a 67 110 0 100000 6027
3.1138 +a 67 176 0 100000 1881
3.1139 +a 68 189 0 100000 8212
3.1140 +a 68 117 0 100000 5853
3.1141 +a 68 102 0 100000 1766
3.1142 +a 68 147 0 100000 9440
3.1143 +a 68 125 0 100000 4494
3.1144 +a 68 196 0 100000 2219
3.1145 +a 68 128 0 100000 8093
3.1146 +a 68 145 0 100000 1500
3.1147 +a 68 152 0 100000 7419
3.1148 +a 68 112 0 100000 357
3.1149 +a 69 169 0 100000 7598
3.1150 +a 69 180 0 100000 4870
3.1151 +a 69 147 0 100000 5253
3.1152 +a 69 119 0 100000 1569
3.1153 +a 69 123 0 100000 2218
3.1154 +a 69 128 0 100000 3191
3.1155 +a 69 178 0 100000 3243
3.1156 +a 69 109 0 100000 2712
3.1157 +a 70 104 0 100000 3090
3.1158 +a 70 161 0 100000 8413
3.1159 +a 70 160 0 100000 5623
3.1160 +a 70 164 0 100000 4675
3.1161 +a 70 101 0 100000 3196
3.1162 +a 70 151 0 100000 6580
3.1163 +a 70 182 0 100000 2231
3.1164 +a 70 189 0 100000 4394
3.1165 +a 70 176 0 100000 7897
3.1166 +a 70 118 0 100000 2776
3.1167 +a 70 135 0 100000 1215
3.1168 +a 70 163 0 100000 3973
3.1169 +a 70 147 0 100000 6983
3.1170 +a 70 145 0 100000 9550
3.1171 +a 70 177 0 100000 9000
3.1172 +a 71 189 0 100000 9496
3.1173 +a 71 176 0 100000 7401
3.1174 +a 71 168 0 100000 3386
3.1175 +a 71 171 0 100000 857
3.1176 +a 71 106 0 100000 1626
3.1177 +a 71 180 0 100000 4392
3.1178 +a 71 117 0 100000 1387
3.1179 +a 71 120 0 100000 2961
3.1180 +a 72 114 0 100000 1334
3.1181 +a 72 155 0 100000 1601
3.1182 +a 72 125 0 100000 4500
3.1183 +a 72 193 0 100000 6333
3.1184 +a 72 142 0 100000 2443
3.1185 +a 72 143 0 100000 6087
3.1186 +a 72 126 0 100000 3103
3.1187 +a 72 122 0 100000 7043
3.1188 +a 72 144 0 100000 2262
3.1189 +a 72 149 0 100000 8288
3.1190 +a 72 169 0 100000 7041
3.1191 +a 72 191 0 100000 1744
3.1192 +a 72 102 0 100000 800
3.1193 +a 72 112 0 100000 6299
3.1194 +a 72 135 0 100000 4666
3.1195 +a 73 149 0 100000 7120
3.1196 +a 73 135 0 100000 4142
3.1197 +a 73 126 0 100000 4345
3.1198 +a 73 163 0 100000 2025
3.1199 +a 73 181 0 100000 6997
3.1200 +a 73 183 0 100000 4271
3.1201 +a 73 137 0 100000 1721
3.1202 +a 73 108 0 100000 8579
3.1203 +a 73 157 0 100000 3323
3.1204 +a 73 189 0 100000 7748
3.1205 +a 73 193 0 100000 2716
3.1206 +a 73 133 0 100000 7771
3.1207 +a 74 179 0 100000 6114
3.1208 +a 74 165 0 100000 2864
3.1209 +a 74 143 0 100000 8298
3.1210 +a 74 185 0 100000 25
3.1211 +a 74 122 0 100000 6212
3.1212 +a 74 153 0 100000 3894
3.1213 +a 74 171 0 100000 4548
3.1214 +a 74 119 0 100000 118
3.1215 +a 74 199 0 100000 993
3.1216 +a 74 142 0 100000 450
3.1217 +a 74 157 0 100000 239
3.1218 +a 74 133 0 100000 4863
3.1219 +a 74 149 0 100000 6706
3.1220 +a 74 131 0 100000 6898
3.1221 +a 74 170 0 100000 3870
3.1222 +a 74 155 0 100000 1070
3.1223 +a 74 160 0 100000 8776
3.1224 +a 74 186 0 100000 1287
3.1225 +a 74 156 0 100000 168
3.1226 +a 74 115 0 100000 9426
3.1227 +a 74 178 0 100000 8333
3.1228 +a 75 158 0 100000 8894
3.1229 +a 75 118 0 100000 5751
3.1230 +a 75 183 0 100000 701
3.1231 +a 75 136 0 100000 7606
3.1232 +a 75 114 0 100000 6108
3.1233 +a 75 187 0 100000 1344
3.1234 +a 75 139 0 100000 6359
3.1235 +a 76 154 0 100000 2123
3.1236 +a 76 108 0 100000 8824
3.1237 +a 76 177 0 100000 7541
3.1238 +a 76 164 0 100000 2126
3.1239 +a 77 112 0 100000 4554
3.1240 +a 77 135 0 100000 1530
3.1241 +a 77 174 0 100000 8435
3.1242 +a 77 163 0 100000 2591
3.1243 +a 77 115 0 100000 2699
3.1244 +a 77 148 0 100000 1129
3.1245 +a 77 151 0 100000 3926
3.1246 +a 77 122 0 100000 5591
3.1247 +a 77 171 0 100000 485
3.1248 +a 77 185 0 100000 3582
3.1249 +a 77 159 0 100000 6813
3.1250 +a 77 186 0 100000 9253
3.1251 +a 77 192 0 100000 8683
3.1252 +a 77 189 0 100000 2594
3.1253 +a 77 126 0 100000 3857
3.1254 +a 77 187 0 100000 4829
3.1255 +a 77 101 0 100000 3127
3.1256 +a 77 168 0 100000 9562
3.1257 +a 78 130 0 100000 4773
3.1258 +a 78 181 0 100000 8278
3.1259 +a 78 174 0 100000 9425
3.1260 +a 78 157 0 100000 960
3.1261 +a 78 153 0 100000 6664
3.1262 +a 78 193 0 100000 1091
3.1263 +a 78 191 0 100000 1146
3.1264 +a 78 167 0 100000 2079
3.1265 +a 78 187 0 100000 7846
3.1266 +a 78 180 0 100000 6890
3.1267 +a 78 140 0 100000 3681
3.1268 +a 78 123 0 100000 9889
3.1269 +a 78 136 0 100000 2581
3.1270 +a 78 114 0 100000 8237
3.1271 +a 78 185 0 100000 7211
3.1272 +a 78 179 0 100000 2871
3.1273 +a 78 163 0 100000 9106
3.1274 +a 78 176 0 100000 613
3.1275 +a 78 113 0 100000 6406
3.1276 +a 78 120 0 100000 2646
3.1277 +a 79 129 0 100000 9500
3.1278 +a 79 117 0 100000 642
3.1279 +a 79 112 0 100000 4390
3.1280 +a 79 163 0 100000 8981
3.1281 +a 79 134 0 100000 692
3.1282 +a 79 151 0 100000 9675
3.1283 +a 79 141 0 100000 9335
3.1284 +a 79 195 0 100000 592
3.1285 +a 79 148 0 100000 9350
3.1286 +a 80 163 0 100000 7627
3.1287 +a 80 115 0 100000 1213
3.1288 +a 80 176 0 100000 6650
3.1289 +a 80 154 0 100000 1461
3.1290 +a 80 129 0 100000 5116
3.1291 +a 80 190 0 100000 8975
3.1292 +a 80 110 0 100000 6622
3.1293 +a 80 172 0 100000 5146
3.1294 +a 80 179 0 100000 9326
3.1295 +a 80 194 0 100000 9545
3.1296 +a 80 193 0 100000 9695
3.1297 +a 80 105 0 100000 6431
3.1298 +a 80 153 0 100000 8063
3.1299 +a 80 151 0 100000 268
3.1300 +a 80 141 0 100000 3870
3.1301 +a 80 127 0 100000 7778
3.1302 +a 80 186 0 100000 1408
3.1303 +a 80 103 0 100000 8091
3.1304 +a 80 147 0 100000 7096
3.1305 +a 81 176 0 100000 5892
3.1306 +a 81 104 0 100000 9989
3.1307 +a 81 148 0 100000 2980
3.1308 +a 81 117 0 100000 4901
3.1309 +a 81 168 0 100000 7736
3.1310 +a 81 183 0 100000 2080
3.1311 +a 81 109 0 100000 4254
3.1312 +a 81 136 0 100000 4219
3.1313 +a 81 113 0 100000 599
3.1314 +a 81 194 0 100000 945
3.1315 +a 81 131 0 100000 6901
3.1316 +a 81 120 0 100000 8066
3.1317 +a 81 112 0 100000 6948
3.1318 +a 81 163 0 100000 290
3.1319 +a 81 167 0 100000 3149
3.1320 +a 81 192 0 100000 3799
3.1321 +a 81 199 0 100000 9046
3.1322 +a 81 114 0 100000 3217
3.1323 +a 82 155 0 100000 1806
3.1324 +a 82 149 0 100000 8452
3.1325 +a 82 131 0 100000 9547
3.1326 +a 82 164 0 100000 6171
3.1327 +a 82 123 0 100000 746
3.1328 +a 82 192 0 100000 7626
3.1329 +a 82 109 0 100000 6452
3.1330 +a 82 183 0 100000 6875
3.1331 +a 82 199 0 100000 9335
3.1332 +a 82 106 0 100000 8829
3.1333 +a 82 140 0 100000 4045
3.1334 +a 82 139 0 100000 1519
3.1335 +a 82 198 0 100000 8376
3.1336 +a 82 132 0 100000 1494
3.1337 +a 83 134 0 100000 8175
3.1338 +a 83 148 0 100000 9715
3.1339 +a 83 137 0 100000 5879
3.1340 +a 83 187 0 100000 6419
3.1341 +a 83 158 0 100000 8364
3.1342 +a 83 109 0 100000 1339
3.1343 +a 83 189 0 100000 3531
3.1344 +a 83 104 0 100000 8448
3.1345 +a 83 142 0 100000 7624
3.1346 +a 84 122 0 100000 9325
3.1347 +a 84 155 0 100000 6505
3.1348 +a 84 197 0 100000 2423
3.1349 +a 84 162 0 100000 7925
3.1350 +a 85 120 0 100000 5058
3.1351 +a 85 141 0 100000 7909
3.1352 +a 85 116 0 100000 744
3.1353 +a 85 117 0 100000 3459
3.1354 +a 85 178 0 100000 6907
3.1355 +a 85 105 0 100000 5893
3.1356 +a 85 111 0 100000 5745
3.1357 +a 85 119 0 100000 5858
3.1358 +a 85 128 0 100000 2066
3.1359 +a 85 168 0 100000 3736
3.1360 +a 85 172 0 100000 7023
3.1361 +a 85 109 0 100000 4184
3.1362 +a 85 197 0 100000 5602
3.1363 +a 86 139 0 100000 7483
3.1364 +a 86 168 0 100000 3950
3.1365 +a 86 157 0 100000 9064
3.1366 +a 86 162 0 100000 2213
3.1367 +a 87 103 0 100000 2133
3.1368 +a 87 152 0 100000 4604
3.1369 +a 87 169 0 100000 5604
3.1370 +a 87 146 0 100000 2714
3.1371 +a 87 166 0 100000 5340
3.1372 +a 87 199 0 100000 5069
3.1373 +a 87 148 0 100000 9419
3.1374 +a 87 104 0 100000 9528
3.1375 +a 87 141 0 100000 9671
3.1376 +a 87 107 0 100000 7085
3.1377 +a 87 131 0 100000 4186
3.1378 +a 87 114 0 100000 2238
3.1379 +a 87 191 0 100000 2804
3.1380 +a 87 132 0 100000 1397
3.1381 +a 87 185 0 100000 9858
3.1382 +a 88 139 0 100000 2066
3.1383 +a 88 144 0 100000 892
3.1384 +a 88 197 0 100000 5596
3.1385 +a 89 184 0 100000 9075
3.1386 +a 89 179 0 100000 4975
3.1387 +a 89 161 0 100000 2205
3.1388 +a 89 176 0 100000 7314
3.1389 +a 89 126 0 100000 6811
3.1390 +a 89 187 0 100000 8180
3.1391 +a 89 102 0 100000 7763
3.1392 +a 89 173 0 100000 8398
3.1393 +a 89 181 0 100000 7363
3.1394 +a 89 129 0 100000 7490
3.1395 +a 89 162 0 100000 8354
3.1396 +a 90 187 0 100000 7647
3.1397 +a 90 153 0 100000 5311
3.1398 +a 90 192 0 100000 2193
3.1399 +a 90 141 0 100000 4888
3.1400 +a 90 165 0 100000 8780
3.1401 +a 90 102 0 100000 5458
3.1402 +a 90 125 0 100000 7208
3.1403 +a 90 158 0 100000 1113
3.1404 +a 90 198 0 100000 6401
3.1405 +a 90 111 0 100000 1515
3.1406 +a 90 138 0 100000 3238
3.1407 +a 90 180 0 100000 3045
3.1408 +a 90 186 0 100000 3
3.1409 +a 90 178 0 100000 8749
3.1410 +a 90 177 0 100000 1632
3.1411 +a 90 106 0 100000 4327
3.1412 +a 90 196 0 100000 470
3.1413 +a 90 163 0 100000 7911
3.1414 +a 91 113 0 100000 8296
3.1415 +a 91 127 0 100000 2971
3.1416 +a 91 146 0 100000 3356
3.1417 +a 91 182 0 100000 2580
3.1418 +a 91 196 0 100000 8202
3.1419 +a 91 116 0 100000 3104
3.1420 +a 92 191 0 100000 8165
3.1421 +a 92 166 0 100000 2242
3.1422 +a 92 197 0 100000 9395
3.1423 +a 93 136 0 100000 8664
3.1424 +a 93 129 0 100000 7802
3.1425 +a 93 170 0 100000 4699
3.1426 +a 93 124 0 100000 5870
3.1427 +a 93 137 0 100000 9775
3.1428 +a 93 115 0 100000 7499
3.1429 +a 93 110 0 100000 9601
3.1430 +a 93 101 0 100000 9002
3.1431 +a 93 150 0 100000 9882
3.1432 +a 93 104 0 100000 1079
3.1433 +a 93 193 0 100000 7464
3.1434 +a 93 105 0 100000 7327
3.1435 +a 93 166 0 100000 1808
3.1436 +a 94 169 0 100000 7589
3.1437 +a 94 141 0 100000 2981
3.1438 +a 94 180 0 100000 9358
3.1439 +a 94 176 0 100000 8554
3.1440 +a 94 124 0 100000 2707
3.1441 +a 94 122 0 100000 7508
3.1442 +a 94 166 0 100000 3171
3.1443 +a 94 165 0 100000 9695
3.1444 +a 94 154 0 100000 8485
3.1445 +a 94 170 0 100000 2444
3.1446 +a 94 177 0 100000 3552
3.1447 +a 94 114 0 100000 6951
3.1448 +a 94 164 0 100000 6526
3.1449 +a 94 189 0 100000 8986
3.1450 +a 94 110 0 100000 4338
3.1451 +a 94 109 0 100000 2554
3.1452 +a 94 116 0 100000 7506
3.1453 +a 94 133 0 100000 1605
3.1454 +a 94 156 0 100000 9888
3.1455 +a 95 157 0 100000 8289
3.1456 +a 95 116 0 100000 1995
3.1457 +a 95 194 0 100000 8381
3.1458 +a 95 132 0 100000 7280
3.1459 +a 95 134 0 100000 6754
3.1460 +a 95 136 0 100000 1773
3.1461 +a 95 144 0 100000 9910
3.1462 +a 95 156 0 100000 1163
3.1463 +a 95 124 0 100000 9214
3.1464 +a 95 146 0 100000 6315
3.1465 +a 95 126 0 100000 2269
3.1466 +a 95 140 0 100000 637
3.1467 +a 95 183 0 100000 924
3.1468 +a 95 163 0 100000 8392
3.1469 +a 95 145 0 100000 8797
3.1470 +a 96 156 0 100000 6213
3.1471 +a 96 129 0 100000 7538
3.1472 +a 96 123 0 100000 8516
3.1473 +a 96 169 0 100000 3383
3.1474 +a 96 142 0 100000 2851
3.1475 +a 96 124 0 100000 8365
3.1476 +a 96 184 0 100000 4157
3.1477 +a 97 182 0 100000 3135
3.1478 +a 97 130 0 100000 3328
3.1479 +a 97 170 0 100000 5735
3.1480 +a 97 174 0 100000 2525
3.1481 +a 97 151 0 100000 5910
3.1482 +a 97 141 0 100000 4351
3.1483 +a 97 126 0 100000 8844
3.1484 +a 97 155 0 100000 629
3.1485 +a 97 149 0 100000 9449
3.1486 +a 97 108 0 100000 422
3.1487 +a 97 131 0 100000 775
3.1488 +a 97 154 0 100000 9304
3.1489 +a 97 172 0 100000 5967
3.1490 +a 97 123 0 100000 793
3.1491 +a 97 128 0 100000 7372
3.1492 +a 97 121 0 100000 835
3.1493 +a 97 157 0 100000 690
3.1494 +a 97 165 0 100000 1889
3.1495 +a 97 156 0 100000 2855
3.1496 +a 97 106 0 100000 3640
3.1497 +a 97 105 0 100000 9742
3.1498 +a 97 122 0 100000 9646
3.1499 +a 97 107 0 100000 3286
3.1500 +a 98 131 0 100000 9078
3.1501 +a 98 196 0 100000 5946
3.1502 +a 98 113 0 100000 9995
3.1503 +a 98 177 0 100000 825
3.1504 +a 98 119 0 100000 7372
3.1505 +a 98 188 0 100000 2749
3.1506 +a 98 130 0 100000 7285
3.1507 +a 98 120 0 100000 7653
3.1508 +a 98 152 0 100000 3129
3.1509 +a 98 104 0 100000 9652
3.1510 +a 98 108 0 100000 7514
3.1511 +a 98 117 0 100000 7705
3.1512 +a 98 171 0 100000 1725
3.1513 +a 99 105 0 100000 5557
3.1514 +a 99 109 0 100000 5355
3.1515 +a 99 114 0 100000 8765
3.1516 +a 99 112 0 100000 100
3.1517 +a 99 187 0 100000 8348
3.1518 +a 99 199 0 100000 419
3.1519 +a 99 167 0 100000 2556
3.1520 +a 99 129 0 100000 196
3.1521 +a 100 184 0 100000 5607
3.1522 +a 100 150 0 100000 749
3.1523 +a 100 110 0 100000 2973
3.1524 +a 100 126 0 100000 9347
3.1525 +a 100 128 0 100000 3349
3.1526 +a 100 133 0 100000 3154
3.1527 +a 100 138 0 100000 8997
3.1528 +a 100 146 0 100000 4125
3.1529 +a 100 151 0 100000 8931
3.1530 +a 100 160 0 100000 1750
3.1531 +a 100 170 0 100000 5508
3.1532 +a 100 178 0 100000 1772
3.1533 +a 100 199 0 100000 9538
3.1534 +a 100 200 0 100000 3509