#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)
  vector<int> num_changed; // the number of changed 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,
			vector< vector<int> > &old_world,
			stats_t &stats,
			int t)
{
  int i,j;
  int n = world.size();
 
  // the number of living and dead cells is 0 initially, 
  // and so is the number of changed cells
 
  stats.num_living[t]  = 0;
  stats.num_dead[t]    = 0;
  stats.num_changed[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]++;
 
	if (world[i][j]!=old_world[i][j])
	  stats.num_changed[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);
  stats.num_changed.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, 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, new_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;
      double avg_num_changed = 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_changed += stats[run].num_changed[t];
	}
 
      avg_num_living  /= num_runs;
      avg_num_dead    /= num_runs;
      avg_num_changed /= 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 << " " << avg_num_changed*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+IG51bV9kZWFkOyAgICAvLyB0aGUgbnVtYmVyIG9mIGRlYWQgY2VsbHMgKGF0IGEgdGltZSkKICB2ZWN0b3I8aW50PiBudW1fY2hhbmdlZDsgLy8gdGhlIG51bWJlciBvZiBjaGFuZ2VkIGNlbGxzIChhdCBhIHRpbWUpCn07Cgp2b2lkIGluaXRpYWxpemVfd29ybGQodmVjdG9yPCB2ZWN0b3I8aW50PiA+ICZ3b3JsZCwgZG91YmxlIHApCnsKICBpbnQgaSwgaiwgbjsKCiAgbiA9IHdvcmxkLnNpemUoKTsKCiAgLy8gZ2VuZXJhdGUgZWFjaCBjZWxsIHRvIGJlIGFsaXZlIHdpdGggcHJvYmFiaWxpdHkgcAoKICBmb3IgKGk9MDsgaTxuOyBpKyspCiAgICBmb3IgKGo9MDsgajxuOyBqKyspCiAgICAgIHsKCWlmIChkcmFuZDQ4KCk8cCkKCSAgd29ybGRbaV1bal0gPSAxOwoJZWxzZQoJICB3b3JsZFtpXVtqXSA9IDA7CiAgICAgIH0KfQoKaW50IGNvdW50X25laWdoYm9ycyh2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJndvcmxkLCAKCQkgICAgaW50IGksCgkJICAgIGludCBqLAoJCSAgICBpbnQgbikKewogIGludCBkaSwgZGo7CiAgaW50IG51bV9uZWlnaGJvcnM9MDsKCiAgLy8gbm90ZSB0aGF0IHRoaXMgYXNzdW1lcyB3cmFwLWFyb3VuZCB3b3JsZCwgaW4gd2hpY2gKICAvLyB0aGUgbGFzdCBjZWxsIGluIGFueSByb3cgaXMgYSBuZWlnaGJvciBvZiB0aGUgdmVyeQogIC8vIGZpcnN0IGNlbGwgaW4gdGhlIHJvdzsgc2ltaWxhcmx5IGZvciB0aGUgY29sdW1ucwoKICBmb3IgKGRpID0gLTE7IGRpIDw9IDE7IGRpKyspCiAgICBmb3IgKGRqID0gLTE7IGRqIDw9IDE7IGRqKyspCiAgICAgIGlmICgoZGkhPTApfHwoZGohPTApKQoJbnVtX25laWdoYm9ycyArPSB3b3JsZFsoaStkaStuKSVuXVsoaitkaituKSVuXTsKCiAgLy8gcmV0dXJuIHRoZSBudW1iZXIgb2YgbmVpZ2hib3JzCgogIHJldHVybiBudW1fbmVpZ2hib3JzOyAgICAgIAp9Cgp2b2lkIHByb2Nlc3Nfd29ybGQodmVjdG9yPCB2ZWN0b3I8aW50PiA+ICZuZXdfd29ybGQsCgkJICAgdmVjdG9yPCB2ZWN0b3I8aW50PiA+ICZ3b3JsZCkKewogIGludCBpLCBqOwogIGludCBuID0gd29ybGQuc2l6ZSgpOwoKICAvLyBjb3VudCBuZWlnaGJvcnMgb2YgZXZlcnkgY2VsbCwgYW5kIGdlbmVyYXRlIHRoZSBuZXcKICAvLyB3b3JsZCB1c2luZyB0aGUgYmFzaWMgcnVsZXMgb2YgdGhlIGdhbWUgb2YgbGlmZQogIC8vIC0gbGl2aW5nIGNlbGwgZGllcyBpZiBsZXNzIHRoYW4gMiBsaXZpbmcgbmVpZ2hib3JzCiAgLy8gLSBsaXZpbmcgY2VsbCBkaWVzIGlmIG1vcmUgdGhhbiAzIGxpdmluZyBuZWlnaGJvcnMKICAvLyAtIGRlYWQgY2VsbCBjaGFuZ2VzIHRvIGxpdmluZyBpZiBleGFjdGx5IDMgbmVpZ2hib3JzCiAgLy8gLSBvdGhlcndpc2UsIG5vIGNoYW5nZQoKICBmb3IgKGk9MDsgaTxuOyBpKyspCiAgICBmb3IgKGo9MDsgajxuOyBqKyspCiAgICAgIHsKCWludCBudW1fbmVpZ2hib3JzID0gY291bnRfbmVpZ2hib3JzKHdvcmxkLCBpLCBqLCBuKTsKCgkvLyB0aGVzZSBjb25kaXRpb25zIGltcGxlbWVudCB0aGUgcnVsZXMKCQoJaWYgKHdvcmxkW2ldW2pdPT0xKSAvLyBsaXZpbmcgY2VsbAoJICB7CgkgICAgaWYgKG51bV9uZWlnaGJvcnM8MikKCSAgICAgIG5ld193b3JsZFtpXVtqXSA9IDA7ICAgLy8gZGllZCBiZWNhdXNlIG9mIHVuZGVycG9wdWxhdGlvbgoJICAgIGVsc2UKCSAgICAgIGlmIChudW1fbmVpZ2hib3JzPjMpCgkJbmV3X3dvcmxkW2ldW2pdID0gMDsgLy8gZGllZCBiZWNhdXNlIG9mIG92ZXJjcm93ZGluZwoJICAgICAgZWxzZQoJCW5ld193b3JsZFtpXVtqXSA9IDE7IC8vIGNlbGwgZ29lcyBvbiBsaXZpbmcKCSAgfQoJZWxzZQoJICBpZiAobnVtX25laWdoYm9ycz09MykgLy8gZGVhZCBjZWxsCgkgICAgbmV3X3dvcmxkW2ldW2pdID0gMTsgLy8gcmVwcm9kdWN0aW9uIChuZXcgY2VsbCkKCSAgZWxzZQoJICAgIG5ld193b3JsZFtpXVtqXSA9IDA7IC8vIHJlbWFpbnMgZW1wdHkgY2VsbAogICAgICB9Cn0KCnZvaWQgZGlzcGxheV93b3JsZCh2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJndvcmxkKQp7CiAgaW50IGksIGo7CiAgaW50IG4gPSB3b3JsZC5zaXplKCk7CiAgaW50IG51bV9saXZpbmcgPSAwOwogIGludCBudW1fZGVhZCA9IDA7CgogIC8vIHNob3cgdGhlIGNvbnRlbnQgb2YgZWFjaCBjZWxsIGluIGEgcmVhc29uYWJseSByZWFkYWJsZSBmb3JtYXQKICAvLyAoYXMgYSBtYXRyaXggd2l0aCAqIGRlbm90aW5nIGEgbGl2aW5nIGNlbGwpCgogIGZvciAoaT0wOyBpPG47IGkrKykKICAgIHsKICAgICAgZm9yIChqPTA7IGo8bjsgaisrKQoJaWYgKHdvcmxkW2ldW2pdPT0xKQoJICB7CgkgICAgY291dCA8PCAiKiAiOwoJICAgIG51bV9saXZpbmcrKzsKCSAgfQoJZWxzZQoJICB7CgkgICAgY291dCA8PCAiICAiOwoJICAgIG51bV9kZWFkKys7CgkgIH0KICAgICAgY291dCA8PCBlbmRsOwogICAgfQoKICBjb3V0IDw8IGVuZGw7CiAgY291dCA8PCAibnVtX2xpdmluZyA9ICIgPDwgbnVtX2xpdmluZyA8PCBlbmRsOwogIGNvdXQgPDwgIm51bV9kZWFkID0gICAiIDw8IG51bV9kZWFkIDw8IGVuZGw7CiAgY291dCA8PCBlbmRsOwp9Cgp2b2lkIGNvbXB1dGVfc3RhdGlzdGljcyh2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJndvcmxkLAoJCQl2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJm9sZF93b3JsZCwKCQkJc3RhdHNfdCAmc3RhdHMsCgkJCWludCB0KQp7CiAgaW50IGksajsKICBpbnQgbiA9IHdvcmxkLnNpemUoKTsKCiAgLy8gdGhlIG51bWJlciBvZiBsaXZpbmcgYW5kIGRlYWQgY2VsbHMgaXMgMCBpbml0aWFsbHksIAogIC8vIGFuZCBzbyBpcyB0aGUgbnVtYmVyIG9mIGNoYW5nZWQgY2VsbHMKCiAgc3RhdHMubnVtX2xpdmluZ1t0XSAgPSAwOwogIHN0YXRzLm51bV9kZWFkW3RdICAgID0gMDsKICBzdGF0cy5udW1fY2hhbmdlZFt0XSA9IDA7CgogIC8vIGRvIHRoZSBjb3VudHMKICAKICBmb3IgKGk9MDsgaTxuOyBpKyspCiAgICBmb3IgKGo9MDsgajxuOyBqKyspCiAgICAgIHsKCWlmICh3b3JsZFtpXVtqXT09MSkKCSAgc3RhdHMubnVtX2xpdmluZ1t0XSsrOwoJZWxzZQoJICBzdGF0cy5udW1fZGVhZFt0XSsrOwoJCglpZiAod29ybGRbaV1bal0hPW9sZF93b3JsZFtpXVtqXSkKCSAgc3RhdHMubnVtX2NoYW5nZWRbdF0rKzsKICAgICAgfQp9Cgp2b2lkIHJ1bl9zaW11bGF0aW9uKHBhcmFtc190ICZwYXJhbXMsIHN0YXRzX3QgJnN0YXRzKQp7CiAgaW50IGksIHQgPSAwOwogIHZlY3RvcjwgdmVjdG9yPGludD4gPiB3b3JsZChwYXJhbXMud29ybGRfc2l6ZSk7CiAgdmVjdG9yPCB2ZWN0b3I8aW50PiA+IG5ld193b3JsZChwYXJhbXMud29ybGRfc2l6ZSk7CgogIC8vIHN0b3JlIHRoZSBudW1iZXIgb2Ygc3RlcHMgYW5kIG1ha2Ugc3VyZSB0aGF0IHRoZXJlCiAgLy8gaXMgZW5vdWdoIHNwYWNlIHRvIHN0b3JlIHRoZSBzdGF0aXN0aWNzIAoKICBzdGF0cy5udW1fc3RlcHM9cGFyYW1zLm1heF90OwogIHN0YXRzLm51bV9saXZpbmcucmVzaXplKHBhcmFtcy5tYXhfdCsxKTsKICBzdGF0cy5udW1fZGVhZC5yZXNpemUocGFyYW1zLm1heF90KzEpOwogIHN0YXRzLm51bV9jaGFuZ2VkLnJlc2l6ZShwYXJhbXMubWF4X3QrMSk7CgogIC8vIHJ1bnMgdGhlIHNpbXVsYXRpb24KCiAgZm9yIChpPTA7IGk8cGFyYW1zLndvcmxkX3NpemU7IGkrKykKICAgIHsKICAgICAgd29ybGRbaV0ucmVzaXplKHBhcmFtcy53b3JsZF9zaXplKTsKICAgICAgbmV3X3dvcmxkW2ldLnJlc2l6ZShwYXJhbXMud29ybGRfc2l6ZSk7CiAgICB9CgogIC8vIGluaXRpYWxpemUgdGhlIHdvcmxkCiAgCiAgaW5pdGlhbGl6ZV93b3JsZCh3b3JsZCwgcGFyYW1zLmluaXRpYWxfcHJvcG9ydGlvbik7CgogIC8vIGNvbXB1dGUgc3RhdGlzdGljcyBmb3IgdGhlIGN1cnJlbnQgdGltZSBzdGVwIChub3cgdD0wKQoKICBjb21wdXRlX3N0YXRpc3RpY3Mod29ybGQsIHdvcmxkLCBzdGF0cywgdCk7CgogIC8vIHByaW50IG91dCB0aGUgaW5pdGlhbCB3b3JsZCAKCiAgaWYgKHBhcmFtcy5kaXNwbGF5KQogICAgewogICAgICBjb3V0IDw8ICItLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tIiA8PCBlbmRsOwogICAgICBjb3V0IDw8ICJJTklUSUFMIFdPUkxEIiA8PCBlbmRsIDw8IGVuZGw7CiAgICAgIGRpc3BsYXlfd29ybGQod29ybGQpOwogICAgfQoKICBmb3IgKHQ9MTsgdDw9cGFyYW1zLm1heF90OyB0KyspCiAgICB7CiAgICAgIC8vIGNyZWF0ZSBuZXcgd29ybGQgdXNpbmcgdGhlIG9sZCB3b3JsZCBhbmQgdGhlIHJ1bGVzCiAgICAgIAogICAgICBwcm9jZXNzX3dvcmxkKG5ld193b3JsZCwgd29ybGQpOwoKICAgICAgLy8gbmV3IHdvcmxkIGJlY29tZXMgY3VycmVudCB3b3JsZAoKICAgICAgc3dhcCh3b3JsZCwgbmV3X3dvcmxkKTsKCiAgICAgIC8vIGNvbXB1dGUgdGhlIHN0YXRpc3RpY3MKCiAgICAgIGNvbXB1dGVfc3RhdGlzdGljcyh3b3JsZCwgbmV3X3dvcmxkLCBzdGF0cywgdCk7CgogICAgICAvLyBwcmludCBvdXQgdGhlIHdvcmxkIChvbmNlIGluIGVhY2ggcGFyYW1zLmRlbGF5IHN0ZXBzKQoKICAgICAgaWYgKCgodC0xKSVwYXJhbXMuZGVsYXk9PTApJiYocGFyYW1zLmRpc3BsYXkpKQoJewoJICBjb3V0IDw8ICItLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tIiA8PCBlbmRsOwoJICBjb3V0IDw8ICJXT1JMRCBBVCBUSU1FICIgPDwgdCA8PCBlbmRsIDw8IGVuZGw7CgkgIGRpc3BsYXlfd29ybGQod29ybGQpOwoJfQogICAgfQp9Cgp2b2lkIHByb2Nlc3Nfc3RhdGlzdGljcyh2ZWN0b3I8c3RhdHNfdD4gc3RhdHMpCnsKICBpbnQgcnVuOwogIGludCB0OwogIGludCBudW1fcnVucyA9IHN0YXRzLnNpemUoKTsKICBpbnQgbWF4X3QgICAgPSBzdGF0c1swXS5udW1fc3RlcHM7CgogIGNvdXQgPDwgIkZpbmFsIHN0YXRpc3RpY3Mgb3ZlciAiIDw8IG51bV9ydW5zIDw8ICIgcnVuczoiIDw8IGVuZGw7CgogIC8vIHByb2Nlc3Mgc3RhdGlzdGljcyBmb3IgYWxsIHRpbWUgc3RlcHMgYW5kIHJ1bnMKICAvLyAoYXZlcmFnaW5nIHRoZSBudW1iZXJzIGZvciBlYWNoIHRpbWUgc3RlcCBvdmVyCiAgLy8gdGhlIHJ1bnMpCgogIGZvciAodD0wOyB0PD1tYXhfdDsgdCsrKQogICAgewogICAgICBkb3VibGUgYXZnX251bV9saXZpbmcgID0gMDsKICAgICAgZG91YmxlIGF2Z19udW1fZGVhZCAgICA9IDA7CiAgICAgIGRvdWJsZSBhdmdfbnVtX2NoYW5nZWQgPSAwOwoKICAgICAgZm9yIChydW49MDsgcnVuPG51bV9ydW5zOyBydW4rKykKCXsKCSAgYXZnX251bV9saXZpbmcgICs9IHN0YXRzW3J1bl0ubnVtX2xpdmluZ1t0XTsKCSAgYXZnX251bV9kZWFkICAgICs9IHN0YXRzW3J1bl0ubnVtX2RlYWRbdF07CgkgIGF2Z19udW1fY2hhbmdlZCArPSBzdGF0c1tydW5dLm51bV9jaGFuZ2VkW3RdOwoJfQogICAgICAKICAgICAgYXZnX251bV9saXZpbmcgIC89IG51bV9ydW5zOwogICAgICBhdmdfbnVtX2RlYWQgICAgLz0gbnVtX3J1bnM7CiAgICAgIGF2Z19udW1fY2hhbmdlZCAvPSBudW1fcnVuczsKICAgICAgCiAgICAgIGNvdXQgPDwgdCA8PCAiICIgPDwgYXZnX251bV9saXZpbmcgPDwgIiAiIDw8IGF2Z19udW1fZGVhZCA8PCAiICI7CiAgICAgIGNvdXQgPDwgIiAiIDw8IGF2Z19udW1fbGl2aW5nKjEwMC8oYXZnX251bV9saXZpbmcrYXZnX251bV9kZWFkKSA8PCAiICI7CiAgICAgIGNvdXQgPDwgIiAiIDw8IGF2Z19udW1fZGVhZCoxMDAvKGF2Z19udW1fbGl2aW5nK2F2Z19udW1fZGVhZCkgPDwgIiAiOwogICAgICBjb3V0IDw8ICIgIiA8PCBhdmdfbnVtX2NoYW5nZWQqMTAwLyhhdmdfbnVtX2xpdmluZythdmdfbnVtX2RlYWQpIDw8ICIgIjsKICAgICAgY291dCA8PCBlbmRsOwogICAgfQp9CgppbnQgbWFpbigpCnsKICBpbnQgcnVuOwogIHBhcmFtc190IHBhcmFtczsKICB2ZWN0b3I8c3RhdHNfdD4gc3RhdHM7CgogIC8vIGluaXRpYWxpemUgcmFuZG9tIG51bWJlciBnZW5lcmF0b3IKCiAgc3JhbmQ0OCgxMjMpOwoKICAvLyByZWFkIHVzZXIgcGFyYW1ldGVycwoKICBjaW4gPj4gcGFyYW1zLndvcmxkX3NpemU7CiAgY2luID4+IHBhcmFtcy5pbml0aWFsX3Byb3BvcnRpb247CiAgY2luID4+IHBhcmFtcy5tYXhfdDsKICBjaW4gPj4gcGFyYW1zLmRlbGF5OwogIGNpbiA+PiBwYXJhbXMubnVtX3J1bnM7CiAgY2luID4+IHBhcmFtcy5kaXNwbGF5OwogIAogIC8vIGFkanVzdCBwYXJhbWV0ZXJzIGlmIG5lY2Vzc2FyeQogIAogIGlmIChwYXJhbXMud29ybGRfc2l6ZTwxKQogICAgcGFyYW1zLndvcmxkX3NpemU9MTsKICBpZiAocGFyYW1zLmluaXRpYWxfcHJvcG9ydGlvbjwwKQogICAgcGFyYW1zLmluaXRpYWxfcHJvcG9ydGlvbj0wOwogIGlmIChwYXJhbXMuaW5pdGlhbF9wcm9wb3J0aW9uPjEpCiAgICBwYXJhbXMuaW5pdGlhbF9wcm9wb3J0aW9uPTE7CiAgaWYgKHBhcmFtcy5tYXhfdDwxKQogICAgcGFyYW1zLm1heF90PTE7CiAgaWYgKHBhcmFtcy5kZWxheTwxKQogICAgcGFyYW1zLmRlbGF5PTE7CiAgaWYgKHBhcmFtcy5udW1fcnVuczwxKQogICAgcGFyYW1zLm51bV9ydW5zPTE7CiAgCiAgLy8gcHJpbnQgb3V0IHBhcmFtZXRlcnMKICAKICBjb3V0IDw8ICJXb3JsZCBzaXplOiAgICAgICAgICIgPDwgcGFyYW1zLndvcmxkX3NpemUgPDwgZW5kbDsKICBjb3V0IDw8ICJJbml0aWFsIHByb3BvcnRpb246ICIgPDwgcGFyYW1zLmluaXRpYWxfcHJvcG9ydGlvbiA8PCBlbmRsOwogIGNvdXQgPDwgIk1heGltdW0gdGltZSBzdGVwczogIiA8PCBwYXJhbXMubWF4X3QgPDwgZW5kbDsKICBjb3V0IDw8ICJSZXBvcnRpbmcgcGVyaW9kOiAgICIgPDwgcGFyYW1zLmRlbGF5IDw8IGVuZGw7IAogIGNvdXQgPDwgIk51bWJlciBvZiBydW5zOiAgICAgIiA8PCBwYXJhbXMubnVtX3J1bnMgPDwgZW5kbDsKICBjb3V0IDw8ICJEaXNwbGF5IHdvcmxkOiAgICAgICIgPDwgcGFyYW1zLmRpc3BsYXkgPDwgZW5kbDsKICBjb3V0IDw8IGVuZGw7CgogIC8vIHJ1biB0aGUgZ2FtZSBvZiBsaWZlIHNpbXVsYXRpb24KCiAgc3RhdHMucmVzaXplKHBhcmFtcy5udW1fcnVucyk7ICAvLyByZXNpemUgdGhlIHZlY3RvciBmb3Igc3RhdGlzdGljcwogIGZvciAocnVuPTA7IHJ1bjxwYXJhbXMubnVtX3J1bnM7IHJ1bisrKQogICAgewogICAgICBjb3V0IDw8ICJFeGVjdXRpbmcgcnVuICIgPDwgcnVuIDw8IGVuZGw7CiAgICAgIHJ1bl9zaW11bGF0aW9uKHBhcmFtcywgc3RhdHNbcnVuXSk7ICAgLy8gZXhlY3V0ZSBvbmUgcnVuCiAgICB9CiAgY291dCA8PCBlbmRsOwoKICAvLyBwcm9jZXNzIHN0YXRpc3RpY3MKCiAgcHJvY2Vzc19zdGF0aXN0aWNzKHN0YXRzKTsKCiAgLy8gcmV0dXJuIDAgZnJvbSBtYWluCgogIHJldHVybiAwOwp9Cg==

MjAKMC4yCjEwMAoxCjEwMAowCg==

20
0.2
100
1
100
0