#include <iostream>
#include <fstream>
#include <vector>

using namespace std;


//-----------------------------------------------------------
template <class T>
class Matrica
{
public:
	Matrica()
		{}
		
	Matrica( unsigned s, unsigned v )
		: _Podaci(s)
		{
		for( unsigned i=0; i<s; i++ )
			_Podaci[i].resize(v);
		}
		
	const vector<T>& operator[] ( unsigned i ) const
		{ return _Podaci[i]; }
		
	vector<T>& operator[] ( unsigned i )
		{ return _Podaci[i]; }
		
	unsigned Sirina() const
		{ return _Podaci.size(); }
		
	unsigned Visina() const
		{ return _Podaci.size() ? _Podaci[0].size() : 0; }
		
private:
	vector< vector<T> > _Podaci;
};

//-----------------------------------------------------------
class Jedinka;
class Tabla : public Matrica<Jedinka*>
{
public:
	Tabla( int s, int v )
		: Matrica<Jedinka*>(s,v)
		{}
		
	Tabla()
		: Matrica<Jedinka*>()
		{}		

	int BrojSuseda( int x, int y );
	int SlobodnaPolja( int x, int y, int pozicije[][2], int n, int prazna[] );
};


//-----------------------------------------------------------
class Jedinka
{
public:
	virtual bool Prezivljava( const Tabla& tabla, int& x, int& y ) = 0;
	virtual Jedinka* NovaJedinka();
	virtual char Izgled() const = 0;
};


//-----------------------------------------------------------
class Cekalica : public Jedinka
{
public:
	bool Prezivljava( const Tabla& tabla, int& x, int& y )
		{
		int bs = tabla.BrojSuseda( x, y );
		return bs>=2 && bs<=3;
		}
	Jedinka* NovaJedinka()
		{ return this; }
	char Izgled() const
		{ return 'x'; }
};
Cekalica cekalica;

//-----------------------------------------------------------
class Setalica : public Jedinka
{
public:
	bool Prezivljava( const Tabla& tabla, int& x, int& y )
		{ 
		int pozicije[][2] = { {0,1}, {0,-1}, {1,0}, {-1,0} };
		int prazna[4];
		int npraznih = tabla.SlobodnaPolja( x, y, pozicije, 4, prazna );
		if( npraznih > 0 ){
			int s = tabla.Sirina();
			int v = tabla.Visina();
			int i = random(npraznih);
			x = (x + pozicije[prazna[i]][0] + s) % s;
			y = (y + pozicije[prazna[i]][1] + v) % v;
			return true;
		}
		else
			return false; 
		}
	Jedinka* NovaJedinka()
		{
			if( random(100)<50 )
				return &cekalica;
			return this; 
		}
	char Izgled() const
		{ return 's'; }
};
Setalica setalica;

//-----------------------------------------------------------
class Skakalica : public Jedinka
{
public:
	bool Prezivljava( const Tabla& tabla, int& x, int& y )
		{ 
		int pozicije[][2] = { {-2,-2}, {-2,0}, {-2,2}, {0,-2}, {0,2}, {2,-2}, {2,0}, {2,2} };
		int prazna[8];
		int npraznih = tabla.SlobodnaPolja( x, y, pozicije, 8, prazna );
		if( npraznih > 0 ){
			int s = tabla.Sirina();
			int v = tabla.Visina();
			int i = random(npraznih);
			x = (x + pozicije[prazna[i]][0] + s) % s;
			y = (y + pozicije[prazna[i]][1] + v) % v;
			return true;
		}
		else
			return false; 
		}
	Jedinka* NovaJedinka()
		{
			if( random(100)<50 )
				return &setalica;
			return this; 
		}
	char Izgled() const
		{ return 'k'; }
};
Skakalica skakalica;

//-----------------------------------------------------------
class PraznoPolje : public Jedinka
{
public:
	bool Prezivljava( const Tabla& tabla, int& x, int& y )
		{
		int bs = tabla.BrojSuseda( x, y );
		return bs==3;
		}

	Jedinka* NovaJedinka()
		{
		int r = random(100);
		Jedinka* p;
		if( r<30 ) 
			p = &skakalica;
		else if( r<60 ) 
			p = &setalica;
		else
			p = &cekalica;
		return p;
		}
		
	char Izgled() const
		{ return '.'; }
};
PraznoPolje praznoPolje;

//-----------------------------------------------------------
int Tabla::BrojSuseda( int x, int y )
{
	int bs = 0;
	int sirina = Sirina();
	int visina = Visina();
	for( int i=-1; i<=1; i++ )
		for( int j=-1; j<=1; j++ )
			if( i || j ){
				int xx = (x+i+sirina) % sirina;
				int yy = (y+j+visina) % visina;
				if( (*this)[xx][yy] != &praznoPolje )
					bs++;
			}
	return bs;
}

int Tabla::SlobodnaPolja( int x0, int y0, int pozicije[][2], int n, int prazna[] )
{
	int npraznih = 0;
	int s = Sirina();
	int v = Visina();
	for( int i=0; i<n; i++ ){
		int x = (x0 + pozicije[i][0] + s) % s;
		int y = (y0 + pozicije[i][1] + v) % v;
		if( (*this)[x][y] == &praznoPolje ){
			prazna[ npraznih++ ] = i;
		}
	}
	return npraznih;
}

//-----------------------------------------------------------
class IgraLife
{
public:
	IgraLife()
		{}
		
	Jedinka* NovaJedinka( char c )
		{
		switch( c ){
			case 's': 
				return &setalica;
			case 'x':
				return &cekalica;
			case 'k':
				return &skakalica;
			default:
				return &praznoPolje;
			}
		}
		
	void Iteracija()
		{
		int sirina = _Tabla.Sirina();
		int visina = _Tabla.Visina();
		Tabla novaTabla( sirina, visina );
		for( int i=0; i<sirina; i++ )
			for( int j=0; j<visina; j++ )
				novaTabla[i][j] = &praznoPolje;
		
		for( int i=0; i<sirina; i++ )
			for( int j=0; j<visina; j++ ){
				int x = i;
				int y = j;
				Jedinka* a = _Tabla[x][y];
				if( a->Prezivljava(_Tabla,x,y) )
					novaTabla[x][y] = a->NovaJedinka();
			}
		_Tabla = novaTabla;
		}
		
	void Ucitaj( istream& istr )
		{
		int sirina, visina;
		istr >> sirina >> visina;
		_Tabla = Tabla( sirina, visina );
		for( int i=0; i<visina; i++ )
			for( int j=0; j<sirina; j++ ){
				char c;
				istr >> c;
				_Tabla[j][i] = NovaJedinka(c);
			}
		}
		
	void Zapisi( ostream& ostr ) const
		{
		int sirina = _Tabla.Sirina();
		int visina = _Tabla.Visina();
				
		ostr << sirina << ' ' << visina << endl;
		for( int i=0; i<visina; i++ ){
			for( int j=0; j<sirina; j++ )
				ostr << _Tabla[j][i]->Izgled();
			ostr << endl;
			}
		}
	
private:
	Tabla _Tabla;
};


istream& operator >> ( istream& istr, IgraLife& igra )
{
	igra.Ucitaj( istr );
	return istr;
}

ostream& operator << ( ostream& ostr, const IgraLife& igra )
{
	igra.Zapisi( ostr );
	return ostr;
}


//-----------------------------------------------------------
main()
{
	randomize();
	IgraLife igra;
	ifstream f( "life.dat");
	f >> igra;
	cout << igra;
	while(1){
		char c = cin.get();
		if( c=='k')
			break;
		igra.Iteracija();
		cout << igra;
	}
	return 0;	
}