// Simple Wireworld iteration program
// Copyright Mark Owen, September 2004
// E-mail: mail -at- quinapalus.com

// Takes pattern on stdin, emits pattern n generations later on stdout,
// n specified as single command-line argument. Sets borders to blank.

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

#define SZ 1024
char board[SZ*SZ];
int lists[4][SZ*SZ];
int llen[4];
int he,ta,wi,nh;

#define addlist(l,i) lists[l][llen[l]++]=i

setlist(int l,char c) {
int i,j;
int *p;

p=lists[l];
j=llen[l];
for(i=0;i<j;i++) board[*p++]=c;
}

main(int argc,char*argv[]) {
int i,j;
int t,u,v;
int x,y;
int ng,g;
char *p;
char s0[SZ+10];

if(argc!=2) {fprintf(stderr,"Usage: %s <count>\n",argv[0]); return 1;}
u=sscanf(argv[1],"%d",&ng);
if(u!=1||ng<0) {fprintf(stderr,"Usage: %s <count>\n",argv[0]); return 1;}

for(i=0;i<SZ*SZ;i++)
  board[i]=' ';
llen[0]=llen[1]=llen[2]=llen[3]=0;
he=0;
ta=1;
wi=2;
nh=3;

p=fgets(s0,SZ+10,stdin);
if(p==NULL) {fprintf(stderr,"File error\n"); return 1;}
i=sscanf(s0,"%d %d",&x,&y);
if(i!=2) return 1;
fprintf(stderr,"%d %d\n",x,y);
if(x>SZ||y>SZ) {fprintf(stderr,"Board too big\n"); return 1;}
p=fgets(s0,SZ+10,stdin);
if(p==NULL) {fprintf(stderr,"File error\n"); return 1;}
for(j=1;j<y-1;j++) {
  p=fgets(s0,SZ+10,stdin);
  if(p==NULL) {fprintf(stderr,"File error\n"); return 1;}
  for(i=1;i<x-1;i++) {
    t=i+j*SZ;
    switch(s0[i]) {
      case' ':board[t]=' ';break;
      case'@':board[t]='@';addlist(wi,t);addlist(he,t);break;
      case'~':board[t]='~';addlist(wi,t);addlist(ta,t);break;
      case'#':board[t]='#';addlist(wi,t);              break;
      default:fprintf(stderr,"Bad character %c\n",s0[i]);return 1;break;
      }
    }
  }
fprintf(stderr,"Read board\n");
for(g=0;g<ng;g++) {
  llen[nh]=0;
  for(i=0;i<llen[wi];i++) {
    u=lists[wi][i];
    p=board+u;
    if(*p=='#') {
      t=(p[-SZ-1]=='@')+
        (p[-SZ  ]=='@')+
        (p[-SZ+1]=='@')+
        (p[   -1]=='@')+
        (p[   +1]=='@')+
        (p[ SZ-1]=='@')+
        (p[ SZ  ]=='@')+
        (p[ SZ+1]=='@');
      if(t==1||t==2) addlist(nh,u);
      }
    }
  setlist(ta,'#');
  setlist(he,'~');
  setlist(nh,'@');
  t=ta; ta=he; he=nh; nh=t;
  }
printf("%d %d\n",x,y);
for(j=0;j<y;j++) {
  for(i=0;i<x;i++) printf("%c",board[i+j*SZ]);
  printf("\n");
  }
return 0;
}