#include <iostream>
#include <limits.h>
#include <math.h>

using namespace std;

int WORLD      = 0;
int LASTWORLD  = 0;
int NEWWORLD   = 0;

const int ROW_L  = sqrt(log2(INT_MAX));
const int set[3] = { -1, 0, 1 };

int offset( int x, int y ) {
	int offset_bit  = (y*ROW_L)+x;
	int numeric_val = pow(2,offset_bit);
	return numeric_val;
}
int getX( int offset ) {
	return ( offset % ROW_L );
}
int getY( int offset ) {
	return ( offset / ROW_L );
}


int pokeCell( int x, int y ) {
	if (
		x >= 0    && y >= 0    &&
		x < ROW_L && y < ROW_L
	) {
		int bit = offset(x, y);
		return ( WORLD & bit ) != 0;
	} else {
		return -1;
	}
}

void setCell(int x, int y) {
	int bit = offset(x,y);
	WORLD += bit;
}

void unsetCell(int x, int y) {
	int bit = offset(x,y);
	WORLD -= bit;
}

int getDelta() {
	int ret = (WORLD & LASTWORLD);
	return (WORLD-ret);
}

int getNextOffset( int MIDWORLD ) {
	int oldmidworld = MIDWORLD;
	MIDWORLD = ((MIDWORLD) & (MIDWORLD-1));
	if ( MIDWORLD == 0 )
		if ( oldmidworld != 0 )
			return oldmidworld;
		else
			return 0;
	else
		return oldmidworld^MIDWORLD;
}

void processNode( int x, int y ) {
	int nCount = 0;

	for ( int i = 0; i < 3; ++i )
		for ( int n = 0; n < 3; ++n )
			if ( pokeCell(x+set[i], y+set[n]) == 1 )
				if (!( set[i] == 0 && set[n] == 0 ))
					nCount++;

	int bitflag = offset(x,y);

	if ( nCount < 2 || nCount > 3 )
		if ( ( NEWWORLD & bitflag ) > 0 )
			NEWWORLD -= bitflag;

	if ( nCount == 3 )
		if ( ( NEWWORLD & bitflag ) == 0 )
			NEWWORLD += bitflag;
}

void processNode( int x, int y, int flag ) {
	if ( flag )
		for ( int i = 0; i < 3; ++i )
			for ( int n = 0; n < 3; ++n )
				processNode(x+set[i], y+set[n]);
}

void renderWorld() {
	for ( int i = 0; i < ROW_L; ++i ) {
		for ( int n = 0; n < ROW_L; ++n )
			if ( pokeCell(i,n) )
				std::cout << " O";
			else
				std::cout << " X";
		std::cout << std::endl;
	}
	std::cout << std::endl;
}

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

	setCell(2,1);
	setCell(2,2);
	setCell(2,3);

	while ( WORLD != LASTWORLD ) {
		renderWorld();
		NEWWORLD = WORLD;
		int delt = getDelta();
		int next = getNextOffset(delt);
		delt -= next;
		while ( next != 0 ) {
			int x = getX(log2(next));
			int y = getY(log2(next));
			processNode(x,y,1);
			next = getNextOffset(delt);
			delt -= next;
		}
		if ( NEWWORLD == LASTWORLD ) {
			std::cout << "Hey! This loops! Cool!" << std::endl;
			LASTWORLD = NEWWORLD;
			WORLD     = NEWWORLD;
		}

		LASTWORLD = WORLD;
		WORLD = NEWWORLD;
	}

	std::cout << "All set. This is the final state." << std::endl << std::endl;
	renderWorld();
}