#include <iostream>
#include <vector>
#include <stdlib.h>
 
using namespace std;
 
struct params_t{
  int world_size; // size of the world (side of the square world)
  double initial_proportion; // initial proportion of living cells
  int max_t; // maximum time for simulation
  int delay; // period in terms of the number of time steps before
             // each display of the world (to make more efficient
             // outputs)
  int num_runs; // number of runs to execute
  int display; // turn on the display-world feature (yes=1, no=0)
};
 
struct stats_t {
  int num_steps;           // the number of time steps
  vector<int> num_living;  // the number of living cells (at a time)
  vector<int> num_dead;    // the number of dead cells (at a time)
};
 
void initialize_world(vector< vector<int> > &world, double p)
{
  int i, j, n;
 
  n = world.size();
 
  // generate each cell to be alive with probability p
 
  for (i=0; i<n; i++)
    for (j=0; j<n; j++)
      {
	if (drand48()<p)
	  world[i][j] = 1;
	else
	  world[i][j] = 0;
      }
}
 
int count_neighbors(vector< vector<int> > &world, 
		    int i,
		    int j,
		    int n)
{
  int di, dj;
  int num_neighbors=0;
 
  // note that this assumes wrap-around world, in which
  // the last cell in any row is a neighbor of the very
  // first cell in the row; similarly for the columns
 
  for (di = -1; di <= 1; di++)
    for (dj = -1; dj <= 1; dj++)
      if ((di!=0)||(dj!=0))
	num_neighbors += world[(i+di+n)%n][(j+dj+n)%n];
 
  // return the number of neighbors
 
  return num_neighbors;      
}
 
void process_world(vector< vector<int> > &new_world,
		   vector< vector<int> > &world)
{
  int i, j;
  int n = world.size();
 
  // count neighbors of every cell, and generate the new
  // world using the basic rules of the game of life
  // - living cell dies if less than 2 living neighbors
  // - living cell dies if more than 3 living neighbors
  // - dead cell changes to living if exactly 3 neighbors
  // - otherwise, no change
 
  for (i=0; i<n; i++)
    for (j=0; j<n; j++)
      {
	int num_neighbors = count_neighbors(world, i, j, n);
 
	// these conditions implement the rules
 
	if (world[i][j]==1) // living cell
	  {
	    if (num_neighbors<2)
	      new_world[i][j] = 0;   // died because of underpopulation
	    else
	      if (num_neighbors>3)
		new_world[i][j] = 0; // died because of overcrowding
	      else
		new_world[i][j] = 1; // cell goes on living
	  }
	else
	  if (num_neighbors==3) // dead cell
	    new_world[i][j] = 1; // reproduction (new cell)
	  else
	    new_world[i][j] = 0; // remains empty cell
      }
}
 
void display_world(vector< vector<int> > &world)
{
  int i, j;
  int n = world.size();
  int num_living = 0;
  int num_dead = 0;
 
  // show the content of each cell in a reasonably readable format
  // (as a matrix with * denoting a living cell)
 
  for (i=0; i<n; i++)
    {
      for (j=0; j<n; j++)
	if (world[i][j]==1)
	  {
	    cout << "* ";
	    num_living++;
	  }
	else
	  {
	    cout << "  ";
	    num_dead++;
	  }
      cout << endl;
    }
 
  cout << endl;
  cout << "num_living = " << num_living << endl;
  cout << "num_dead =   " << num_dead << endl;
  cout << endl;
}
 
void compute_statistics(vector< vector<int> > &world,
			stats_t &stats,
			int t)
{
  int i,j;
  int n = world.size();
 
  // the number of living and dead cells is 0 initially
 
  stats.num_living[t] = 0;
  stats.num_dead[t]   = 0;
 
  // do the counts
 
  for (i=0; i<n; i++)
    for (j=0; j<n; j++)
      if (world[i][j]==1)
	stats.num_living[t]++;
      else
	stats.num_dead[t]++;
}
 
void run_simulation(params_t &params, stats_t &stats)
{
  int i, t = 0;
  vector< vector<int> > world(params.world_size);
  vector< vector<int> > new_world(params.world_size);
 
  // store the number of steps and make sure that there
  // is enough space to store the statistics 
 
  stats.num_steps=params.max_t;
  stats.num_living.resize(params.max_t+1);
  stats.num_dead.resize(params.max_t+1);
 
  // runs the simulation
 
  for (i=0; i<params.world_size; i++)
    {
      world[i].resize(params.world_size);
      new_world[i].resize(params.world_size);
    }
 
  // initialize the world
 
  initialize_world(world, params.initial_proportion);
 
  // compute statistics for the current time step (now t=0)
 
  compute_statistics(world, stats, t);
 
  // print out the initial world 
 
  if (params.display)
    {
      cout << "----------------------------------------------------------" << endl;
      cout << "INITIAL WORLD" << endl << endl;
      display_world(world);
    }
 
  for (t=1; t<=params.max_t; t++)
    {
      // create new world using the old world and the rules
 
      process_world(new_world, world);
 
      // new world becomes current world
 
      swap(world, new_world);
 
      // compute the statistics
 
      compute_statistics(world, stats, t);
 
      // print out the world (once in each params.delay steps)
 
      if (((t-1)%params.delay==0)&&(params.display))
	{
	  cout << "----------------------------------------------------------" << endl;
	  cout << "WORLD AT TIME " << t << endl << endl;
	  display_world(world);
	}
    }
}
 
void process_statistics(vector<stats_t> stats)
{
  int run;
  int t;
  int num_runs = stats.size();
  int max_t    = stats[0].num_steps;
 
  cout << "Final statistics over " << num_runs << " runs:" << endl;
 
  // process statistics for all time steps and runs
  // (averaging the numbers for each time step over
  // the runs)
 
  for (t=0; t<=max_t; t++)
    {
      double avg_num_living = 0;
      double avg_num_dead   = 0;
 
      for (run=0; run<num_runs; run++)
	{
	  avg_num_living += stats[run].num_living[t];
	  avg_num_dead   += stats[run].num_dead[t];
	}
 
      avg_num_living /= num_runs;
      avg_num_dead   /= num_runs;
 
      cout << t << " " << avg_num_living << " " << avg_num_dead << " ";
      cout << " " << avg_num_living*100/(avg_num_living+avg_num_dead) << " ";
      cout << " " << avg_num_dead*100/(avg_num_living+avg_num_dead) << " ";
      cout << endl;
    }
}
 
int main()
{
  int run;
  params_t params;
  vector<stats_t> stats;
 
  // initialize random number generator
 
  srand48(123);
 
  // read user parameters
 
  cin >> params.world_size;
  cin >> params.initial_proportion;
  cin >> params.max_t;
  cin >> params.delay;
  cin >> params.num_runs;
  cin >> params.display;
 
  // adjust parameters if necessary
 
  if (params.world_size<1)
    params.world_size=1;
  if (params.initial_proportion<0)
    params.initial_proportion=0;
  if (params.initial_proportion>1)
    params.initial_proportion=1;
  if (params.max_t<1)
    params.max_t=1;
  if (params.delay<1)
    params.delay=1;
  if (params.num_runs<1)
    params.num_runs=1;
 
  // print out parameters
 
  cout << "World size:         " << params.world_size << endl;
  cout << "Initial proportion: " << params.initial_proportion << endl;
  cout << "Maximum time steps: " << params.max_t << endl;
  cout << "Reporting period:   " << params.delay << endl; 
  cout << "Number of runs:     " << params.num_runs << endl;
  cout << "Display world:      " << params.display << endl;
  cout << endl;
 
  // run the game of life simulation
 
  stats.resize(params.num_runs);  // resize the vector for statistics
  for (run=0; run<params.num_runs; run++)
    {
      cout << "Executing run " << run << endl;
      run_simulation(params, stats[run]);   // execute one run
    }
  cout << endl;
 
  // process statistics
 
  process_statistics(stats);
 
  // return 0 from main
 
  return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RkbGliLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IHBhcmFtc190ewogIGludCB3b3JsZF9zaXplOyAvLyBzaXplIG9mIHRoZSB3b3JsZCAoc2lkZSBvZiB0aGUgc3F1YXJlIHdvcmxkKQogIGRvdWJsZSBpbml0aWFsX3Byb3BvcnRpb247IC8vIGluaXRpYWwgcHJvcG9ydGlvbiBvZiBsaXZpbmcgY2VsbHMKICBpbnQgbWF4X3Q7IC8vIG1heGltdW0gdGltZSBmb3Igc2ltdWxhdGlvbgogIGludCBkZWxheTsgLy8gcGVyaW9kIGluIHRlcm1zIG9mIHRoZSBudW1iZXIgb2YgdGltZSBzdGVwcyBiZWZvcmUKICAgICAgICAgICAgIC8vIGVhY2ggZGlzcGxheSBvZiB0aGUgd29ybGQgKHRvIG1ha2UgbW9yZSBlZmZpY2llbnQKICAgICAgICAgICAgIC8vIG91dHB1dHMpCiAgaW50IG51bV9ydW5zOyAvLyBudW1iZXIgb2YgcnVucyB0byBleGVjdXRlCiAgaW50IGRpc3BsYXk7IC8vIHR1cm4gb24gdGhlIGRpc3BsYXktd29ybGQgZmVhdHVyZSAoeWVzPTEsIG5vPTApCn07CgpzdHJ1Y3Qgc3RhdHNfdCB7CiAgaW50IG51bV9zdGVwczsgICAgICAgICAgIC8vIHRoZSBudW1iZXIgb2YgdGltZSBzdGVwcwogIHZlY3RvcjxpbnQ+IG51bV9saXZpbmc7ICAvLyB0aGUgbnVtYmVyIG9mIGxpdmluZyBjZWxscyAoYXQgYSB0aW1lKQogIHZlY3RvcjxpbnQ+IG51bV9kZWFkOyAgICAvLyB0aGUgbnVtYmVyIG9mIGRlYWQgY2VsbHMgKGF0IGEgdGltZSkKfTsKCnZvaWQgaW5pdGlhbGl6ZV93b3JsZCh2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJndvcmxkLCBkb3VibGUgcCkKewogIGludCBpLCBqLCBuOwoKICBuID0gd29ybGQuc2l6ZSgpOwoKICAvLyBnZW5lcmF0ZSBlYWNoIGNlbGwgdG8gYmUgYWxpdmUgd2l0aCBwcm9iYWJpbGl0eSBwCgogIGZvciAoaT0wOyBpPG47IGkrKykKICAgIGZvciAoaj0wOyBqPG47IGorKykKICAgICAgewoJaWYgKGRyYW5kNDgoKTxwKQoJICB3b3JsZFtpXVtqXSA9IDE7CgllbHNlCgkgIHdvcmxkW2ldW2pdID0gMDsKICAgICAgfQp9CgppbnQgY291bnRfbmVpZ2hib3JzKHZlY3RvcjwgdmVjdG9yPGludD4gPiAmd29ybGQsIAoJCSAgICBpbnQgaSwKCQkgICAgaW50IGosCgkJICAgIGludCBuKQp7CiAgaW50IGRpLCBkajsKICBpbnQgbnVtX25laWdoYm9ycz0wOwoKICAvLyBub3RlIHRoYXQgdGhpcyBhc3N1bWVzIHdyYXAtYXJvdW5kIHdvcmxkLCBpbiB3aGljaAogIC8vIHRoZSBsYXN0IGNlbGwgaW4gYW55IHJvdyBpcyBhIG5laWdoYm9yIG9mIHRoZSB2ZXJ5CiAgLy8gZmlyc3QgY2VsbCBpbiB0aGUgcm93OyBzaW1pbGFybHkgZm9yIHRoZSBjb2x1bW5zCgogIGZvciAoZGkgPSAtMTsgZGkgPD0gMTsgZGkrKykKICAgIGZvciAoZGogPSAtMTsgZGogPD0gMTsgZGorKykKICAgICAgaWYgKChkaSE9MCl8fChkaiE9MCkpCgludW1fbmVpZ2hib3JzICs9IHdvcmxkWyhpK2RpK24pJW5dWyhqK2RqK24pJW5dOwoKICAvLyByZXR1cm4gdGhlIG51bWJlciBvZiBuZWlnaGJvcnMKCiAgcmV0dXJuIG51bV9uZWlnaGJvcnM7ICAgICAgCn0KCnZvaWQgcHJvY2Vzc193b3JsZCh2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJm5ld193b3JsZCwKCQkgICB2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJndvcmxkKQp7CiAgaW50IGksIGo7CiAgaW50IG4gPSB3b3JsZC5zaXplKCk7CgogIC8vIGNvdW50IG5laWdoYm9ycyBvZiBldmVyeSBjZWxsLCBhbmQgZ2VuZXJhdGUgdGhlIG5ldwogIC8vIHdvcmxkIHVzaW5nIHRoZSBiYXNpYyBydWxlcyBvZiB0aGUgZ2FtZSBvZiBsaWZlCiAgLy8gLSBsaXZpbmcgY2VsbCBkaWVzIGlmIGxlc3MgdGhhbiAyIGxpdmluZyBuZWlnaGJvcnMKICAvLyAtIGxpdmluZyBjZWxsIGRpZXMgaWYgbW9yZSB0aGFuIDMgbGl2aW5nIG5laWdoYm9ycwogIC8vIC0gZGVhZCBjZWxsIGNoYW5nZXMgdG8gbGl2aW5nIGlmIGV4YWN0bHkgMyBuZWlnaGJvcnMKICAvLyAtIG90aGVyd2lzZSwgbm8gY2hhbmdlCgogIGZvciAoaT0wOyBpPG47IGkrKykKICAgIGZvciAoaj0wOyBqPG47IGorKykKICAgICAgewoJaW50IG51bV9uZWlnaGJvcnMgPSBjb3VudF9uZWlnaGJvcnMod29ybGQsIGksIGosIG4pOwoKCS8vIHRoZXNlIGNvbmRpdGlvbnMgaW1wbGVtZW50IHRoZSBydWxlcwoJCglpZiAod29ybGRbaV1bal09PTEpIC8vIGxpdmluZyBjZWxsCgkgIHsKCSAgICBpZiAobnVtX25laWdoYm9yczwyKQoJICAgICAgbmV3X3dvcmxkW2ldW2pdID0gMDsgICAvLyBkaWVkIGJlY2F1c2Ugb2YgdW5kZXJwb3B1bGF0aW9uCgkgICAgZWxzZQoJICAgICAgaWYgKG51bV9uZWlnaGJvcnM+MykKCQluZXdfd29ybGRbaV1bal0gPSAwOyAvLyBkaWVkIGJlY2F1c2Ugb2Ygb3ZlcmNyb3dkaW5nCgkgICAgICBlbHNlCgkJbmV3X3dvcmxkW2ldW2pdID0gMTsgLy8gY2VsbCBnb2VzIG9uIGxpdmluZwoJICB9CgllbHNlCgkgIGlmIChudW1fbmVpZ2hib3JzPT0zKSAvLyBkZWFkIGNlbGwKCSAgICBuZXdfd29ybGRbaV1bal0gPSAxOyAvLyByZXByb2R1Y3Rpb24gKG5ldyBjZWxsKQoJICBlbHNlCgkgICAgbmV3X3dvcmxkW2ldW2pdID0gMDsgLy8gcmVtYWlucyBlbXB0eSBjZWxsCiAgICAgIH0KfQoKdm9pZCBkaXNwbGF5X3dvcmxkKHZlY3RvcjwgdmVjdG9yPGludD4gPiAmd29ybGQpCnsKICBpbnQgaSwgajsKICBpbnQgbiA9IHdvcmxkLnNpemUoKTsKICBpbnQgbnVtX2xpdmluZyA9IDA7CiAgaW50IG51bV9kZWFkID0gMDsKCiAgLy8gc2hvdyB0aGUgY29udGVudCBvZiBlYWNoIGNlbGwgaW4gYSByZWFzb25hYmx5IHJlYWRhYmxlIGZvcm1hdAogIC8vIChhcyBhIG1hdHJpeCB3aXRoICogZGVub3RpbmcgYSBsaXZpbmcgY2VsbCkKCiAgZm9yIChpPTA7IGk8bjsgaSsrKQogICAgewogICAgICBmb3IgKGo9MDsgajxuOyBqKyspCglpZiAod29ybGRbaV1bal09PTEpCgkgIHsKCSAgICBjb3V0IDw8ICIqICI7CgkgICAgbnVtX2xpdmluZysrOwoJICB9CgllbHNlCgkgIHsKCSAgICBjb3V0IDw8ICIgICI7CgkgICAgbnVtX2RlYWQrKzsKCSAgfQogICAgICBjb3V0IDw8IGVuZGw7CiAgICB9CgogIGNvdXQgPDwgZW5kbDsKICBjb3V0IDw8ICJudW1fbGl2aW5nID0gIiA8PCBudW1fbGl2aW5nIDw8IGVuZGw7CiAgY291dCA8PCAibnVtX2RlYWQgPSAgICIgPDwgbnVtX2RlYWQgPDwgZW5kbDsKICBjb3V0IDw8IGVuZGw7Cn0KCnZvaWQgY29tcHV0ZV9zdGF0aXN0aWNzKHZlY3RvcjwgdmVjdG9yPGludD4gPiAmd29ybGQsCgkJCXN0YXRzX3QgJnN0YXRzLAoJCQlpbnQgdCkKewogIGludCBpLGo7CiAgaW50IG4gPSB3b3JsZC5zaXplKCk7CgogIC8vIHRoZSBudW1iZXIgb2YgbGl2aW5nIGFuZCBkZWFkIGNlbGxzIGlzIDAgaW5pdGlhbGx5CgogIHN0YXRzLm51bV9saXZpbmdbdF0gPSAwOwogIHN0YXRzLm51bV9kZWFkW3RdICAgPSAwOwoKICAvLyBkbyB0aGUgY291bnRzCiAgCiAgZm9yIChpPTA7IGk8bjsgaSsrKQogICAgZm9yIChqPTA7IGo8bjsgaisrKQogICAgICBpZiAod29ybGRbaV1bal09PTEpCglzdGF0cy5udW1fbGl2aW5nW3RdKys7CiAgICAgIGVsc2UKCXN0YXRzLm51bV9kZWFkW3RdKys7Cn0KCnZvaWQgcnVuX3NpbXVsYXRpb24ocGFyYW1zX3QgJnBhcmFtcywgc3RhdHNfdCAmc3RhdHMpCnsKICBpbnQgaSwgdCA9IDA7CiAgdmVjdG9yPCB2ZWN0b3I8aW50PiA+IHdvcmxkKHBhcmFtcy53b3JsZF9zaXplKTsKICB2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gbmV3X3dvcmxkKHBhcmFtcy53b3JsZF9zaXplKTsKCiAgLy8gc3RvcmUgdGhlIG51bWJlciBvZiBzdGVwcyBhbmQgbWFrZSBzdXJlIHRoYXQgdGhlcmUKICAvLyBpcyBlbm91Z2ggc3BhY2UgdG8gc3RvcmUgdGhlIHN0YXRpc3RpY3MgCgogIHN0YXRzLm51bV9zdGVwcz1wYXJhbXMubWF4X3Q7CiAgc3RhdHMubnVtX2xpdmluZy5yZXNpemUocGFyYW1zLm1heF90KzEpOwogIHN0YXRzLm51bV9kZWFkLnJlc2l6ZShwYXJhbXMubWF4X3QrMSk7CgogIC8vIHJ1bnMgdGhlIHNpbXVsYXRpb24KCiAgZm9yIChpPTA7IGk8cGFyYW1zLndvcmxkX3NpemU7IGkrKykKICAgIHsKICAgICAgd29ybGRbaV0ucmVzaXplKHBhcmFtcy53b3JsZF9zaXplKTsKICAgICAgbmV3X3dvcmxkW2ldLnJlc2l6ZShwYXJhbXMud29ybGRfc2l6ZSk7CiAgICB9CgogIC8vIGluaXRpYWxpemUgdGhlIHdvcmxkCiAgCiAgaW5pdGlhbGl6ZV93b3JsZCh3b3JsZCwgcGFyYW1zLmluaXRpYWxfcHJvcG9ydGlvbik7CgogIC8vIGNvbXB1dGUgc3RhdGlzdGljcyBmb3IgdGhlIGN1cnJlbnQgdGltZSBzdGVwIChub3cgdD0wKQoKICBjb21wdXRlX3N0YXRpc3RpY3Mod29ybGQsIHN0YXRzLCB0KTsKCiAgLy8gcHJpbnQgb3V0IHRoZSBpbml0aWFsIHdvcmxkIAoKICBpZiAocGFyYW1zLmRpc3BsYXkpCiAgICB7CiAgICAgIGNvdXQgPDwgIi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0iIDw8IGVuZGw7CiAgICAgIGNvdXQgPDwgIklOSVRJQUwgV09STEQiIDw8IGVuZGwgPDwgZW5kbDsKICAgICAgZGlzcGxheV93b3JsZCh3b3JsZCk7CiAgICB9CgogIGZvciAodD0xOyB0PD1wYXJhbXMubWF4X3Q7IHQrKykKICAgIHsKICAgICAgLy8gY3JlYXRlIG5ldyB3b3JsZCB1c2luZyB0aGUgb2xkIHdvcmxkIGFuZCB0aGUgcnVsZXMKICAgICAgCiAgICAgIHByb2Nlc3Nfd29ybGQobmV3X3dvcmxkLCB3b3JsZCk7CgogICAgICAvLyBuZXcgd29ybGQgYmVjb21lcyBjdXJyZW50IHdvcmxkCgogICAgICBzd2FwKHdvcmxkLCBuZXdfd29ybGQpOwoKICAgICAgLy8gY29tcHV0ZSB0aGUgc3RhdGlzdGljcwoKICAgICAgY29tcHV0ZV9zdGF0aXN0aWNzKHdvcmxkLCBzdGF0cywgdCk7CgogICAgICAvLyBwcmludCBvdXQgdGhlIHdvcmxkIChvbmNlIGluIGVhY2ggcGFyYW1zLmRlbGF5IHN0ZXBzKQoKICAgICAgaWYgKCgodC0xKSVwYXJhbXMuZGVsYXk9PTApJiYocGFyYW1zLmRpc3BsYXkpKQoJewoJICBjb3V0IDw8ICItLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tIiA8PCBlbmRsOwoJICBjb3V0IDw8ICJXT1JMRCBBVCBUSU1FICIgPDwgdCA8PCBlbmRsIDw8IGVuZGw7CgkgIGRpc3BsYXlfd29ybGQod29ybGQpOwoJfQogICAgfQp9Cgp2b2lkIHByb2Nlc3Nfc3RhdGlzdGljcyh2ZWN0b3I8c3RhdHNfdD4gc3RhdHMpCnsKICBpbnQgcnVuOwogIGludCB0OwogIGludCBudW1fcnVucyA9IHN0YXRzLnNpemUoKTsKICBpbnQgbWF4X3QgICAgPSBzdGF0c1swXS5udW1fc3RlcHM7CgogIGNvdXQgPDwgIkZpbmFsIHN0YXRpc3RpY3Mgb3ZlciAiIDw8IG51bV9ydW5zIDw8ICIgcnVuczoiIDw8IGVuZGw7CgogIC8vIHByb2Nlc3Mgc3RhdGlzdGljcyBmb3IgYWxsIHRpbWUgc3RlcHMgYW5kIHJ1bnMKICAvLyAoYXZlcmFnaW5nIHRoZSBudW1iZXJzIGZvciBlYWNoIHRpbWUgc3RlcCBvdmVyCiAgLy8gdGhlIHJ1bnMpCgogIGZvciAodD0wOyB0PD1tYXhfdDsgdCsrKQogICAgewogICAgICBkb3VibGUgYXZnX251bV9saXZpbmcgPSAwOwogICAgICBkb3VibGUgYXZnX251bV9kZWFkICAgPSAwOwoKICAgICAgZm9yIChydW49MDsgcnVuPG51bV9ydW5zOyBydW4rKykKCXsKCSAgYXZnX251bV9saXZpbmcgKz0gc3RhdHNbcnVuXS5udW1fbGl2aW5nW3RdOwoJICBhdmdfbnVtX2RlYWQgICArPSBzdGF0c1tydW5dLm51bV9kZWFkW3RdOwoJfQogICAgICAKICAgICAgYXZnX251bV9saXZpbmcgLz0gbnVtX3J1bnM7CiAgICAgIGF2Z19udW1fZGVhZCAgIC89IG51bV9ydW5zOwogICAgICAKICAgICAgY291dCA8PCB0IDw8ICIgIiA8PCBhdmdfbnVtX2xpdmluZyA8PCAiICIgPDwgYXZnX251bV9kZWFkIDw8ICIgIjsKICAgICAgY291dCA8PCAiICIgPDwgYXZnX251bV9saXZpbmcqMTAwLyhhdmdfbnVtX2xpdmluZythdmdfbnVtX2RlYWQpIDw8ICIgIjsKICAgICAgY291dCA8PCAiICIgPDwgYXZnX251bV9kZWFkKjEwMC8oYXZnX251bV9saXZpbmcrYXZnX251bV9kZWFkKSA8PCAiICI7CiAgICAgIGNvdXQgPDwgZW5kbDsKICAgIH0KfQoKaW50IG1haW4oKQp7CiAgaW50IHJ1bjsKICBwYXJhbXNfdCBwYXJhbXM7CiAgdmVjdG9yPHN0YXRzX3Q+IHN0YXRzOwoKICAvLyBpbml0aWFsaXplIHJhbmRvbSBudW1iZXIgZ2VuZXJhdG9yCgogIHNyYW5kNDgoMTIzKTsKCiAgLy8gcmVhZCB1c2VyIHBhcmFtZXRlcnMKCiAgY2luID4+IHBhcmFtcy53b3JsZF9zaXplOwogIGNpbiA+PiBwYXJhbXMuaW5pdGlhbF9wcm9wb3J0aW9uOwogIGNpbiA+PiBwYXJhbXMubWF4X3Q7CiAgY2luID4+IHBhcmFtcy5kZWxheTsKICBjaW4gPj4gcGFyYW1zLm51bV9ydW5zOwogIGNpbiA+PiBwYXJhbXMuZGlzcGxheTsKICAKICAvLyBhZGp1c3QgcGFyYW1ldGVycyBpZiBuZWNlc3NhcnkKICAKICBpZiAocGFyYW1zLndvcmxkX3NpemU8MSkKICAgIHBhcmFtcy53b3JsZF9zaXplPTE7CiAgaWYgKHBhcmFtcy5pbml0aWFsX3Byb3BvcnRpb248MCkKICAgIHBhcmFtcy5pbml0aWFsX3Byb3BvcnRpb249MDsKICBpZiAocGFyYW1zLmluaXRpYWxfcHJvcG9ydGlvbj4xKQogICAgcGFyYW1zLmluaXRpYWxfcHJvcG9ydGlvbj0xOwogIGlmIChwYXJhbXMubWF4X3Q8MSkKICAgIHBhcmFtcy5tYXhfdD0xOwogIGlmIChwYXJhbXMuZGVsYXk8MSkKICAgIHBhcmFtcy5kZWxheT0xOwogIGlmIChwYXJhbXMubnVtX3J1bnM8MSkKICAgIHBhcmFtcy5udW1fcnVucz0xOwogIAogIC8vIHByaW50IG91dCBwYXJhbWV0ZXJzCiAgCiAgY291dCA8PCAiV29ybGQgc2l6ZTogICAgICAgICAiIDw8IHBhcmFtcy53b3JsZF9zaXplIDw8IGVuZGw7CiAgY291dCA8PCAiSW5pdGlhbCBwcm9wb3J0aW9uOiAiIDw8IHBhcmFtcy5pbml0aWFsX3Byb3BvcnRpb24gPDwgZW5kbDsKICBjb3V0IDw8ICJNYXhpbXVtIHRpbWUgc3RlcHM6ICIgPDwgcGFyYW1zLm1heF90IDw8IGVuZGw7CiAgY291dCA8PCAiUmVwb3J0aW5nIHBlcmlvZDogICAiIDw8IHBhcmFtcy5kZWxheSA8PCBlbmRsOyAKICBjb3V0IDw8ICJOdW1iZXIgb2YgcnVuczogICAgICIgPDwgcGFyYW1zLm51bV9ydW5zIDw8IGVuZGw7CiAgY291dCA8PCAiRGlzcGxheSB3b3JsZDogICAgICAiIDw8IHBhcmFtcy5kaXNwbGF5IDw8IGVuZGw7CiAgY291dCA8PCBlbmRsOwoKICAvLyBydW4gdGhlIGdhbWUgb2YgbGlmZSBzaW11bGF0aW9uCgogIHN0YXRzLnJlc2l6ZShwYXJhbXMubnVtX3J1bnMpOyAgLy8gcmVzaXplIHRoZSB2ZWN0b3IgZm9yIHN0YXRpc3RpY3MKICBmb3IgKHJ1bj0wOyBydW48cGFyYW1zLm51bV9ydW5zOyBydW4rKykKICAgIHsKICAgICAgY291dCA8PCAiRXhlY3V0aW5nIHJ1biAiIDw8IHJ1biA8PCBlbmRsOwogICAgICBydW5fc2ltdWxhdGlvbihwYXJhbXMsIHN0YXRzW3J1bl0pOyAgIC8vIGV4ZWN1dGUgb25lIHJ1bgogICAgfQogIGNvdXQgPDwgZW5kbDsKCiAgLy8gcHJvY2VzcyBzdGF0aXN0aWNzCgogIHByb2Nlc3Nfc3RhdGlzdGljcyhzdGF0cyk7CgogIC8vIHJldHVybiAwIGZyb20gbWFpbgoKICByZXR1cm4gMDsKfQo=

MjAKMC4yCjEwMAoxCjEwMAowCg==

20
0.2
100
1
100
0