#include <stdio.h>



#include <string.h>
#include <stdio.h>

class bitvec;

class counter
{
	friend class bitvec;
	
	int i;
	int b;

public:
	counter() : i(0), b(1) {}
	counter(const counter& rhs) { i = rhs.i; b = rhs.b; }
	counter(int v) 
	{
		i = v >> 3;
		b = 1 << (v & 7);
	}
	
	inline void zero() { i = 0; b = 1; }
	inline bool iszero() { return i == 0 && b == 1; }
	inline void inc()
	{	if (b == 128)
		{	i++;
			b = 1;
		}
		else
			b *= 2;
	}
	inline void dec()
	{	if (b == 1)
		{	i--;
			b = 128;
		}
		else
			b /= 2;
	}
	inline const counter& operator=(const int v)
	{
		i = v >> 3;
		b = 1 << (v & 7);
		return *this;
	}
	inline const counter& operator=(const counter& rhs)
	{
		i = rhs.i;
		b = rhs.b;
		return *this;
	}
	inline bool operator<(const counter& rhs)
	{
		return i < rhs.i || (i == rhs.i && b < rhs.b);
	}
	inline bool operator==(const counter& rhs)
	{
		return i == rhs.i && b == rhs.b;
	}
	void print()
	{
		printf("(%d:%d)",i,b);
	}
};

class counter;

class bitvec
{
public:
	int v[25];

	static int len;
	static counter lencounter;
	static counter highbit;
	static int len8;
	static int len8m1;
	static int highnrbits;
	static int highmask;
	static int memlen;
	
	static void setlen(int newlen)
	{
		len = newlen;
		lencounter = len;
		highbit = len - 1;
		len8 = (len + 7)/8;
		len8m1 = len8-1;
		highnrbits = len % 8;
		highmask = (1 << highnrbits) - 1;
		memlen = len8 * sizeof(int);
		init_nrones();
	}
	
	inline void zero()
	{
		memset(v, 0, memlen);
	}
	inline bitvec& operator=(const bitvec rhs)
	{
		memcpy(v, rhs.v, memlen);
		return *this;
	}
	inline bool operator==(const bitvec rhs) const
	{
		return memcmp(v, rhs.v, memlen) == 0;
	}
	bool operator<=(const bitvec rhs) const
	{
		if (*this == rhs)
			return true;
		
		for (int i = len8m1; i >= 0; i--)
		{
			if (v[i] < rhs.v[i]) return true;
			if (v[i] > rhs.v[i]) return false;
		}
		return true; // equal, should not occur
	}
	bool operator<(const bitvec rhs) const
	{
		for (int i = len8m1; i >= 0; i--)
		{
			if (v[i] < rhs.v[i]) return true;
			if (v[i] > rhs.v[i]) return false;
		}
		return false;
	}

	inline int getbit(const counter& c) const
	{
		return v[c.i] & c.b;
	}
	inline void setbit(const counter& c)
	{	
		v[c.i] |= c.b;
	}
	inline void resetbit(const counter& c)
	{
		v[c.i] &= ~c.b;
	}
	inline void assignbit(const counter& c, int val)
	{
		if (val)
			v[c.i] |= c.b;
		else
			v[c.i] &= ~c.b;
	}
	
	void print(FILE* f = stdout)
	{
		counter i = lencounter;
		
		for (; !i.iszero();)
		{	i.dec();
			fprintf(f, "%c", getbit(i) ? '1' : '0');
		}
	}
	
	int nrones() const
	{
		int ones = 0;
		for (int i = 0; i < len8; i++)
			ones += _nrones[v[i]];
		
		return ones;
	}
	
	void rotate()
	{
		int lowest = v[0] & 1;
		for (int i = 0; i < len8m1; i++)
		{
			v[i] /= 2;
			if (v[i+1] & 1)
				v[i] |= (1 << 7);
		}
		v[len8m1] /= 2;
		if (lowest)
			v[len8m1] |= (1 << (highnrbits-1));
	}
	
private:	
	static int _nrones[256];

	static void init_nrones()
	{
		for (int i = 0; i < 256; i++)
		{
			int ones = 0;
			for (int j = 0; j < 8; j++)
				if (i & (1 << j))
					ones++;
			_nrones[i] = ones;
		}
	}
};

int bitvec::len;
counter bitvec::lencounter;
counter bitvec::highbit;
int bitvec::len8;
int bitvec::len8m1;
int bitvec::highnrbits;
int bitvec::highmask;
int bitvec::memlen;
int bitvec::_nrones[256];




bool equal(const bitvec& a, const bitvec& b)
{
	if (a == b)
		return true;

	if (a.nrones() != b.nrones())
		return false;
		
	for (counter i = 0; i < bitvec::lencounter; i.inc())
	{
		counter ca = 0;
		counter cb = i;
		
		int k;
		for (k = 0; k < bitvec::len; k++)
		{
			if (a.getbit(ca) != 0 ? b.getbit(cb) == 0 : b.getbit(cb) != 0)
				break;
				
			ca.inc();
			cb.inc();
			if (cb == bitvec::lencounter)
				cb.zero();
		}
		if (k == bitvec::len)
			return true;
	}
	
	return false;
}



int rule30sols[1024];


void init_rule30sols()
{
	for (int i = 0; i < 1024; i++)
	{
		int sol = 0;
		for (int j = 0; j < 8; j++)
		{
			if ((1 << ((i >> j) & 7)) & 30)
				sol |= (1 << j);
		}
		rule30sols[i] = sol;
	}
}

bool rule30(int a1, int a2, int a3)
{
	int bits = 0;
	if (a1) bits |= 4;
	if (a2) bits |= 2;
	if (a3) bits |= 1;
	
	return (1 << bits) & 30;
}

void slow_rule30(bitvec& a)
{
	bitvec b = a;
	
	a.zero();

	for (int i = 0; i < bitvec::len; i++)
	{
		counter a1 = i == (bitvec::len-1) ? 0 : i+1;
		counter a2 = i;
		counter a3 = i == 0 ? (bitvec::len-1) : i-1;
		
		if (rule30(b.getbit(a1), b.getbit(a2), b.getbit(a3)))
			a.setbit(a2);
	}
}

inline void normalize(bitvec& a)
{
	bitvec a1 = a;
	
    for (int i = 0; i < bitvec::len; i++)
    {
        a1.rotate();
        if (a1 < a)
            a = a1;
    }
}







#define HEIGHT 16
#define WIDTH 128
bool one[HEIGHT][WIDTH];
bool isass[HEIGHT][WIDTH];

struct
{	int h;
	int w;
} assigned[HEIGHT*WIDTH];

int width;
int height;
int shift;

void print_state()
{
	for (int h = 0; h < height; h++)
	{	for (int w = width-1; w >= 0; w--)
			printf("%c", isass[h][w] ? one[h][w] ? '1' : '0' : '?');
		printf("\n");
	}
}

int cur_nr_ass;

#define LEFT(w) (((w)+1) % width)
#define RIGHT(w) (((w)-1+width) % width)


bool complete(int h, int w, bool v)
{
	if (isass[h][w])
		return one[h][w] == v;

	one[h][w] = v;
	isass[h][w] = true;
	assigned[cur_nr_ass].h = h;
	assigned[cur_nr_ass].w = w;
	cur_nr_ass++;

	int w_l = LEFT(w);
	int w_r = RIGHT(w);
	
	int w_d = w;
	int h_d = h+1;
	if (h_d == height)
	{
		h_d = 0;
		w_d = (w_d + shift) % width;
	}
	
	if (isass[h][w_l])
	{
		int w_l2 = LEFT(w_l);
		if (isass[h][w_l2])
		{
			int w_dl = LEFT(w_d);
			
			bool val = rule30(one[h][w_l2], one[h][w_l], one[h][w]);
			if (!complete(h_d, w_dl, val))
				return false;
		}
	}
	if (isass[h][w_r])
	{
		int w_r2 = RIGHT(w_r);
		
		if (isass[h][w_r2])
		{
			int w_dr = RIGHT(w_d);
			
			bool val = rule30(one[h][w], one[h][w_r], one[h][w_r2]);
			if (!complete(h_d, w_dr, val))
				return false;
		}

		if (isass[h][w_l])
		{
			bool val = rule30(one[h][w_l], one[h][w], one[h][w_r]);
			if (!complete(h_d, w_d, val))
				return false;
		}
	}
	
	return true;
}

void solverec(int i)
{
	if (i == width)
	{
		//printf("Found solution %d %d %d\n", width, height, shift);
		//print_state();
		
		bitvec x;
		x.zero();
		for (int i = 0; i < bitvec::len; i++)
			if (one[0][i])
				x.setbit(counter(i));
		//x.print();
		//printf("\n");

		// Did already report it
		bool good = true;
		bitvec z = x;
		
		
		//printf("\n");
		//z.print();
		for (int l = 0; l < bitvec::len - 1; l++)
		{
			z.rotate();
			//printf(" r:");
			//z.print();
			if (z <= x)
			{
				//printf("\n");
				//z.print();
				
				good = false;
				break;
			}
		}
		
		if (good)
		{	//printf("\n== ");
			//x.print();
			//printf(" ");
			//y.print();
			//printf(" %d\n", height);

			bitvec a = x;
			for (int l = 0; l < height; l++)
			{
				slow_rule30(a);
				bitvec norm = a;
				normalize(norm);
				if (norm < x)
				{	good = false;
					break;
				}
			}
			
			if (good)
			{						
				if (!equal(a, x))
				{
					printf("Error!!!\n");
					x.print();
					printf("\n");
					a.print();
					printf("\n");
				}
				printf("Found solution %d %d %d\n", width, height, shift);
				//print_state();
				a = x;
				//printf("\n");
				a.print();
				printf("\n");
				for (int l = 0; l < height-1; l++)
				{
					slow_rule30(a);
					a.print();
					printf("\n");
				}
			}
		}
		else
		{	//printf("\n== ");
			//x.print();
			//printf(" ");
			//y.print();
			//printf(" already done!!\n");
		}
	}
	else if (isass[0][i])
	{
		solverec(i+1);
	}
	else
	{
		//printf("Try %d\n", i);
		//print_state();
		
		int nr_ass = cur_nr_ass;
		
		if (complete(0,i,false))
			solverec(i+1);

		while (cur_nr_ass > nr_ass)
		{
			cur_nr_ass--;
			isass[assigned[cur_nr_ass].h][assigned[cur_nr_ass].w] = false;
		}
		
		one[0][i] = true;

		if (complete(0,i,true))
			solverec(i+1);

		while (cur_nr_ass > nr_ass)
		{
			cur_nr_ass--;
			isass[assigned[cur_nr_ass].h][assigned[cur_nr_ass].w] = false;
		}

		isass[0][i] = false;
	}
}

void solve(int new_width, int new_height, int new_shift)
{
	width = new_width;
	height = new_height;
	shift = new_shift;
	
	for (int w = 0; w < width; w++)
		for (int h = 0; h < height; h++)
			isass[h][w] = false;
	
	cur_nr_ass = 0;
	solverec(0);
}

int main(int argc, char *argv[])
{
	for (int w = 10; w <= 100; w++)
	{
		bitvec::setlen(w);
		
		for (int h = 1; h * w <= 100; h++)
			for (int s = 1; s < w; s++)
				solve(w, h, s);
	}
}