#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>

#define N 512

/* Règles de transition données par un octet:

   Etant donné les états 0/1 de la cellule et de ses deux voisins,
   un bit donne l'état suivant de la cellule.

   On code en binaire: (left here right) avec left en poids fort,
   ce qui donne un entier n entre 0 et 7. On accède au bit 1<<n
   de l'octet représentant la règle pour avoir le résultat de la
   transition.
 */

bool transition (char rule, bool left, bool here, bool right) {
  int n = (left<<2)+(here<<1)+right;
  return ((rule&(1<<n))!=0);
}

void step (int rule, bool prev[N], bool next[N]) {
  int j;
  for (j=0; j<N; j++) {
    next[j]=transition(rule,prev[(N+j-1)%N],prev[j],prev[(j+1)%N]);
  }
}

void print_line(bool cur[N]) {
  int j;
  assert((N&7)==0);
  for (j=0; j<N; j+=8) {
    printf("%c",128*cur[j]+64*cur[j+1]+32*cur[j+2]+16*cur[j+3]+
                8*cur[j+4]+4*cur[j+5]+2*cur[j+6]+cur[j+7]);
  }
}

int main(int argc, char** argv) {

  int j,k;

  if (argc==1) {
    printf("Usage: %s <int>\n",argv[0]);
    exit(1);
  }

  int rule = atoi(argv[1]);

  assert(transition(4,false,true,false));
  assert(transition(7,false,true,false));
  assert(transition(64+4,true,true,false));
  assert(!transition(64+4,true,true,true));
  assert(transition(128,true,true,true));
  assert(!transition(128,true,true,false));

  bool state[2][N];
  bool cur=0;
  printf("P4\n%d %d\n",N,N);
  for (j=0; j<N; j++) state[0][j]=(j==N/2);
  for (k=0; k<N; k++) {
    print_line(state[cur]);
    step(rule,state[cur],state[!cur]);
    cur = !cur;
  }

}