/*	Eric S. Rowland				*/
/*	http://math.rutgers.edu/~erowland	*/
/*	08/08/05				*/

import java.io.*;

class rule30 {
  public static void main(String[] args) {

    int[] row = {1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0};
    // The variable "row" is a list of rightmost cells of a row, PLUS AN APPENDED "0".  (Currently it is set at the 121 rightmost cells of row 2^40 - 1.)

    Runs(row, 512);	// This means "do 512 runs of 2^31 rows each" (or 2^40 iterations) and takes several months.
  }

// -----------------------------------------
// prints all but the last element of a list
// -----------------------------------------

  static void printRow(int[] row) {
    String rowstring = "{" + row[0];

    for(int i = 1; i < row.length - 1; i++) rowstring += ", " + row[i];

    System.out.println(rowstring + "}");
  }

// ------------------------------------------------------------------------------------
// finds the number of rightmost (excluding the rightmost entry) "1" elements in a list
// ------------------------------------------------------------------------------------

  static int lengthOfBlack(int[] row) {
    int i = row.length - 2;

    while(i > 0 && row[i] == 1) i--;

    return row.length - 2 - i;
  }

// ----------------------------------------------------------------
// finds the cells that are 2^31 rows below given (rightmost) cells
// ----------------------------------------------------------------

  static int[] Run(int[] row) {
    int length = row.length - 2;
    int i, j;

    for(i = -1; i < 2147483647; i++) for(j = 0; j < length; j++) if(row[j + 1] == 1 || row[j + 2] == 1) row[j] = 1 - row[j];

    return row;
  }

// -------------------------------------------------------------
// executes a given number of 2^31-row runs (and prints results)
// -------------------------------------------------------------

  static int[] Runs(int[] row, int runs) {
    for(int i = 1; i <= runs; i++) {
      System.out.print("Run " + i + " of " + runs + ":  ");
      row = Run(row);
      System.out.println("Length of rightmost black string is " + lengthOfBlack(row) + ".");
      printRow(row);
      System.out.println();
    }

    return row;
  }
}