#include <stdio.h>

#define BIT(I) (1 << (I))
#define GETBIT(X,I) (((X) >> (I)) & 1)
#define BITS2(X,Y) ((X) | ((Y) << 1))
#define BITS3(X,Y,Z) ((X) | ((Y) << 1) | ((Z) << 2))

#define FORALLTILE(I,X) for (int I = 0; I < 16; I++) if (GETBIT(X,I))

void print_qt_first(int qt)
{
	FORALLTILE(i, qt)
		printf(" %c%c", i & 1 ? '1' : '0', i & 2 ? '1' : '0');
}

void print_qt_second(int qt)
{
	FORALLTILE(i, qt)
		printf(" %c%c", i & 4 ? '1' : '0', i & 8 ? '1' : '0');
}

void print_qt(int qt)
{
	printf("\n");
	print_qt_first(qt);
	printf("\n");
	print_qt_second(qt);
	printf("\n");
}

class SetOfQT
{
public:
	SetOfQT() : nr(0) {}
	
	void add(int v)
	{
		for (int i = 0; i < nr; i++)
			if (values[i] == v)
				return;
		values[nr++] = v;
	}

	void print_first()
	{
		for (int i = 0; i < nr; i++)
		{
			if (i > 0)
				printf(" | ");
			print_qt_first(values[i]);
		}
	}
	void print_second()
	{
		for (int i = 0; i < nr; i++)
		{
			if (i > 0)
				printf("   ");
			print_qt_second(values[i]);
		}
	}
	int nr;
	int values[20];
};

int permutations[8][4] =
{
	{ 0, 1, 2, 3 },
	{ 2, 0, 3, 1 },
	{ 3, 2, 1, 0 },
	{ 1, 3, 0, 2 },
	{ 0, 2, 1, 3 },
	{ 1, 0, 3, 2 },
	{ 3, 1, 2, 0 },
	{ 2, 3, 0, 1 },
};

long permvectors[15][16];

void fill_permvectors()
{
	for (int i = 1; i < 8; i++)
	{
		for (int v = 0; v < 16; v++)
		{
			int r = 0;
			for (int j = 0; j < 4; j++)
				if (GETBIT(v, j))
				    r |= BIT(permutations[i][j]);
			permvectors[i-1][v] = BIT(r);
		}
	}
	for (int i = 0; i < 8; i++)
	{
		for (int v = 0; v < 16; v++)
		{
			int r = 0;
			for (int j = 0; j < 4; j++)
				if (!(GETBIT(v, j)))
				    r |= BIT(permutations[i][j]);
			permvectors[7+i][v] = BIT(r);
		}
	}
}

bool is_minimal(long qt)
{
	for (int i = 0; i < 15; i++)
	{
		long aqt = 0;
		FORALLTILE(j, qt)
			aqt |= permvectors[i][j];
		if (aqt < qt)
			return false;
	}
	
	return true;
}

bool has_unused_pieces(long qt)
{
	int left = 0;
	int right = 0;
	int top = 0;
	int bottom = 0;
	FORALLTILE(i, qt)
	{
		int v0 = GETBIT(i,0);
		int v1 = GETBIT(i,1);
		int v2 = GETBIT(i,2);
		int v3 = GETBIT(i,3);
		left   |= BIT(BITS2(v0, v2));
		right  |= BIT(BITS2(v1, v3));
		top    |= BIT(BITS2(v0, v1));
		bottom |= BIT(BITS2(v2, v3));
	}
	return left != right || top != bottom;	
}

bool has_unused_pieces_in_cross(long qt)
{
	//if (qt > 1000) return true;
		
	int topleft = 0;
	int topright = 0;
	int bottomleft = 0;
	int bottomright = 0;
	
	FORALLTILE(i, qt)
	{
		int v0 = GETBIT(i,0);
		int v1 = GETBIT(i,1);
		int v2 = GETBIT(i,2);
		int v3 = GETBIT(i,3);

		/*printf("%d   %d %d %d %d\n",
		       i,
		       BITS3(v1,v3,v2),
		       BITS3(v3,v2,v0),
		       BITS3(v2,v0,v1),
		       BITS3(v0,v1,v3));
		*/		
		topleft     |= BIT(BITS3(v1,v3,v2));
		topright    |= BIT(BITS3(v3,v2,v0));
		bottomright |= BIT(BITS3(v2,v0,v1));
		bottomleft  |= BIT(BITS3(v0,v1,v3));
	}

	int poss_topleft = 0;
	int poss_topright = 0;
	int poss_bottomright = 0;
	int poss_bottomleft = 0;
	
	for (int i = 0; i < 32; i++)
	{
		int c0 = GETBIT(i,0);
		int c1 = GETBIT(i,1);
		int c2 = GETBIT(i,2);
		int c3 = GETBIT(i,3);
		int c4 = GETBIT(i,4);
		
		int v_tl = BITS3(c1,c0,c4);
		int v_tr = BITS3(c2,c0,c1);
		int v_br = BITS3(c3,c0,c2);
		int v_bl = BITS3(c4,c0,c3);

		bool tl = GETBIT(topleft,     v_tl);
		bool tr = GETBIT(topright,    v_tr);
		bool br = GETBIT(bottomright, v_br);
		bool bl = GETBIT(bottomleft,  v_bl);

		if (tr && br && bl)
		{
			poss_topleft |= BIT(v_tl);
		}
		if (tl && br && bl)
		{
			poss_topright |= BIT(v_tr);
		}
		if (tl && tr && bl)
		{
			poss_bottomright |= BIT(v_br);
		}
		if (tl && tr && br)
		{
			poss_bottomleft |= BIT(v_bl);
		}
	}

	bool result;

	for (int r = 1; r <=2; r++)
	{	
		result = false;
		
		FORALLTILE(i, qt)
		{
			int v0 = GETBIT(i,0);
			int v1 = GETBIT(i,1);
			int v2 = GETBIT(i,2);
			int v3 = GETBIT(i,3);
	
			int v_tl = BITS3(v1,v3,v2);
			int v_tr = BITS3(v3,v2,v0);
			int v_br = BITS3(v2,v0,v1);
			int v_bl = BITS3(v0,v1,v3);
			
			if (   !GETBIT(poss_topleft, v_tl)
			    || !GETBIT(poss_topright, v_tr)
			    || !GETBIT(poss_bottomright, v_br)
			    || !GETBIT(poss_bottomleft, v_bl))
			{
				if (!result)
				{
					if (r == 1)
					{
						printf("\n");
						print_qt_first(qt);
						printf(" impossible");
					}
					else
					{
						printf("\n");
						print_qt_second(qt);
						printf("           ");
					}
					result = true;
				}
				
				if (r == 1)
					printf(" %c%d%d%c", 
						GETBIT(poss_bottomright, v_br) ? ' ' : '~', 
						v0, v1,
						GETBIT(poss_bottomleft, v_bl) ? ' ' : '~');
				else
				{
					printf(" %c%d%d%c", 
						GETBIT(poss_topright, v_tr) ? ' ' : '_', 
						v2, v3,
						GETBIT(poss_topleft, v_tl) ? ' ' : '_');
				}
			}
		}
	}
	if (result)
		printf("\n");
		
	return result;
}

bool has_unused_pieces_in_square(long qt)
{

	long qt_1 = 0;
	long qt_2 = 0;
	long qt_3 = 0;
	long qt_5 = 0;
	long qt_6 = 0;
	long qt_7 = 0;
	long qt_9 = 0;
	long qt_10 = 0;
	long qt_11 = 0;
	
	FORALLTILE(i, qt)
	{
		int val[17];
		val[6] = GETBIT(i, 0);
		val[7] = GETBIT(i, 1);
		val[10] = GETBIT(i, 2);
		val[11] = GETBIT(i, 3);
		
		int count = 0;
		for (int j = 0; j < 4096; j++)
		{
			val[1] = GETBIT(j, 0);
			val[2] = GETBIT(j, 1);
			val[3] = GETBIT(j, 2);
			val[4] = GETBIT(j, 3);
			val[5] = GETBIT(j, 4);
			val[8] = GETBIT(j, 5);
			val[9] = GETBIT(j, 6);
			val[12] = GETBIT(j, 7);
			val[13] = GETBIT(j, 8);
			val[14] = GETBIT(j, 9);
			val[15] = GETBIT(j, 10);
			val[16] = GETBIT(j, 11);

//#define ZZZ(N) (val[N] | (val[N+1] << 1) | (val[N+4] << 2) | (val[N+5] << 3))
#define SQUARE(N) (val[N] | (val[N+1] << 1) | (val[N+4] << 2) | (val[N+5] << 3))
		
			int v1 = SQUARE(1);
			int v2 = SQUARE(2);
			int v3 = SQUARE(3);
			int v5 = SQUARE(5);
			int v7 = SQUARE(7);
			int v9 = SQUARE(9);
			int v10 = SQUARE(10);
			int v11 = SQUARE(11);
			if (   GETBIT(qt, v1)
			    && GETBIT(qt, v2)
			    && GETBIT(qt, v3)
			    && GETBIT(qt, v5)
			    && GETBIT(qt, v7)
			    && GETBIT(qt, v9)
			    && GETBIT(qt, v10)
			    && GETBIT(qt, v11))
			{
				qt_1 |= BIT(v1);
				qt_2 |= BIT(v2);
				qt_3 |= BIT(v3);
				qt_5 |= BIT(v5);
				qt_6 |= BIT(i);
				qt_7 |= BIT(v7);
				qt_9 |= BIT(v9);
				qt_10 |= BIT(v10);
				qt_11 |= BIT(v11);
			    count++;
			}
		}
		
	}
	int qt_possible = qt_1 & qt_2 & qt_3 & qt_5 & qt_6 & qt_7 & qt_9 & qt_10 & qt_11;
	if (qt_possible != qt)
	{
		printf("\n");
		print_qt_first(qt);
		printf(" impossible 3x3 ");
		print_qt_first(qt & ~qt_possible);
		printf("\n");
		print_qt_second(qt);
		printf("                ");
		print_qt_second(qt & ~qt_possible);
		printf("\n");
		return true;
	}
	return false;
}
			
class Relation
{
public:
	Relation()
	{
		for (int i = 0; i < 16; i++)
		{
			for (int j = 0; j < 16; j++)
				rel[i][j] = ' ';
		}
	}
	
	void calculate_closure()
	{
		// Floyds algorithm for calculating closure
		for (int j = 0; j < 16; j++)
			for (int i = 0; i < 16; i++)
				for (int k = 0; k < 16; k++)
				{
					if (rel[i][j] != ' ' && rel[j][k] != ' ' && rel[i][k] == ' ')
						rel[i][k] = 'x';
				}
	}

	char rel[16][16];
};
			
class SingleDirection : public Relation
{
public:
	SingleDirection(int new_qt) : Relation(),
	    qt(new_qt)
	{
		for (int i = 0; i < 16; i++)
		{
			group[i] = i;
			size[i] = 0;
		}
	}
	
	void analyze()
	{
		calculate_closure();
		
		// Calculate groups		
		FORALLTILE(i, qt)
			if (rel[i][i] != ' ')
			{
				FORALLTILE(j, qt)
					if (rel[i][j] != ' ' && rel[j][i] != ' ' && rel[j][j] != ' ')
					{
						group[i] = j;
						break;
					}
			}
		
		// Calculate size
		FORALLTILE(i, qt)
			FORALLTILE(j,qt)
				if (rel[i][j] != ' ' || i == j)
					size[i]++;
	}

#define FORALLGROUP(I,X) FORALLTILE(I,X) if (group[I] == I)

	bool smallerRel(int i, int j)
	{
		if (size[i] >= size[j])
			return false;
			
		FORALLTILE(k, qt)
			if (rel[i][k] != ' ' && rel[j][k] == ' ')
				return false;
		return true;
	}
	
	void analyze_groups()
	{
		FORALLGROUP(i,qt)
		{
			FORALLGROUP(j,qt)
			{
				bool smaller = false;
				if (rel[i][j] != ' ' && smallerRel(j,i))
				{
					smaller = true;
					FORALLGROUP(k, qt)
						if (smallerRel(j,k) && smallerRel(k,i))
						{
							smaller = false;
							break;
						}
				}
				before[i][j] = smaller ? '<' : ' ';
			}
		}
		
		nr_groups = 0;
		nr_start = 0;
		nr_end = 0;
		
		FORALLGROUP(i,qt)
		{
			nr_groups++;
			
			bool is_start = true;
			bool is_end = true;
			
			FORALLGROUP(j,qt)
			{
				if (before[j][i] == '<')
					is_start = false;
				if (before[i][j] == '<')
					is_end = false;
			}
			startgroup[i] = is_start;
			endgroup[i] = is_end;
			if (is_start)
				nr_start++;
			if (is_end)
				nr_end++;
		}
		
		FORALLTILE(i,qt)
			if (i != group[i])
			{
				startgroup[i] = startgroup[group[i]];
				endgroup[i] = endgroup[group[i]];
			}
	}
	
	void analyze_groups_print()
	{
		FORALLGROUP(i,qt)
		{
			FORALLGROUP(j,qt)
				printf("%c", before[i][j]);
			printf(" %3d %3d %d%d\n", group[i], size[i], startgroup[i], endgroup[i]);
		}
		
		printf("groups %d start %d end %d\n", nr_groups, nr_start, nr_end);
	}

	int group[16];
	int size[16];
	char before[16][16];
	int qt;

	bool startgroup[16];
	bool endgroup[16];	
	int nr_groups;
	int nr_start;
	int nr_end;
};

bool overlapping_components(Relation& rel1, Relation& rel2, int qt, char* dir, SetOfQT& overlap)
{
	bool result = false;

	bool processed[16];
	for (int i = 0; i < 16; i++)
		processed[i] = false;
	
	FORALLTILE(i, qt)
		if (!processed[i])
		{
			bool all = true;
			FORALLTILE(j, qt)
				if (rel1.rel[i][j] == ' ')
					all = false;
				else
					processed[j] = true;
			
			if (!all)
			{
				bool used[16];
				for (int j = 0; j < 16; j++)
					used[j] = false;
				
				FORALLTILE(j, qt)
					if (rel1.rel[i][j] != ' ')
					{
						FORALLTILE(k, qt)
							if (rel2.rel[j][k] != ' ')
								used[k] = true;
					}
				
				bool all_used = true;
				FORALLTILE(j, qt)
					if (!used[j])
						all_used = false;
				
				if (!all_used)
				{
					result = true;
					int value = 0;
					FORALLTILE(j,qt)
						if (used[j])
							value |= BIT(j);
					overlap.add(value);
				}
			}
		}
	return result;
}

#define MAX_LENGTH 7
#define MAX_DEPTH 10
#define MAX_SOLUTIONS 10000

class PartialSolutions
{
public:
	PartialSolutions() : nr_sols(0), empty(true) {}
	void add(int qt)
	{
		empty = false;
		int j = 0;
		bool found = false;
		for (int i = 0; i < nr_sols; i++)
		{
			if ((sols[i] | qt) == sols[i]) // qt subset of sols[i]
			{
				found = true;
				sols[j++] = sols[i];
			}
			else if ((sols[i] | qt) == qt) // sols[i] subset of qt
				; // remove sols[i]
			else
				sols[j++] = sols[i];
		}
		if (!found && j < 50)
		{
			sols[j++] = qt;
		}
		nr_sols = j;
	}
	
	void print_first_row(int qt)
	{
		if (empty)
			printf("empty");
		for (int i = 0; i < nr_sols; i++)
		{
			if (i > 0)
				printf("  ");
			print_qt_first(qt & ~sols[i]);
		}
	}
	void print_second_row(int qt)
	{
		for (int i = 0; i < nr_sols; i++)
		{
			if (i > 0)
				printf("  ");
			print_qt_second(qt & ~sols[i]);
		}
	}

private:
	bool empty;
	int sols[50];
	int nr_sols;
};

class SearchRepeating
{
protected:
	SearchRepeating(SingleDirection& direction, bool top_bottom, PartialSolutions &partial_solutions)
	  : _direction(direction), _top_bottom(top_bottom), _print(false), _partial_solutions(partial_solutions) {}
	
	void setPrint() { _print = true; }
	
	void insert_solution(int from, int to, int used)
	{
		int i;
		for (i = 0; i < _nr_solutions; i++)
			if (_solutions[i].from == from && _solutions[i].to == to && _solutions[i].qt_used == used)
			{
				//_solutions[i].qt_used |= used;
				break;
			}
		
		if (i == _nr_solutions && _nr_solutions < MAX_SOLUTIONS)
		{
			_solutions[i].from = from;
			_solutions[i].to = to;
			_solutions[i].qt_used = used;
			_nr_solutions++;
		}
	}

	bool find_path_in_solution()
	{
		if (_nr_solutions == MAX_SOLUTIONS)
		{
		}
		else
		{
			// Remove solutions that have no previous or next
			bool go;
			do
			{
				go = false;
				
				for (int i = 0; i < _nr_solutions; i++)
				{
					_solutions[i].prev = false;
					_solutions[i].next = false;
				}
				
				for (int i = 0; i < _nr_solutions; i++)
					for (int j = 0; j < _nr_solutions; j++)
						if (_solutions[i].to == _solutions[j].from)
						{
							_solutions[i].next = true;
							_solutions[j].prev = true;
						}
				
				int i;
				int j;
				for (i = 0, j = 0; i < _nr_solutions; i++)
				{
					if (_solutions[i].next && _solutions[i].prev)
					{
						_solutions[j].from = _solutions[i].from;
						_solutions[j].to = _solutions[i].to;
						_solutions[j].qt_used = _solutions[i].qt_used;
						j++;
					}
					else
						go = true;
				}
				_nr_solutions = j;					
			} while (go && _nr_solutions > 0);
			
			if (_nr_solutions > 0)
			{
				// Calculate reachable states
				bool all_found = false;
				for (int i = 0; i < _nr_solutions; i++)
					_solutions[i].qt_cum = _solutions[i].qt_used;
				do
				{
					go = false;
					
					for (int i = 0; i < _nr_solutions; i++)
						for (int j = 0; j < _nr_solutions; j++)
							if (_solutions[i].to == _solutions[j].from)
							{
								int new_qt_cum = _solutions[i].qt_cum | _solutions[j].qt_cum;
								if (new_qt_cum != _solutions[j].qt_cum)
								{
									_solutions[j].qt_cum = new_qt_cum;
									go = true;
								}
								if (new_qt_cum == _direction.qt)
									all_found = true;
							}
				} while (go);
			
				if (all_found)
				{
					// Mark all paths leading to states reaching all tiles
					for (int i = 0; i < _nr_solutions; i++)
						_solutions[i].good = _solutions[i].qt_cum == _direction.qt;
					do
					{
						go = false;
						
						for (int i = 0; i < _nr_solutions; i++)
						    if (!_solutions[i].good)
							for (int j = 0; j < _nr_solutions; j++)
								if (   _solutions[i].to == _solutions[j].from
								    && _solutions[j].good)
								{
									_solutions[i].good = true;
									go = true;
									break;
								}
					} while (go);
				
					for (int i = 0; i < _size; i++)
					{
						if (search_down_path(0, i, 0))
							return true;
					}
				}
			}
		}
		return false;
	}

	virtual void print_state(int state)
	{
	}
	virtual void print_found()
	{
	}
	
	bool search_down_path(int depth, int from, int qt_cum)
	{
		for (int i = 0; i < _nr_solutions; i++)
			if (_solutions[i].from == from && _solutions[i].good)
			{
				int to = _solutions[i].to;
				int qt_used = _solutions[i].qt_used;
				int new_qt_cum = qt_cum | qt_used;
				
				if (new_qt_cum == _direction.qt)
				{
					printf("\n");
					print_qt_first(_direction.qt);
					print_found();
					print_qt_second(_direction.qt);
					printf("\n");
					
					if (_print)
					{
						printf("--\n");
						for (int j = 0; j < depth; j++)
						{
							print_state(_steps[j].from);
							print_qt(_steps[j].qt);
						}
						print_state(from);
						print_qt(qt_used);
						print_state(to);
						printf("\n");
						printf("--\n");
					}
					return true;
				}
				
				_partial_solutions.add(new_qt_cum);
				
				if (depth < MAX_DEPTH)
				{
					_steps[depth].from = from;
					_steps[depth].to = to;
					_steps[depth].qt = qt_used;
					_steps[depth].qt_cum = new_qt_cum;
					
					// Check for cycle
					bool cycle = false;
					for (int i = 0; i < depth; i++)
						if (_steps[i].to == to && _steps[i].qt_cum == new_qt_cum)
						{
							cycle = true;
							break;
						}
					
					if (!cycle)
					{
						if (search_down_path(depth+1, to, new_qt_cum))
							return true;					
					}
				}
			}
		return false;
	}	
	
	SingleDirection& _direction;
	bool _top_bottom;
	bool _print;
	PartialSolutions &_partial_solutions;

	struct 
	{
		long from;
		long to;
		int qt_used;
		bool prev;
		bool next;
		int qt_cum;
		bool good;
	} _solutions[MAX_SOLUTIONS];
	int _nr_solutions;
	int _length;
	int _size;
	struct
	{
		int from;
		int to;
		int qt;
		int qt_cum;
	} _steps[MAX_DEPTH+1];
};


class SearchRepeatingRectangle : public SearchRepeating
{
public:
	SearchRepeatingRectangle(SingleDirection& direction, bool top_bottom, PartialSolutions &partial_solutions)
	  : SearchRepeating(direction, top_bottom, partial_solutions) {}

	bool search()
	{
		setPrint();
		for (_length = 1; _length <= MAX_LENGTH; _length++)
		{
			_size = 1 << _length;
			_nr_solutions = 0;

			fflush(stdout);
						
			FORALLTILE(i,_direction.qt)
				find_solution(0, i);

			if (find_path_in_solution())
				return true;
		}

		return false;
	}

private:
	void find_solution(int l, int from)
	{
		if (l == _length)
		{
			if (from == _path[0])
			{
				// found solution
				int from = 0;
				int to = 0;
				int used = 0;
				for (int i = 0; i < _length; i++)
				{
					used |= BIT(_path[i]);
					if (_top_bottom)
					{
						if (GETBIT(_path[i], 0))
							from |= BIT(i);
						if (GETBIT(_path[i], 2))
							to |= BIT(i);
					}
					else
					{
						if (GETBIT(_path[i], 0))
							from |= BIT(i);
						if (GETBIT(_path[i], 1))
							to |= BIT(i);
					}
				}
				from = normalize(from);
				to = normalize(to);

				insert_solution(from, to, used);				
			}
			return;
		}

		_path[l++] = from;
		
		FORALLTILE(i,_direction.qt)
			if (_direction.rel[from][i] == 'X')
				find_solution(l, i);
	}
	
	int normalize(int v)
	{
		int r = v;
		for (int i = 0; i < _length; i++)
		{
			v = (v >> 1) | ((v&1) << (_length - 1));
			if (v < r)
				r = v;
		}
		
		return r;
	}

	virtual void print_state(int state)
	{
		printf("(");
		for (int k = 0; k < _length; k++)
			printf("%d", GETBIT(state, k));
		printf(")*");
	}
	virtual void print_found()
	{
		printf(" found %s cyclic rectangle\n", _top_bottom ? "top-bottom" : "left-right");
	}
	
	int _path[MAX_LENGTH];
};

class SearchRepeatingLines : public SearchRepeating
{
public:
	SearchRepeatingLines(SingleDirection& direction, bool top_bottom, PartialSolutions &partial_solutions)
	  : SearchRepeating(direction, top_bottom, partial_solutions) {}

	bool search()
	{
		setPrint();
		
		for (_length = 2; _length <= MAX_LENGTH; _length++)
		{
			_size = 1 << _length;
			
			for (int se_length = 2; se_length <= _length; se_length++)
				for (_start_length = 1, _end_length = se_length - _start_length; _end_length >= 1; _start_length++, _end_length--)
				{
					_end_pos = _length - _end_length;
					
					fflush(stdout);
					
					_nr_solutions = 0;
					FORALLTILE(i,_direction.qt)
						find_solution(0, i);
						
					if (find_path_in_solution())
						return true;
				}
		}
		return false;
	}

private:

	void find_solution(int l, int from)
	{
		if (l > _length+1)
		{
			return;
		}
			
		if (l == _start_length && _path[0] != from)
		{
			return;
		}
		
		if (l == _start_length+1 && _path[1] == from)
		{
			return;
		}
			
		if (l > _start_length + _end_length && from == _path[l - _end_length])
		{
			// Found some solution
			int fromline[MAX_LENGTH];
			int toline[MAX_LENGTH];
			int used = 0;

			for (int i = 0; i < l; i++)
			{
				used |= BIT(_path[i]);
				if (_top_bottom)
				{
					fromline[i] = GETBIT(_path[i], 1);
					toline[i] = GETBIT(_path[i], 3);
				}
				else
				{
					fromline[i] = GETBIT(_path[i], 2);
					toline[i] = GETBIT(_path[i], 3);
				}
			}

			int from = normalize(fromline, l-1);
			int to = normalize(toline, l-1);
			
			insert_solution(from, to, used);
		}
		_path[l++] = from;

		FORALLTILE(i,_direction.qt)
			if (_direction.rel[from][i] == 'X')
				find_solution(l, i);
	}
	
	int normalize(int line[], int length)
	{
		bool trace = false;
		bool trace_n = false;
		if (trace)
		{
			printf("%d: ", length);
			for (int i = 0; i < length; i++)
			{
				if (i == _start_length || i == length - _end_length)
					printf("*");
				printf("%d", line[i]);
			}
			printf(" -> ");
		}
		
		int s = _start_length;
		int start = 0;
		for (int i = 0; i < _start_length; i++)
			if (line[i])
				start |= BIT(i);
		int start_length;
		{
			int v = start;
			int f = 1;
			for (int i = 1; i < _start_length; i++)
			{
				v = (v >> 1) | ((v&1) << (_start_length - 1));
				if (v < start)
				{
					start = v;
					f = 1;
					s = _start_length - i;
				}
				else if (v == start)
					f++;		
			}
			start_length = _start_length / f;
		}
		
		int e = length - _end_length;
		int end = 0;
		for (int i = 0; i < _end_length; i++)
			if (line[e+i])
				end |= BIT(i);
		int end_length;
		{
			int v = end;
			int f = 0;
			for (int i = 1; i <= _end_length; i++)
			{
				v = (v >> 1) | ((v&1) << (_end_length - 1));
				if (v < end)
				{
					end = v;
					f = 1;
					e = length - i;
				}
				else if (v == end)
				{
					f++;
					e = length - i;
				}
			}
			end_length = _end_length / f;
		}
		
		if (trace)
		{
			for (int i = 0; i < start_length; i++)
				printf("%d", GETBIT(start, i));
			printf("|");
			for (int i = s; i < e; i++)
				printf("%d", line[i]);
			printf("|");
			for (int i = 0; i < end_length; i++)
				printf("%d", GETBIT(end, i));
			printf(" -> %d:%d", s, e);
		}
				
		int best_l = 100;
		int best_v;
		
#define LINEBIT(X) \
		( (X) < s ?  GETBIT(start, ((X) - s + start_length*10) % start_length) \
		: (X) >= e ? GETBIT(end, ((X) - e) % end_length) \
		:            line[X] )
		
		bool go = true;
		int a_s = s;
		for (; a_s <= e; a_s += start_length)
		{
			if (trace_n) printf(" a_s=%d", a_s);
			// process a_s to e
			
			for (int a_e = e; a_e >= a_s - start_length; )
			{
				if (trace_n) printf(" a_e=%d", a_e);
				
				// check a_e
				int new_l = a_e - a_s;
				int new_v = 0;
				for (int j = 0; j < new_l; j++)
					if (LINEBIT(a_s + j))
						new_v |= BIT(j);
				if (trace_n) 
				{
					printf(" %d:%d=", a_s, a_e);
					for (int j = 0; j < new_l; j++)
						printf("%d", GETBIT(new_v, j));
				}
				
				if (new_l < best_l || (new_l == best_l && new_v < best_v))
				{
					best_l = new_l;
					best_v = new_v;
				}
				
				if (best_l == 0)
					break;
					
				// previous
				a_e -= end_length;
				int a_end = 0;
				for (int j = 0; j < end_length; j++)
					if (LINEBIT(a_e + j))
						a_end |= BIT(j);
				
				if (a_end != end)
				{
					if (trace_n) printf(" e:%d!=%d", a_end, end);
					break;
				}
			}
			if (best_l == 0)
				break;
				
			if (a_s + start_length > e)
				break;
				
			// next
			int a_start = 0;
			for (int i = 0; i < start_length; i++)
				if (line[a_s + i])
					a_start |= BIT(i);
			
			if (a_start != start)
			{
				if (trace_n) printf(" s:%d!=%d", a_start, start);
				go = false;
				break;
			}
		}
		
		if (go && best_l > 0)
		{
			int a_e = e;
			
			for (int i = 0; i < 10 /* just some number */; i++)
			{
				if (trace_n) printf(" i=%d", i);
				
				while (a_e < a_s)
					a_e += end_length;
				
				int new_l = a_e - a_s;
				int new_v = 0;
				for (int j = 0; j < new_l; j++)
					if (LINEBIT(a_s + j))
						new_v |= BIT(j);
				if (trace_n) 
				{
					printf(" %d:%d=", a_s, a_e);
					for (int j = 0; j < new_l; j++)
						printf("%d", GETBIT(new_v, j));
				}
				
				if (new_l < best_l || (new_l == best_l && new_v < best_v))
				{
					best_l = new_l;
					best_v = new_v;
				}
				
				if (best_l == 0)
					break;

				int a_start = 0;
				for (int j = 0; j < start_length; j++)
					if (LINEBIT(a_s + j))
						a_start |= BIT(j);
				
				if (a_start != start)
					break;
					
				a_s += start_length;
			}
		}
		
		if (best_l == 100)
		{	
			return 0;
		}
		
		int t = 0;
		int r = 0;
		if (trace) printf(" -> ");
		for (int i = 0; i < _start_length; i++, t++)
		{
			if (GETBIT(start, i % start_length))
				r |= BIT(t);
			
			if (trace && i < start_length) printf("%d", GETBIT(start, i % start_length));
		}
		if (trace) printf("|");
		for (int i = 0; i < best_l; i++, t++)
		{
			if (GETBIT(best_v, i))
				r |= BIT(t);
			if (trace) printf("%d", GETBIT(best_v, i));
		}
		if (trace) printf("|");
		for (int i = 0; i < _end_length; i++, t++)
		{
			if (GETBIT(end, i % end_length))
				r |= BIT(t);
			if (trace && i < end_length) printf("%d", GETBIT(end, i));
		}
		r |= BIT(t);
		if (trace) printf(" %d\n", r);
		
		return r;
	}

	virtual void print_state(int state)
	{
		int l = 0;
		for (int i = 0; i < 30; i++)
			if (GETBIT(state, i))
				l = i;
		
		printf("(");		
		for (int k = 0; k < l; k++)
		{
			if (k == _start_length)
				printf(")*");
			if (k == l - _end_length)
				printf("(");
			printf("%d", GETBIT(state, k));
		}
		printf(")*");
	}
	virtual void print_found()
	{
		printf(" found %s cyclic lines\n", _top_bottom ? "top-bottom" : "left-right");
	}
	

	int _path[MAX_LENGTH+2];
	int _start_length;
	int _end_length;
	int _end_pos;
};
	
int main(int argc, char *argv[])
{
	fill_permvectors();
	
	int c_not_minimal = 0;
	int c_has_unused_pieces = 0;
	int c_has_unused_pieces_in_cross = 0;
	int c_has_unused_pieces_in_square = 0;
	int c_several_components = 0;
	int c_overlap = 0;
	int c_cyclic_rectangle = 0;
	int c_cyclic_lines = 0;
	int c_unsolved = 0;
	int c_unsolved_2dir = 0;
	for (long qt = 1; qt < (1L << 16); qt++)
		if (!is_minimal(qt))
		{
			c_not_minimal++;
		}
		else if (has_unused_pieces(qt))
		{
			c_has_unused_pieces++;
		}
		else if (has_unused_pieces_in_cross(qt))
		{
			c_has_unused_pieces_in_cross++;
		}
		else if (has_unused_pieces_in_square(qt))
		{
			c_has_unused_pieces_in_square++;
		}
		else
		{
			// 2115
			
			Relation related;
			Relation horz_related;
			Relation vert_related;
			SingleDirection left_to_right(qt);
			SingleDirection up_to_down(qt);
		
			FORALLTILE(i,qt)
				FORALLTILE(j,qt)	
				{	if (GETBIT(i,1) == GETBIT(j,0) && GETBIT(i,3) == GETBIT(j,2))
					{
						related.rel[i][j] = 'X';
						related.rel[j][i] = 'X';
						horz_related.rel[i][j] = 'X';
						horz_related.rel[j][i] = 'X';
						left_to_right.rel[i][j] = 'X';
					}
					if (GETBIT(i,2) == GETBIT(j,0) && GETBIT(i,3) == GETBIT(j,1))
					{
						related.rel[i][j] = 'X';
						related.rel[j][i] = 'X';
						vert_related.rel[i][j] = 'X';
						vert_related.rel[j][i] = 'X';
						up_to_down.rel[i][j] = 'X';
					}
				}
		
			related.calculate_closure();

			SetOfQT components;
			FORALLTILE(i,qt)
			{
				int value = 0;
				FORALLTILE(j,qt)
					if (related.rel[i][j] != ' ')
						value |= BIT(j);
				components.add(value);
			}
			
			if (components.nr > 1)
			{
				c_several_components++;
				
				printf("\n");
				print_qt_first(qt);
				printf("  %d component ", components.nr);
				components.print_first();
				printf("\n");
				print_qt_second(qt);
				printf("              ");
				components.print_second();
				printf("\n");
			}
			else
			{
				// 2097
			
				horz_related.calculate_closure();
				vert_related.calculate_closure();
			
				SetOfQT overlap;
				bool horz_over_comp = overlapping_components(horz_related, vert_related, qt, "x", overlap);
				bool vert_over_comp = overlapping_components(vert_related, horz_related, qt, "y", overlap);
				
				if (horz_over_comp || vert_over_comp)
				{
					c_overlap++;
					printf("\n");
					print_qt_first(qt);
					printf("  %d overlap ", overlap.nr);
					overlap.print_first();
					printf("\n");
					print_qt_second(qt);
					printf("            ");
					overlap.print_second();
					printf("\n");
				}	
				else
				{	
					// 2085
				
					left_to_right.analyze();
					up_to_down.analyze();
					
					left_to_right.analyze_groups();
					up_to_down.analyze_groups();

					PartialSolutions partial_solutions;

					bool found_cyclic = false;
					if (left_to_right.nr_groups == 1)
					{
						SearchRepeatingRectangle searchRepeatingRectangle1(left_to_right, true, partial_solutions);
						if (searchRepeatingRectangle1.search())
						{
							c_cyclic_rectangle++;
							found_cyclic = true;
						}
					}
					if (up_to_down.nr_groups == 1 && !found_cyclic)
					{							
						SearchRepeatingRectangle searchRepeatingRectangle2(up_to_down, false, partial_solutions);
						if (searchRepeatingRectangle2.search())
						{
							c_cyclic_rectangle++;
							found_cyclic = true;
						}
					}
					if (/*left_to_right.nr_groups > 1 &&*/ !found_cyclic)
					{
						SearchRepeatingLines searchRepeatingLines(left_to_right, true, partial_solutions);
						if (searchRepeatingLines.search())
						{
							c_cyclic_lines++;
							found_cyclic = true;
						}
					}
					if (/*up_to_down.nr_groups > 1 &&*/ !found_cyclic)
					{
						SearchRepeatingLines searchRepeatingLines(up_to_down, false, partial_solutions);
						if (searchRepeatingLines.search())
						{
							c_cyclic_lines++;
							found_cyclic = true;
						}
					}
					
					if (!found_cyclic)
					{
						c_unsolved++;
						
						printf("\n");
						print_qt_first(qt);
						printf(" unsolved ");
						partial_solutions.print_first_row(qt);
						printf("\n");
						print_qt_second(qt);
						printf("          ");
						partial_solutions.print_second_row(qt);
						printf("\n\n");
						
						FORALLTILE(i,qt)					
						{
							FORALLTILE(j,qt)
								printf("%c", left_to_right.rel[i][j]);
							printf(" %3d %3d ", left_to_right.group[i], left_to_right.size[i]);
							FORALLTILE(j,qt)
								printf("%c", up_to_down.rel[i][j]);
							printf("\n");
						}
						left_to_right.analyze_groups_print();
						up_to_down.analyze_groups_print();
					
						if (left_to_right.nr_groups > 1 && up_to_down.nr_groups > 1)
							c_unsolved_2dir++;
					}
				}
			}
		}

	long left = (1L << 16) - 1;
	left -= c_not_minimal;
	printf("Not minimal: %d (left %d)\n", c_not_minimal, left);
	left -= c_has_unused_pieces;
	printf("Has unused pieces: %d (left %d)\n", c_has_unused_pieces, left);
	left -= c_has_unused_pieces_in_cross;
	printf("Has unused pieces in cross: %d (left %d)\n", c_has_unused_pieces_in_cross, left);
	left -= c_has_unused_pieces_in_square;
	printf("Has unused pieces in square: %d (left %d)\n", c_has_unused_pieces_in_square, left);
	left -= c_several_components;
	printf("Has components : %d (left %d)\n", c_several_components, left);
	left -= c_overlap;
	printf("Has overlap : %d (left %d)\n", c_overlap, left);
	left -= c_cyclic_rectangle;
	printf("Found cyclic rectangle : %d (left %d)\n", c_cyclic_rectangle, left);
	left -= c_cyclic_lines;
	printf("Found cyclic lines : %d (left %d)\n", c_cyclic_lines, left);
	printf("Unsolved : %d\n", c_unsolved);
	printf("  complex : %d\n", c_unsolved_2dir);

	return 0;
}