#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

//////////////////////////////////////////////////////////////////////////////

#define	MAX_SECONDS_STOP	58
#define	MIN_SECONDS_SPLIT	15	// Do not split before 15 seconds passed

#define NO_CHANGE_LIMIT		8
#define ADJUST_EVENT_LIMIT	3

#define NUM_RANDOM_CHANGES	3

#define MAX_COST	2147483647

bool WeCanSplit()
{
	return ((clock()/CLOCKS_PER_SEC)>=MIN_SECONDS_SPLIT);
}

bool WeShouldStop()
{
	return ((clock()/CLOCKS_PER_SEC)>=MAX_SECONDS_STOP);
}

//////////////////////////////////////////////////////////////////////////////

#define mymin(x,y) (((x)<(y))?(x):(y))
#define mymax(x,y) (((x)>(y))?(x):(y))

bool myisupper(char ch) {return (ch>='A' && ch<='Z');}

#define MAX_ROW 80
#define MAX_COL 5

bool	on_my_machine;

string	start_grid[MAX_COL];
string	goal_grid[MAX_COL];
int		num_rows;

// This struct is concerned only with Operations (Kill, Delete, Insert) which are done
//	in sequence at some position (pos), and there is no intermediate top-down-left-right-endline..
//	commands, (shift) is used to know the new position of the other operations after executing 
//	this operation

#define	NO_WAIT			0
#define	WAIT_NEXT		1
#define	WAITED_BY_PREV	2
#define	REDUNDANT		3
#define	PERFORM_FIRST	4

#define	MAX_LINE_SOLUTIONS	100			// 60
#define MAX_LINE_OPERATIONS	10			//(6->7sec, 5-><3sec)
#define MAX_INSERT			16

//////////////////////////////////////////////////////////////////////////////

struct Operation
{
	short	start_pos;		// The cursor should be at start_pos to do this action
	short	end_pos;		// The cursor will be at end_pos after doing this action
	short	shift;			// All the following operations (start_pos, end_pos) will be incremented (go right) by (shift) after doing this action (may be -ve to go left)
	short	cost;			// The cost for this operation
	short	wait;			// WAIT_NEXT if this operation should wait for the next one (needed for kill_first), WAITED_BY_PREV if the previous operation is waiting it, NO_WAIT otherwise
	string	seq;			// The sequence of commands

	//////////////////////////////////////////////////////////////////////////////

	Operation() {Set();}

	void Set(short _start_pos=0, short _end_pos=0,	short _shift=0, 
			 short _cost=0,		short _wait=0,	string _seq="")
	{
		start_pos=_start_pos; end_pos=_end_pos; shift=_shift; 
		cost=_cost; wait=_wait; seq=_seq;
	}

	//////////////////////////////////////////////////////////////////////////////

	void InitializeKillFirst(short start_pos, short wait=NO_WAIT)
	{
		Set(start_pos, 0, -(start_pos+1), 
			1, wait, "<");
	}

	void InitializeKillLast(short start_pos, short str_size, short wait = NO_WAIT)
	{
		Set(start_pos, (start_pos-1), -(str_size-start_pos), 
			1, wait, ">");
	}

	void InitializeDelete(short start_pos, short num_deletions)
	{
		string str_comm;

		for (int i=0; i<num_deletions; i++)
			str_comm = str_comm+"x";

		Set(start_pos, start_pos, -num_deletions,
			num_deletions, NO_WAIT, str_comm);
	}

	void InitializeInsert(short start_pos, string str_insert, short wait=NO_WAIT)
	{
		short num_insertions = str_insert.size();
		
		string str_comm="a";
		str_comm = str_comm+str_insert;

		Set(start_pos, start_pos+num_insertions, num_insertions,
			2*num_insertions+1, wait, str_comm);
	}

	//////////////////////////////////////////////////////////////////////////////
};

//////////////////////////////////////////////////////////////////////////////

struct LineOperation
{
	vector<Operation>	opers;
	
	int					cost;
	short				start_pos;
	short				end_pos;

	bool operator < (const LineOperation& lo) const
	{
		if (cost == lo.cost)
			return (opers.size()<lo.opers.size());
		return (cost < lo.cost);
	}
};

vector<LineOperation> all_operations[MAX_COL];

int LCS[MAX_ROW][MAX_ROW];
int LCS_DECISION[MAX_ROW][MAX_ROW];

#define LCS_STAY	0
#define LCS_S1		1
#define LCS_S2		2

//////////////////////////////////////////////////////////////////////////////
// Initialization takes place everytime first (of the start_string) is changed

void InitializeGetTheBestOperations()
{
	int i, j;
	for (i=0; i<MAX_ROW; i++)
		for (j=0; j<MAX_ROW; j++)
			LCS[i][j]=-1;
}

//////////////////////////////////////////////////////////////////////////////
// first_s2 will equal 0 for any case

int GetLCS(int line, int first_s1, int last_s1, int last_s2)
{
	if (last_s1<first_s1 || last_s2<0)
		return 0;
	
	if (LCS[last_s1][last_s2]!=-1)
		return LCS[last_s1][last_s2];

	int lcs;

	if (start_grid[line][last_s1] == goal_grid[line][last_s2])
	{
		lcs = 1+GetLCS(line, first_s1, last_s1-1, last_s2-1);
		LCS_DECISION[last_s1][last_s2]=LCS_STAY;
	}
	else
	{
		int lcs1 = GetLCS(line, first_s1, last_s1-1, last_s2);
		int lcs2 = GetLCS(line, first_s1, last_s1, last_s2-1);

		if (lcs1>lcs2)
		{
			lcs = lcs1;
			LCS_DECISION[last_s1][last_s2]=LCS_S1;
		}
		else
		{
			lcs = lcs2;
			LCS_DECISION[last_s1][last_s2]=LCS_S2;
		}
	}

	LCS[last_s1][last_s2] = lcs;
	return LCS[last_s1][last_s2];
}

//////////////////////////////////////////////////////////////////////////////

struct MatchingPos
{
	int index_s1;
	int index_s2;
};

vector<MatchingPos> GetTheLongestCommonSubsequence(int line, int first, int last)
{
	// Get the longest common subsequence
	int lcs = GetLCS(line, first, last, goal_grid[line].size()-1);

	vector<MatchingPos> match_lcs;

	if (lcs > 0)
	{
		match_lcs.resize(lcs);

		int last_s1=last, last_s2=goal_grid[line].size()-1;

		int i=lcs-1;	// i is the position to put the next common element
		int dec;

		while(i>=0)
		{
			dec = LCS_DECISION[last_s1][last_s2];

			if (dec == LCS_STAY)
			{
				match_lcs[i].index_s1=last_s1;
				match_lcs[i].index_s2=last_s2;
				last_s1--;
				last_s2--;
				i--;
			}
			else if (dec == LCS_S1)
			{
				last_s1--;
			}
			else
			{
				last_s2--;
			}
		}
	}

	return match_lcs;
}

//////////////////////////////////////////////////////////////////////////////

bool GetTheBestOperations(int line, int first, int last, vector<Operation>& line_operations)
{
	vector<MatchingPos> match_lcs = GetTheLongestCommonSubsequence(line, first, last);

	// Handle the case in which we have some characters but no match /////////////////
	// Do not do anything (This case we should delete all), and it is handled
	//	separately at first

	if (match_lcs.size()==0)
		return false;

	// When we reach here, we have at least one matching
	//	try to make benefit of it

	if (match_lcs[0].index_s1!=first)
		return false;

	if (match_lcs[match_lcs.size()-1].index_s1!=last)
		return false;

	// When we enter here, we have the first char in s1 matches a char in s2
	//	Also, we have the last char in s1 matches a char in s2

	// Note: in the following cases, except the last, we try to match the 2 strings
	//			until a matcning occurrence

	string& s1 = start_grid[line];
	string& s2 = goal_grid[line];

	int len1 = s1.size();
	int len2 = s2.size();
	
	int i;
	int match_s1=match_lcs[0].index_s1;
	int match_s2=match_lcs[0].index_s2;

	// Handle the starting case ////////////////////////////////////////////

	int kill_first = first-1;

	if (match_s2==0)	// The first char in s1 matches the first char in s2
	{
		if (kill_first >= 0)
		{
			Operation op_kill;
			op_kill.InitializeKillFirst(kill_first);
			line_operations.push_back(op_kill);
		}
	}
	else				// The first char in s1 matches a char in s2
	{
		if (kill_first >= 0)
		{
			// Make insert command (for chars in s2 before match), 
			//	and the kill_first will wait it

			if (kill_first-1 >= 0)
			{
				// Make Redundant Kill

				Operation op_kill;
				op_kill.InitializeKillFirst(kill_first-1, REDUNDANT);
				line_operations.push_back(op_kill);
			}

			Operation op_kill;
			op_kill.InitializeKillFirst(kill_first, WAIT_NEXT);
			line_operations.push_back(op_kill);

			Operation op_insert;
			op_insert.InitializeInsert(kill_first, s2.substr(0, match_s2), WAITED_BY_PREV);
			if (op_insert.cost > 1)
				line_operations.push_back(op_insert);
		}
		else	// We will not take benefit of this case
		{
			return false;
		}
	}

	int prev_match_s1 = match_s1;
	int prev_match_s2 = match_s2;

	// End Handle the starting case ////////////////////////////////////////////

	// When we enter here, the 2 strings are matched upto and including
	//	the first matching occurrence

	for (i=1; i<match_lcs.size(); i++)	// For each matching, we will make operations to match all somethings before it
	{
		prev_match_s1 = match_s1;
		prev_match_s2 = match_s2;

		match_s1 = match_lcs[i].index_s1;
		match_s2 = match_lcs[i].index_s2;

		if (match_s1 == prev_match_s1+1 && match_s2 == prev_match_s2+1)
			continue;

		// Make the insert operations

		Operation op_insert;
		op_insert.InitializeInsert(prev_match_s1, s2.substr(prev_match_s2+1, match_s2-(prev_match_s2+1)));
		if (op_insert.cost > 1)
			line_operations.push_back(op_insert);

		// Make the delete operations

		Operation op_delete;
		op_delete.InitializeDelete(prev_match_s1+1, match_s1-(prev_match_s1+1));
		if (op_delete.cost > 0)
			line_operations.push_back(op_delete);
	}

	// Handle the end line case ////////////////////////////////////////////
	
	int kill_last = last+1;

	if (match_s2==len2-1)	// The last char in s1 matches the last char in s2
	{
		if (kill_last < len1)
		{
			Operation op_kill;
			op_kill.InitializeKillLast(kill_last, len1, NO_WAIT);
			line_operations.push_back(op_kill);
		}
	}
	else				// The last char in s1 matches a char in s2
	{
		if (kill_last < len1)
		{
			// Make insert command (for chars in s2 after match), and the kill_last
			//	Make the insert command wait for the kill

			Operation op_insert;
			//op_insert.InitializeInsert(last, s2.substr(match_s2+1, len2-(match_s2+1)), WAIT_NEXT);
			op_insert.InitializeInsert(last, s2.substr(match_s2+1, len2-(match_s2+1)), NO_WAIT);
			if (op_insert.cost > 1)
				line_operations.push_back(op_insert);

			Operation op_kill;
			//op_kill.InitializeKillLast(kill_last, len1, WAITED_BY_PREV);
			op_kill.InitializeKillLast(kill_last, len1, NO_WAIT);
			line_operations.push_back(op_kill);
		}
		else
		{
			Operation op_insert;
			op_insert.InitializeInsert(last, s2.substr(match_s2+1, len2-(match_s2+1)));
			if (op_insert.cost > 1)
				line_operations.push_back(op_insert);
		}
	}

	// End Handle the end line case ////////////////////////////////////////

	return true;
}

//////////////////////////////////////////////////////////////////////////////
// This fn will change # of operations in the line so as it will be maximum # <= MAX_LINE_OPERATIONS

void CombineLineOperations(vector<Operation>& opers)
{
	int i, j;

	while (opers.size() > MAX_LINE_OPERATIONS)
	{
		int iminspace = MAX_COST;
		int ifirst_oper=-1;
		int iminspace_cost=-1;

		for (i=0; i<opers.size()-1; i++)
		{
			if (opers[i].wait == REDUNDANT || opers[i].wait == WAIT_NEXT)
				continue;

			if (opers[i+1].start_pos - opers[i].start_pos < iminspace ||
				opers[i+1].start_pos - opers[i].start_pos == iminspace &&
				opers[i+1].cost + opers[i].cost < iminspace_cost)
			{
				iminspace = (opers[i].shift + opers[i+1].start_pos) - opers[i].end_pos;
				ifirst_oper = i;
				iminspace_cost = opers[i].cost + iminspace + opers[i+1].cost;
			}
		}

		if (iminspace == MAX_COST)
			return;

		string right; for (j=0; j<iminspace; j++) right += "r";

		i = ifirst_oper;
		
		Operation new_oper;

		new_oper.start_pos = opers[i].start_pos;
		new_oper.end_pos = opers[i].shift + opers[i+1].end_pos;
		new_oper.cost = iminspace_cost;
		new_oper.seq = opers[i].seq + right + opers[i+1].seq;
		new_oper.shift = opers[i].shift + opers[i+1].shift;
		new_oper.wait = opers[i].wait;

		opers[i] = new_oper;
		opers.erase(opers.begin()+(i+1));
	}
}

//////////////////////////////////////////////////////////////////////////////
// In current implementation, it will use it even if it is not better

void UseTheOperationIfBetter(int line, vector<Operation>& line_operations)
{
	LineOperation lo;
	lo.opers = line_operations;
	all_operations[line].push_back(lo);
}

//////////////////////////////////////////////////////////////////////////////

void GenerateTrivialCase1(int line, vector<Operation>& line_operations)
{
	// Make the trivial case of:
	//	1) Insert All chars in from the goal (st last of the start)
	//	2) kill_first all previously existing chars after the insertions

	if (start_grid[line].size()-2 >= 0)
	{
		// Make Redundant Kill

		Operation op_kill;
		op_kill.InitializeKillFirst(start_grid[line].size()-2, REDUNDANT);
		line_operations.push_back(op_kill);
	}

	Operation op_kill;
	op_kill.InitializeKillFirst(start_grid[line].size()-1, WAIT_NEXT);
	line_operations.push_back(op_kill);

	Operation op_insert;
	op_insert.InitializeInsert(start_grid[line].size()-1, goal_grid[line], WAITED_BY_PREV);
	if (op_insert.cost > 1)
		line_operations.push_back(op_insert);
}

//////////////////////////////////////////////////////////////////////////////

void GenerateTrivialCase2(int line, vector<Operation>& line_operations)
{
	// Make the trivial case of:
	//	1) kill_first all elements then insert all elements at the empty line

	Operation op_trivial;

	op_trivial.seq = "<a";
	op_trivial.seq += goal_grid[line];
	op_trivial.cost = 2+2*goal_grid[line].size();
	op_trivial.start_pos = start_grid[line].size()-1;
	op_trivial.end_pos = goal_grid[line].size()-1;
	op_trivial.shift = goal_grid[line].size()-start_grid[line].size();
	op_trivial.wait = NO_WAIT;

	line_operations.push_back(op_trivial);
}

//////////////////////////////////////////////////////////////////////////////

void GenerateTrivialCase3(int line, vector<Operation>& line_operations)
{
	// Make the trivial case of:
	//	1) kill_last all elements then insert all elements at the empty line

	Operation op_trivial;

	op_trivial.seq = ">a";
	op_trivial.seq += goal_grid[line];
	op_trivial.cost = 2+2*goal_grid[line].size();
	op_trivial.start_pos = 0;
	op_trivial.end_pos = goal_grid[line].size()-1;
	op_trivial.shift = goal_grid[line].size()-start_grid[line].size();
	op_trivial.wait = NO_WAIT;

	line_operations.push_back(op_trivial);
}

//////////////////////////////////////////////////////////////////////////////

void CombineLineOperationsAll(int line)
{
	int j;

	for (j=0; j<all_operations[line].size(); j++)
	{
		// Deal with the case of 111
		
		vector<Operation>& opers = all_operations[line][j].opers;

		if (opers.size() >= 2 && opers[0].wait != REDUNDANT)
		{
			if (opers[0].seq == "<" && opers[0].start_pos == 0)
			{
				if (opers[1].seq.size() >= 2 && opers[1].seq[0] == 'a' && 
					opers[1].start_pos == 0)
				{
					if (opers[1].seq[1] == start_grid[line][0])
					{
						opers[1].seq.erase(1, 1);
						opers[1].cost -= 2;
						opers[1].shift--;
						opers[1].end_pos--;
						opers[1].wait = NO_WAIT;

						if (opers[1].cost == 1)
						{
							opers.erase(opers.begin()+1);
						}

						opers.erase(opers.begin());

						if (opers.size() == 0)
						{
							Operation op_none;
							opers.push_back(op_none);
						}
					}
				}
			}
		}

		CombineLineOperations(all_operations[line][j].opers);
	}
}

//////////////////////////////////////////////////////////////////////////////

void ComputeLineOperations(int line)
{
	string& s1 = start_grid[line];
	string& s2 = goal_grid[line];

	int len1 = s1.size();
	int len2 = s2.size();

	int kill_first, kill_last;

	// kill_first will kill chars upto this index
	// kill_first will kill chars from this index and upto last
	// Do not try to delete the whole line!
	
	vector<Operation> line_operations;

	if (s1==s2)
	{
		Operation op_none;

		line_operations.push_back(op_none);
		UseTheOperationIfBetter(line, line_operations);

		return;
	}

	line_operations.clear();
	GenerateTrivialCase1(line, line_operations);
	UseTheOperationIfBetter(line, line_operations);

	line_operations.clear();
	GenerateTrivialCase2(line, line_operations);
	UseTheOperationIfBetter(line, line_operations);

	line_operations.clear();
	GenerateTrivialCase3(line, line_operations);
	UseTheOperationIfBetter(line, line_operations);

	// Try all combinations of kill_first and kill_last
	// But avoid killing the whole line, because when we do this, 
	//	we will not be able to insert anything in it
	
	for (kill_first=-1; kill_first<=len1-2; kill_first++)
	{
		InitializeGetTheBestOperations();

		for (kill_last=kill_first+2; kill_last<=len1; kill_last++)
		{
			line_operations.clear();

			if (GetTheBestOperations(line, kill_first+1, kill_last-1, line_operations))
				UseTheOperationIfBetter(line, line_operations);
		}
	}
}

//****************************************************************************
//////////////////////////////////////////////////////////////////////////////

// We will create array of PerformOperation and we will index it
// For each time of different indexing, we will reset all things in this array

struct PerformOperation
{
	short	start_pos_old;		// Used for restoring
	short	end_pos_old;		// Used for restoring
	short	shift_old;		// Used for restoring

	short	start_pos;		// The cursor should be at start_pos to do this action
	short	end_pos;		// The cursor will be at end_pos after doing this action
	short	shift;			// All the following operations (start_pos, end_pos) will be incremented (go right) by (shift) after doing this action (may be -ve to go left)
	short	cost;			// The cost for this operation
	short	wait;			// WAIT_NEXT if this operation should wait for the next one (needed for kill_first), WAITED_BY_PREV if the previous operation is waiting it, NO_WAIT otherwise
	string	seq;			// The sequence of commands

	short	index;			// The index of this operation in the array which indexes these operations
	bool	done;

	void Set(short _start_pos=0, short _end_pos=0,	short _shift=0, 
			 short _cost=0,		short _wait=0,	string _seq="")
	{
		start_pos_old=start_pos=_start_pos; end_pos_old=end_pos=_end_pos; 
		shift_old=shift=_shift; 
		cost=_cost; wait=_wait; seq=_seq;
	}

	void InitializeInsert(short start_pos, string str_insert, short wait=NO_WAIT)
	{
		short num_insertions = str_insert.size();
		
		string str_comm="a";
		str_comm = str_comm+str_insert;

		Set(start_pos, start_pos+num_insertions, num_insertions,
			2*num_insertions+1, wait, str_comm);

		done = false;
	}
};

//////////////////////////////////////////////////////////////////////////////

void SplitLineOperations(vector<PerformOperation>& opers)
{
	int i;
	
	while (opers.size() < MAX_LINE_OPERATIONS)
	{
		int ioper=-1;
		int max_insert=-1;
		int max_type=-1;

		for (i=0; i<opers.size(); i++)
		{
			if (opers[i].wait == REDUNDANT || opers[i].wait == WAIT_NEXT)
				continue;

			int type;
			
			if (opers[i].seq.size()>0 && opers[i].seq[0] == 'a')
			{
				type=0;
			}
			else if (opers[i].seq.size()>1 && opers[i].seq[1] == 'a' &&
					(opers[i].seq[0]=='<' || opers[i].seq[0]=='>'))
			{
				type=1;
			}
			else
			{
				continue;
			}
			
			// Check that all chars are uppercase letters
			
			bool all_insert = true;

			for (int j=type+1; j<opers[i].seq.size(); j++)
			{
				if (!myisupper(opers[i].seq[j]))
				{
					all_insert = false;
					break;
				}
			}

			if (!all_insert)
				continue;

			// Now, all chars are uppercase

			int num_insert = opers[i].seq.size()-1;

			if (num_insert > MAX_INSERT && num_insert > max_insert)
			{
				max_insert = num_insert;
				ioper = i;
				max_type = type;
			}
		}

		if (max_insert == -1)
			return;

		i = ioper;
		
		string cur_seq = opers[i].seq.substr(max_type+1, opers[i].seq.size()-1);
		int ifirst_half = cur_seq.size()/2;
		int isecond_half = cur_seq.size()-ifirst_half;

		PerformOperation oper1, oper2;
		string str_first_half = cur_seq.substr(0, ifirst_half);
		string str_second_half = cur_seq.substr(ifirst_half, isecond_half);

		if (max_type==0)
		{
			oper1.InitializeInsert(	opers[i].start_pos,
									str_first_half, 
									opers[i].wait);

			oper2.InitializeInsert(	opers[i].start_pos,
									str_second_half, 
									NO_WAIT);
		}
		else
		{
			oper1.seq = opers[i].seq.substr(0, 2);
			oper1.seq += str_first_half;
			oper1.cost = 2+2*str_first_half.size();
			
			oper1.start_pos_old = oper1.start_pos = opers[i].start_pos;
			oper1.end_pos_old = oper1.end_pos = str_first_half.size()-1;

			oper1.shift_old = oper1.shift = str_first_half.size()-1;
			oper1.wait = PERFORM_FIRST;

			oper2.InitializeInsert( 0,
									str_second_half, 
									NO_WAIT);
		}
	
		opers[i] = oper1;
		opers.insert(opers.begin()+(i+1), oper2);
	}
}

//////////////////////////////////////////////////////////////////////////////

struct CursorPos
{
	short	row;
	short	col;
};

//////////////////////////////////////////////////////////////////////////////

struct PerformOperIndex
{
	short iline;
	short ioper;
};

#define NO_MOVE 0
#define MOVE_MOVE 1
#define SWAP_MOVE 2

struct SolutionMove
{
	char	type;
	short	index1;
	short	index2;
};

struct Solution
{
	short						line_operations_used[MAX_COL];	// The index of the used operation vector for the line i
	vector<PerformOperIndex>	indexed_operations;		// The real order of execution of perform_operations
	vector<PerformOperation>	perform_operations[MAX_COL];
	int							all_cost;
	string						str_moves;
	SolutionMove				last_move;

	bool operator < (const Solution& sol) const
	{
		return (this->all_cost < sol.all_cost);
	}
};

Solution best_sol;
Solution restore_sol;

#define MAX_SOLS_LEV2	5
#define MAX_SOLS_LEV3	5			// 10 takes about 10 secs (For each iteration)

#define MAX_HASH	(1000001)

bool enable_hash;

char hash_table[MAX_HASH];

Solution all_sols[MAX_SOLS_LEV2];

int	num_sols;

//////////////////////////////////////////////////////////////////////////////
// These members will be generated every time

short						line_sizes[MAX_COL];
CursorPos					cp;

//////////////////////////////////////////////////////////////////////////////
// Solution cur_sol;
// The following 4 members for the current solution

short						line_operations_used[MAX_COL];	// The index of the used operation vector for the line i
vector<PerformOperIndex>	indexed_operations;		// The real order of execution of perform_operations
vector<PerformOperation>	perform_operations[MAX_COL];
int							all_cost;
string						str_moves;
SolutionMove				last_move;

//////////////////////////////////////////////////////////////////////////////

void CopySolution(Solution& dst, Solution& src)
{
	dst.all_cost = src.all_cost;
	dst.str_moves = src.str_moves;
	dst.indexed_operations = src.indexed_operations;
	dst.last_move = src.last_move;

	for (int i=0; i<num_rows; i++) 
	{
		dst.line_operations_used[i] = src.line_operations_used[i];
		dst.perform_operations[i] = src.perform_operations[i];
	}
}

//////////////////////////////////////////////////////////////////////////////

void CopyCurrentSolution(Solution& dst)
{
	dst.all_cost = all_cost;
	dst.str_moves = str_moves;
	dst.indexed_operations = indexed_operations;
	dst.last_move = last_move;

	for (int i=0; i<num_rows; i++) 
	{
		dst.line_operations_used[i] = line_operations_used[i];
		dst.perform_operations[i] = perform_operations[i];
	}
}

//////////////////////////////////////////////////////////////////////////////
// Go down or up until the row, then go left or right until the col

string GetDirectDistanceBetweenTwoPositions(CursorPos cp1, CursorPos cp2)
{
	int i;
	string str_go;

	while(cp1.row !=  cp2.row)
	{
		if (cp1.row < cp2.row)
		{
			cp1.row++;
			if (line_sizes[cp1.row] <= cp1.col) cp1.col=line_sizes[cp1.row]-1;
			str_go = str_go + "d";
		}
		
		if (cp1.row > cp2.row)
		{
			cp1.row--;
			if (line_sizes[cp1.row] <= cp1.col) cp1.col=line_sizes[cp1.row]-1;
			str_go = str_go + "u";
		}
	}

	int iNumMovesDirect = abs(cp1.col-cp2.col);
	int iNumMovesEnd = 1+((line_sizes[cp1.row]-1)-cp2.col);
	int iNumMovesStart = 1+(cp2.col);

	int iNumMovesMin = mymin(iNumMovesDirect, mymin(iNumMovesEnd, iNumMovesStart));
	
	if (iNumMovesMin == iNumMovesDirect)
	{
		for (i=0; i<abs(cp1.col-cp2.col); i++)
		{
			if (cp1.col > cp2.col) str_go = str_go + "l";
			else str_go = str_go + "r";
		}
	}
	else if (iNumMovesMin == iNumMovesEnd)
	{
		str_go = str_go + "e";
		for (i=0; i<((line_sizes[cp1.row]-1)-cp2.col); i++)
			str_go = str_go + "l";
	}
	else
	{
		str_go = str_go + "b";
		for (i=0; i<cp2.col; i++)
			str_go = str_go + "r";
	}

	return str_go;
}

//////////////////////////////////////////////////////////////////////////////

string GetShortestDistanceBetweenTwoPositions(CursorPos cp1, CursorPos cp2)
{
	int i;
	string str_go;

	str_go = GetDirectDistanceBetweenTwoPositions(cp1, cp2);

	for (i=0; i<num_rows; i++)
	{
		CursorPos cpmid;

		cpmid.col = line_sizes[i]-1;
		cpmid.row = i;

		string str_indir = GetDirectDistanceBetweenTwoPositions(cp1, cpmid) +
							GetDirectDistanceBetweenTwoPositions(cpmid, cp2);

		if (str_indir.size() < str_go.size())
			str_go = str_indir;
	}

	return str_go;
}

//////////////////////////////////////////////////////////////////////////////

// ipo is an index in perform_operations
// Note: It is a condition that perform_operations are ordered in the trivial way
//		(First line, then next line ....)
// So, This ExecuteOperation() is correct and will not be changed
//	Also, it is required that this operation can be executed now (The next and prev 
//			conditions are not tested here, they should be tested before calling this fn)

int ExecuteOperation(PerformOperIndex poi)
{
	int i;
	
	PerformOperation& perform_oper = perform_operations[poi.iline][poi.ioper];

	if (perform_oper.cost == 0)		// None Operation, Or deleted Operation
		return -1;

	if (perform_oper.wait == REDUNDANT && 
		perform_operations[poi.iline][poi.ioper+1].done)
	{
		return -1;
	}

	// Move the cursor to the current position
	
	CursorPos cp_new;
	cp_new.row = poi.iline;
	cp_new.col = perform_oper.start_pos;

	string str_go = GetShortestDistanceBetweenTwoPositions(cp, cp_new);

	str_moves += str_go;
	all_cost += str_go.size();
	
	cp = cp_new;

	// Execute the operation and make updates

	perform_oper.done = true;

	// This is done after splitting insert

	if (str_moves.size()>0 && 
		myisupper(str_moves[str_moves.size()-1]) &&
		perform_oper.seq.size()>0 &&
		perform_oper.seq[0]=='a')
	{
		str_moves += perform_oper.seq.substr(1, perform_oper.seq.size()-1);
		all_cost += perform_oper.cost-1;
	}
	else
	{
		str_moves += perform_oper.seq;
		all_cost += perform_oper.cost;
	}
	
	cp.col = perform_oper.end_pos;

	line_sizes[poi.iline] += perform_oper.shift;

	for (i=poi.ioper+1; i<perform_operations[poi.iline].size(); i++)
	{
		perform_operations[poi.iline][i].start_pos += perform_oper.shift;
		perform_operations[poi.iline][i].end_pos += perform_oper.shift;
	}

	if (perform_oper.wait == REDUNDANT)
	{
		perform_operations[poi.iline][poi.ioper+1].shift -= perform_oper.shift;
		perform_operations[poi.iline][poi.ioper+1].end_pos = 0;
	}

	if (perform_oper.wait == PERFORM_FIRST)
	{
		line_sizes[poi.iline] = perform_oper.seq.size()-2;
	}

	return str_go.size();
}

//////////////////////////////////////////////////////////////////////////////

bool change_occurs;

int ComputeHash(int& cost, string& moves)
{
	int moves_size = moves.size();

	int hash = (29 * cost * moves_size) % MAX_HASH;

	for (int i=0; i<moves_size; i++)
	{
		hash = (hash * (i+(int) moves[i])) % MAX_HASH;
	}

	return hash;
}

//////////////////////////////////////////////////////////////////////////////

int GetMaxCostIndex()
{
	int max_cost_index = 0;

	for (int i=1; i<num_sols; i++)
	{
		if (all_sols[i].all_cost > all_sols[max_cost_index].all_cost)
		{
			max_cost_index = i;
		}
	}

	return max_cost_index;
}

//////////////////////////////////////////////////////////////////////////////

string	test_grid[MAX_COL];

bool TestOutput(string& moves)
{
	CursorPos cp_test;
	cp_test.row = 0;
	cp_test.col = 0;

	bool insert_mode = false;

	char c;
	
	int i;
	
	for (i=0; i<num_rows; i++)
	{
		test_grid[i]=start_grid[i];
	}
	
	for (i=0; i<moves.size(); i++)
	{
		c = moves[i];

		if (myisupper(c))
		{
			if (!insert_mode) return false;
			insert_mode=true;

			test_grid[cp_test.row].insert(cp_test.col+1, 1, c);
			cp_test.col++;
		}
		else if (c=='a')	
		{
			if (insert_mode) return false;
			insert_mode=true;

			if (i+1>=moves.size())
				return false;

			if (!myisupper(moves[i+1])) return false;
		}	
		else 
		{
			insert_mode=false;
		}

		if (c=='b')	
		{
			if (cp_test.col == 0) return false;
			cp_test.col = 0; 
		}
		
		if (c=='e')	
		{
			if (cp_test.col == test_grid[cp_test.row].size()-1) return false;
			cp_test.col = test_grid[cp_test.row].size()-1; 
		}

		if (c=='l') 
		{
			cp_test.col--; if (cp_test.col<0) return false;
		}

		if (c=='r') 
		{
			cp_test.col++; 
			if (cp_test.col>=test_grid[cp_test.row].size()) return false;
		}

		if (c=='u') 
		{
			cp_test.row--; 
			if (cp_test.row<0) return false;

			if (cp_test.col>=test_grid[cp_test.row].size()) 
			{
				cp_test.col=test_grid[cp_test.row].size()-1;
			}
		}

		if (c=='d') 
		{
			cp_test.row++; 
			if (cp_test.row>=num_rows) return false;
			
			if (cp_test.col>=test_grid[cp_test.row].size()) 
			{
				cp_test.col=test_grid[cp_test.row].size()-1;
			}
		}

		if (c=='x') 
		{
			test_grid[cp_test.row].erase(cp_test.col,1); 
		}

		if (c=='<') 
		{
			if (cp_test.col == test_grid[cp_test.row].size()-1)
			{
				if (i+2>=moves.size())
					return false;

				if (moves[i+1]!='a' || !myisupper(moves[i+2]))
					return false;

				if (insert_mode) return false;
				insert_mode=true;

				test_grid[cp_test.row] = moves[i+2];
				cp_test.col = 0;

				i++;
				i++;
			}
			else
			{
				test_grid[cp_test.row].erase(0,cp_test.col+1);
				cp_test.col = 0;
			}
		}

		if (c=='>') 
		{
			if (cp_test.col == 0)
			{
				if (i+2>=moves.size())
					return false;

				if (moves[i+1]!='a' || !myisupper(moves[i+2]))
					return false;

				if (insert_mode) return false;
				insert_mode=true;

				test_grid[cp_test.row] = moves[i+2];
				cp_test.col = 0;

				i++;
				i++;
			}
			else
			{
				test_grid[cp_test.row].erase(cp_test.col, test_grid[cp_test.row].size()-cp_test.col);
				cp_test.col = test_grid[cp_test.row].size()-1;
			}
		}
	}

	bool bSuccess = true;
	
	for (i=0; i<num_rows; i++)
	{
		if (test_grid[i]!=goal_grid[i])
		{
			bSuccess = false;
		}
	}

	return bSuccess;
}

//////////////////////////////////////////////////////////////////////////////

void OutputOperations()
{
	int i;
	string all_waitings[]={"NO_WAIT", "WAIT_NEXT", "WAITED_BY_PREV", "REDUNDANT", "PERFORM_FIRST"};
	
	for (i=0; i<indexed_operations.size(); i++)
	{
		PerformOperation& po = 
			perform_operations[indexed_operations[i].iline][indexed_operations[i].ioper];

		cout << "Operation " << i << ":" << "\t";
		
		cout << "Line " << indexed_operations[i].iline << "\t";
		cout << "StartPos " << po.start_pos_old << "\t";
		cout << "EndPos " << po.end_pos_old << "\t";
		cout << "Shift " << po.shift_old << "\t";
		cout << "Sequence " << po.seq << "\t";
		cout << "Wait " << all_waitings[po.wait] << "\t";
		
		cout << endl;
	}
}

//////////////////////////////////////////////////////////////////////////////

void AdjustBestSolution(int max_cost_index=-1)
{
	if (!TestOutput(str_moves))
	{
		if (on_my_machine)	// The program is running at my machine
		{
			int i;

			cout << "\nTestOutput Failed Middle FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF.\n\n";
			cout << str_moves << " " << (char)(last_move.type+'0')  << " " << endl << endl;

			cout << "goal:\n";
			for (i=0; i<num_rows; i++)
				cout << goal_grid[i] << endl;

			cout << "result:\n";
			for (i=0; i<num_rows; i++)
				cout << test_grid[i] << endl;

			cout << endl;

			OutputOperations();

			cout << endl;

			exit(0);
		}

		return;
	}
	
	if (all_cost < best_sol.all_cost)
	{
		CopyCurrentSolution(best_sol);
		CopyCurrentSolution(restore_sol);
		change_occurs = true;
	}
	else if (all_cost < restore_sol.all_cost)
	{
		CopyCurrentSolution(restore_sol);
	}

	if (enable_hash)
	{
		int hash = ComputeHash(all_cost, str_moves);
		if (hash_table[hash]==1)
			return;
		hash_table[hash]=1;
	}

	if (max_cost_index==-1)
		max_cost_index = GetMaxCostIndex();

	if (all_cost < all_sols[max_cost_index].all_cost)
	{
		CopyCurrentSolution(all_sols[max_cost_index]);
		change_occurs = true;
	}
}

//////////////////////////////////////////////////////////////////////////////

void ExecuteAllOperations()
{
	int i;

	int max_cost_index = GetMaxCostIndex();
	int max_cost = all_sols[max_cost_index].all_cost;

	cp.row=0;
	cp.col=0;

	all_cost = 0;
	str_moves = "";

	for (i=0; i<num_rows; i++)
	{
		line_sizes[i]=start_grid[i].size();
	}

	int* accum_cost = new int[indexed_operations.size()+1];
	accum_cost[indexed_operations.size()]=0;

	for (i=indexed_operations.size()-1; i>=0; i--)
	{
		int cost_this;

		PerformOperation& po = perform_operations[indexed_operations[i].iline][indexed_operations[i].ioper];
		
		if (po.wait == REDUNDANT)
		{
			cost_this=0;
		}
		else
		{
			cost_this=po.cost;
			if (po.seq.size()>0 && po.seq[0]=='a') cost_this--;
		}

		accum_cost[i]=cost_this+accum_cost[i+1];
	}

	for (i=0; i<indexed_operations.size(); i++)
	{
		ExecuteOperation(indexed_operations[i]);

		if (all_cost+accum_cost[i+1] > max_cost)
		{
			delete[] accum_cost;
			return;
		}
	}

	delete[] accum_cost;

	AdjustBestSolution(max_cost_index);
}

//////////////////////////////////////////////////////////////////////////////

void GetInfoFromBasicOperations(int line, int ioper, PerformOperation& oper)
{
	vector<Operation>& current_opers = all_operations[line][line_operations_used[line]].opers;

	oper.done = false;

	oper.start_pos_old = oper.start_pos = current_opers[ioper].start_pos;
	oper.end_pos_old = oper.end_pos = current_opers[ioper].end_pos;
	oper.shift_old = oper.shift = current_opers[ioper].shift;
	oper.cost = current_opers[ioper].cost;
	oper.wait = current_opers[ioper].wait;
	oper.seq = current_opers[ioper].seq;
}

//////////////////////////////////////////////////////////////////////////////

int GetNumberOfOperationsInCurrentLineSol(int line)
{
	return all_operations[line][line_operations_used[line]].opers.size();
}

//////////////////////////////////////////////////////////////////////////////
// In this function, you should reset perform_operations to its original values
// This function prepare the current solution to be a copy of a previous solution (ready to be modified)

//////////////////////////////////////////////////////////////////////////////
// In this function, you should reset perform_operations to its original values
// This function prepare the current solution to be a copy of a previous solution (ready to be modified)

void ResetCurrentSolution()
{
	int i, j;
	
	for (i=0; i<num_rows; i++)
	{
		for (j=0; j<perform_operations[i].size(); j++)
		{
			PerformOperation& po = perform_operations[i][j];
			
			po.start_pos = po.start_pos_old;
			po.end_pos = po.end_pos_old;
			po.shift = po.shift_old;
			po.done = false;
		}
	}
}

//////////////////////////////////////////////////////////////////////////////

void RestoreSolution(Solution& sol)
{
	int i;
	
	for (i=0; i<num_rows; i++) 
	{
		line_operations_used[i] = sol.line_operations_used[i];
		perform_operations[i] = sol.perform_operations[i];
	}

	last_move = sol.last_move;

	indexed_operations = sol.indexed_operations;

	// The previos line is not sufficient to get the previous indexes!
	//	We should also update the values which we have damaged in perform_operations!

	for (i=0; i<indexed_operations.size(); i++)
	{
		perform_operations[indexed_operations[i].iline][indexed_operations[i].ioper].index = i;
	}

	ResetCurrentSolution();
}

//////////////////////////////////////////////////////////////////////////////

bool CanMoveOneOperation(short index1, short index2)
{
	if (index1==index2)
		return false;

	if (index1 < index2)
	{
		if (perform_operations[indexed_operations[index2].iline][indexed_operations[index2].ioper].wait == WAIT_NEXT &&
			perform_operations[indexed_operations[index2].iline][indexed_operations[index2].ioper+1].index == index1)
		{
			return false;
		}
		
		if (perform_operations[indexed_operations[index1].iline][indexed_operations[index1].ioper].wait == WAITED_BY_PREV &&
			perform_operations[indexed_operations[index1].iline][indexed_operations[index1].ioper-1].index <= index2)
		{
			return false;
		}
	}
	else
	{
		if (perform_operations[indexed_operations[index1].iline][indexed_operations[index1].ioper].wait == WAIT_NEXT &&
			perform_operations[indexed_operations[index1].iline][indexed_operations[index1].ioper+1].index >= index2)
		{
			return false;
		}
		
		if (perform_operations[indexed_operations[index2].iline][indexed_operations[index2].ioper].wait == WAITED_BY_PREV &&
			perform_operations[indexed_operations[index2].iline][indexed_operations[index2].ioper-1].index == index1)
		{
			return false;
		}
	}
	
	// The following for not moving redundant kill
	//	The only available move for the redundant kill when index1 > index2 is to move 
	//	it to become in the position of the kill operation which after it
	
	if (index1 > index2 &&
		perform_operations[indexed_operations[index1].iline][indexed_operations[index1].ioper].wait == REDUNDANT &&
		perform_operations[indexed_operations[index1].iline][indexed_operations[index1].ioper+1].index != index2)
	{
		return false;
	}

	// Do not move the element which has been lastly moved
	
	if (last_move.type == MOVE_MOVE)
	{
		if (last_move.index2 == index1)
		{
			return false;
		}
	}

	return true;
}

//////////////////////////////////////////////////////////////////////////////

bool MoveOneOperation(short index1, short index2)
{
	int i;
	
	// Move index1 to index2
	
	if (index1 < index2)
	{
		PerformOperIndex poi_temp = indexed_operations[index1];

		for (i=index1+1; i<=index2; i++)
		{
			indexed_operations[i-1] = indexed_operations[i];
		}

		indexed_operations[index2] = poi_temp;
	}
	else
	{
		PerformOperIndex poi_temp = indexed_operations[index1];

		for (i=index1-1; i>=index2; i--)
		{
			indexed_operations[i+1] = indexed_operations[i];
		}

		indexed_operations[index2] = poi_temp;
	}

	for (int w=0; w<indexed_operations.size(); w++)
		perform_operations[indexed_operations[w].iline][indexed_operations[w].ioper].index = w;

	last_move.type = MOVE_MOVE;
	last_move.index1 = index1;
	last_move.index2 = index2;

	for (i=0; i<num_rows; i++)
	{
		if (perform_operations[i][0].wait == PERFORM_FIRST)
		{
			int j;
			
			for (j=1; j<perform_operations[i].size(); j++)
			{
				if (perform_operations[i][j].index < perform_operations[i][0].index)
					return false;
			}
		}
	}
		
	return true;
}

//////////////////////////////////////////////////////////////////////////////

bool CanSwapTwoOperations(short index1, short index2)
{
	short min_index = mymin(index1, index2);
	short max_index = mymax(index1, index2);

	if (perform_operations[indexed_operations[max_index].iline][indexed_operations[max_index].ioper].wait == WAIT_NEXT &&
		perform_operations[indexed_operations[max_index].iline][indexed_operations[max_index].ioper+1].index >= min_index)
	{
		return false;
	}
	
	if (perform_operations[indexed_operations[min_index].iline][indexed_operations[min_index].ioper].wait == WAITED_BY_PREV &&
		perform_operations[indexed_operations[min_index].iline][indexed_operations[min_index].ioper-1].index <= max_index)
	{
		return false;
	}

	// The following for not swapping redundant kill if it has no effect 
	//	(occurs after its friend kill)
	
	if (perform_operations[indexed_operations[index1].iline][indexed_operations[index1].ioper].wait == REDUNDANT &&
		perform_operations[indexed_operations[index1].iline][indexed_operations[index1].ioper+1].index < index1)
	{
		return false;
	}

	if (perform_operations[indexed_operations[index2].iline][indexed_operations[index2].ioper].wait == REDUNDANT &&
		perform_operations[indexed_operations[index2].iline][indexed_operations[index2].ioper+1].index < index2)
	{
		return false;
	}

	// Do not swap the elements which have been lastly swapped
	
	if (last_move.type == SWAP_MOVE)
	{
		if (last_move.index1 == index1 && last_move.index2 == index2 ||
			last_move.index1 == index2 && last_move.index2 == index1)
		{
			return false;
		}
	}

	return true;
}

//////////////////////////////////////////////////////////////////////////////

bool SwapTwoOperations(short index1, short index2)
{
	// Swap the two indexes
	
	perform_operations[indexed_operations[index1].iline][indexed_operations[index1].ioper].index = index2;
	perform_operations[indexed_operations[index2].iline][indexed_operations[index2].ioper].index = index1;

	PerformOperIndex poi_temp = indexed_operations[index1];
	indexed_operations[index1] = indexed_operations[index2];
	indexed_operations[index2] = poi_temp;

	last_move.type = SWAP_MOVE;
	last_move.index1 = index1;
	last_move.index2 = index2;

	int i;

	for (i=0; i<num_rows; i++)
	{
		if (perform_operations[i][0].wait == PERFORM_FIRST)
		{
			int j;
			
			for (j=1; j<perform_operations[i].size(); j++)
			{
				if (perform_operations[i][j].index < perform_operations[i][0].index)
					return false;
			}
		}
	}
		
	return true;
}

//////////////////////////////////////////////////////////////////////////////

bool FindNewSolutionLev2()
{
	int i, j, k;

	num_sols = MAX_SOLS_LEV3;

	sort(all_sols, all_sols+MAX_SOLS_LEV3);
	
	Solution all_sols_copy[MAX_SOLS_LEV3];

	for (i=0; i<num_sols; i++)
	{
		CopySolution(all_sols_copy[i], all_sols[i]);
		all_sols[i].all_cost = MAX_COST;
	}

	change_occurs = false;
	
	for (i=0; i<num_sols; i++)
	{
		if (all_sols_copy[i].all_cost == MAX_COST)	// This element is removed
			continue;

		int num_operations = all_sols_copy[i].indexed_operations.size();
		
		RestoreSolution(all_sols_copy[i]);

		for (j=0; j<num_operations; j++)
		{
			for (k=j+1; k<num_operations; k++)
			{
				if (WeShouldStop())
					return false;

				if (CanSwapTwoOperations(j, k))
				{
					if (SwapTwoOperations(j, k))
						ExecuteAllOperations();
					
					SwapTwoOperations(j, k);
					ResetCurrentSolution();
					last_move = all_sols_copy[i].last_move;
				}
			}
		}

		for (j=0; j<num_operations; j++)
		{
			for (k=0; k<num_operations; k++)
			{
				if (WeShouldStop())
					return false;

				if (k==j || k==j+1 || j==k+1)
					continue;

				if (CanMoveOneOperation(j, k))
				{
					if (MoveOneOperation(j, k))
						ExecuteAllOperations();
					
					indexed_operations = all_sols_copy[i].indexed_operations;
					for (int w=0; w<indexed_operations.size(); w++)
						perform_operations[indexed_operations[w].iline][indexed_operations[w].ioper].index = w;
					ResetCurrentSolution();
					last_move = all_sols_copy[i].last_move;
				}
			}
		}
	}
	
	return change_occurs;
}

//////////////////////////////////////////////////////////////////////////////

void TryInitialSolution()
{
	int i, j;

	for (i=0; i<num_rows; i++)
	{
		perform_operations[i].clear();
	}

	for (i=0; i<num_rows; i++)
	{
		for (j=0; j<GetNumberOfOperationsInCurrentLineSol(i); j++)
		{
			PerformOperation oper;
			GetInfoFromBasicOperations(i, j, oper);

			perform_operations[i].push_back(oper);
		}
	}

	indexed_operations.clear();

	for (i=0; i<num_rows; i++)
	{
		bool last_oper = false;
		PerformOperIndex last_poi;	// This will be inserted as the last operation of the line
		
		for (j=0; j<perform_operations[i].size(); j++)
		{
			if (perform_operations[i][j].wait==WAIT_NEXT)
			{
				last_oper = true;
				last_poi.iline = i;
				last_poi.ioper = j;
			}
			else
			{
				PerformOperIndex poi;
				poi.iline = i;
				poi.ioper = j;

				indexed_operations.push_back(poi);
				int indexing_cur = indexed_operations.size()-1;

				perform_operations[indexed_operations[indexing_cur].iline]
								[indexed_operations[indexing_cur].ioper].index = indexing_cur;
			}
		}

		if (last_oper)
		{
			indexed_operations.push_back(last_poi);
			int indexing_cur = indexed_operations.size()-1;

			perform_operations[indexed_operations[indexing_cur].iline]
							[indexed_operations[indexing_cur].ioper].index = indexing_cur;
		}
	}

	ExecuteAllOperations();
}

//////////////////////////////////////////////////////////////////////////////

void ExecuteLineOperations(int line)
{
	// Start from the start_pos of the line
	// Execute operations in their order (as we did in TryInitialSolution())
	// Save the last position of the cursor and the last line size
	// When combinig line operations, combine the last cursor pos from 
	//	the prev to the first oper start_pos of the next

	int i, j, k;

	for (k=0; k<all_operations[line].size(); k++)
	{
		perform_operations[line].clear();

		vector<Operation>& current_opers = all_operations[line][k].opers;

		for (j=0; j<current_opers.size(); j++)
		{
			PerformOperation oper;

			oper.done = false;

			oper.start_pos_old = oper.start_pos = current_opers[j].start_pos;
			oper.end_pos_old = oper.end_pos = current_opers[j].end_pos;
			oper.shift_old = oper.shift = current_opers[j].shift;
			oper.cost = current_opers[j].cost;
			oper.wait = current_opers[j].wait;
			oper.seq = current_opers[j].seq;

			perform_operations[line].push_back(oper);
		}

		indexed_operations.clear();

		bool last_oper = false;
		PerformOperIndex last_poi;	// This will be inserted as the last operation of the line
		
		for (j=0; j<perform_operations[line].size(); j++)
		{
			if (perform_operations[line][j].cost == 0)
				continue;

			if (perform_operations[line][j].wait==WAIT_NEXT)
			{
				last_oper = true;
				last_poi.iline = line;
				last_poi.ioper = j;
			}
			else
			{
				PerformOperIndex poi;
				poi.iline = line;
				poi.ioper = j;

				indexed_operations.push_back(poi);
				int indexing_cur = indexed_operations.size()-1;

				perform_operations[indexed_operations[indexing_cur].iline]
								[indexed_operations[indexing_cur].ioper].index = indexing_cur;
			}
		}

		if (last_oper)
		{
			indexed_operations.push_back(last_poi);
			int indexing_cur = indexed_operations.size()-1;

			perform_operations[indexed_operations[indexing_cur].iline]
							[indexed_operations[indexing_cur].ioper].index = indexing_cur;
		}

		//// Execute This Line Operations ///////////////////
		
		if (indexed_operations.size()==0)
		{
			all_operations[line][k].cost = 0;
			all_operations[line][k].start_pos = -1;
			all_operations[line][k].end_pos = -1;
		}
		else
		{
			cp.row=line;
			cp.col=perform_operations[indexed_operations[0].iline][indexed_operations[0].ioper].start_pos;
			
			all_operations[line][k].start_pos = cp.col;

			all_cost = 0;
			str_moves = "";

			for (i=0; i<line; i++)
			{
				line_sizes[i]=goal_grid[i].size();
			}

			for (i=line; i<num_rows; i++)
			{
				line_sizes[i]=start_grid[i].size();
			}

			for (i=0; i<indexed_operations.size(); i++)
			{
				ExecuteOperation(indexed_operations[i]);
			}

			all_operations[line][k].cost = all_cost;
			all_operations[line][k].end_pos = cp.col;
		}
	}
	
	sort(all_operations[line].begin(), all_operations[line].end());
	
	while (all_operations[line].size() > MAX_LINE_SOLUTIONS)
		all_operations[line].pop_back();
}

//////////////////////////////////////////////////////////////////////////////

struct LineOperationState
{
	short				line_operations_used[MAX_COL];

	int					cost;
	CursorPos			cp_end;

	bool operator < (const LineOperationState& lo) const
	{
		return (cost < lo.cost);
	}
};

//////////////////////////////////////////////////////////////////////////////

void FindSolutionLev1()
{
	best_sol.all_cost = MAX_COST;
	num_sols = MAX_SOLS_LEV2;

	// For each good solution, Fill line_operations_used[] with the line indexes,
	//	then call TryInitialSolution()

	int i, j, k;
	
	LineOperationState line_opers_states[MAX_LINE_SOLUTIONS];

	int cur_line = 0;
	int num_states = all_operations[cur_line].size();

	for (i=0; i<num_rows; i++)
	{
		line_sizes[i]=start_grid[i].size();
	}

	for (i=0; i<num_states; i++)
	{
		line_opers_states[i].line_operations_used[cur_line] = i;
		line_opers_states[i].cost = all_operations[cur_line][i].cost;

		CursorPos cp_old;
		cp_old.row = 0;
		cp_old.col = 0;

		CursorPos cp_new;
		cp_new.row = cur_line;
		cp_new.col = all_operations[cur_line][i].start_pos;

		string str_go;
		
		if (cp_new.col != -1)
		{
			str_go = GetShortestDistanceBetweenTwoPositions(cp_old, cp_new);
			
			line_opers_states[i].cp_end.row = cur_line;
			line_opers_states[i].cp_end.col = all_operations[cur_line][i].end_pos;
		}
		else
		{
			line_opers_states[i].cp_end = cp_old;
		}

		line_opers_states[i].cost += str_go.size();
	}

	sort(line_opers_states, line_opers_states+num_states);

	// Initialize Finished /////////////////////////

	for (cur_line=1; cur_line<num_rows; cur_line++)
	{
		line_sizes[cur_line-1]=goal_grid[cur_line-1].size();

		LineOperationState line_opers_states_new[MAX_LINE_SOLUTIONS*MAX_LINE_SOLUTIONS];
		int line_states_size = 0;
		
		for (i=0; i<num_states; i++)		// Loop over line_opers_states[]
		{
			for (j=0; j<all_operations[cur_line].size(); j++)	// Loop over all_operations[cur_line]
			{
				for (k=0; k<cur_line; k++)
				{
					line_opers_states_new[line_states_size].line_operations_used[k] =
						line_opers_states[i].line_operations_used[k];
				}

				line_opers_states_new[line_states_size].line_operations_used[cur_line] = j;

				line_opers_states_new[line_states_size].cost = 
							line_opers_states[i].cost + all_operations[cur_line][j].cost;

				CursorPos cp_old = line_opers_states[i].cp_end;

				CursorPos cp_new;
				cp_new.row = cur_line;
				cp_new.col = all_operations[cur_line][j].start_pos;

				string str_go;

				if (cp_new.col != -1)
				{
					str_go = GetShortestDistanceBetweenTwoPositions(cp_old, cp_new);

					line_opers_states_new[line_states_size].cp_end.col = 
														all_operations[cur_line][j].end_pos;
					line_opers_states_new[line_states_size].cp_end.row = cur_line;
				}
				else
				{
					line_opers_states_new[line_states_size].cp_end = cp_old;
				}

				// Need some corrections in end_pos, but not important
				
				line_opers_states_new[line_states_size].cost += str_go.size();

				line_states_size++;
			}
		}

		// Sort and save ////////////////////
		
		sort(line_opers_states_new, line_opers_states_new+line_states_size);

		num_states = line_states_size;

		if (num_states > MAX_LINE_SOLUTIONS)
		{
			num_states = MAX_LINE_SOLUTIONS;
		}

		for (i=0; i<num_states; i++)
		{
			line_opers_states[i] = line_opers_states_new[i];
			line_opers_states[i].cost = line_opers_states_new[i].cost;
		}
	}
	
	// Now, call TryInitialSolution() for the first num_sols solutions /////

	//for (i=0; i<num_sols; i++)
	
	for (i=0; i<num_states; i++)
	{
		for (j=0; j<num_rows; j++)
		{
			line_operations_used[j] = line_opers_states[i].line_operations_used[j];
		}

		TryInitialSolution();

		if (change_occurs && on_my_machine)
		{
			cout << "My cost = " << line_opers_states[i].cost;
			cout << " -- Actual cost = " << all_cost << endl;
		}

		bool remain_sols = false;

		for (j=0; j<num_sols; j++)
		{
			if (all_sols[j].all_cost==MAX_COST)
			{
				remain_sols = true;
				break;
			}
		}

		if (!remain_sols)
			break;
	}

	if (on_my_machine)
	{
		cout << "\n\nInitial Solutions:" << endl;

		for (j=0; j<num_sols; j++)
		{
			cout << "Actual cost = " << all_sols[j].all_cost << endl;
			cout << "Actual moves = " << all_sols[j].str_moves << endl << endl;
		}

		cout << "\n\n";
	}
}

//////////////////////////////////////////////////////////////////////////////

void MakeRandomSwap()
{
	int num_opers = indexed_operations.size();

	for (int i=0; i<20; i++)
	{
		short index1 = rand()%num_opers;
		short index2 = rand()%num_opers;

		if (index1<index2 && CanSwapTwoOperations(index1, index2))
		{
			if (SwapTwoOperations(index1, index2))
				break;

			SwapTwoOperations(index1, index2);
			ResetCurrentSolution();
		}
	}
}

//////////////////////////////////////////////////////////////////////////////

void MakeRandomMove()
{
	int num_opers = indexed_operations.size();

	vector<PerformOperIndex> indexed_operations_saved = indexed_operations;

	for (int i=0; i<20; i++)
	{
		short index1 = rand()%num_opers;
		short index2 = rand()%num_opers;

		if (abs(index1-index2)>1 && CanMoveOneOperation(index1, index2))
		{
			if (MoveOneOperation(index1, index2))
				break;
			
			indexed_operations = indexed_operations_saved;
			for (int w=0; w<indexed_operations.size(); w++)
				perform_operations[indexed_operations[w].iline][indexed_operations[w].ioper].index = w;
			ResetCurrentSolution();
		}
	}
}

//////////////////////////////////////////////////////////////////////////////

void SplitSolution(Solution& sol)
{
	int i, j;

	for (i=0; i<num_rows; i++)
	{
		for (j=0; j<sol.perform_operations[i].size(); j++)
		{
			sol.perform_operations[i][j].end_pos = 
				sol.perform_operations[i][j].end_pos_old;

			sol.perform_operations[i][j].start_pos = 
				sol.perform_operations[i][j].start_pos_old;

			sol.perform_operations[i][j].shift = 
				sol.perform_operations[i][j].shift_old;
		}
	}

	// Split Insert //////////////////////////////////////////

	for (i=0; i<num_rows; i++)
	{
		SplitLineOperations(sol.perform_operations[i]);
	}

	sol.indexed_operations.clear();

	for (i=0; i<num_rows; i++)
	{
		bool last_oper = false;
		PerformOperIndex last_poi;	// This will be inserted as the last operation of the line
		
		for (j=0; j<sol.perform_operations[i].size(); j++)
		{
			if (sol.perform_operations[i][j].wait==WAIT_NEXT)
			{
				last_oper = true;
				last_poi.iline = i;
				last_poi.ioper = j;
			}
			else
			{
				PerformOperIndex poi;
				poi.iline = i;
				poi.ioper = j;

				sol.indexed_operations.push_back(poi);
				int indexing_cur = sol.indexed_operations.size()-1;

				sol.perform_operations[sol.indexed_operations[indexing_cur].iline]
								[sol.indexed_operations[indexing_cur].ioper].index = indexing_cur;
			}
		}

		if (last_oper)
		{
			sol.indexed_operations.push_back(last_poi);
			int indexing_cur = sol.indexed_operations.size()-1;

			sol.perform_operations[sol.indexed_operations[indexing_cur].iline]
							[sol.indexed_operations[indexing_cur].ioper].index = indexing_cur;
		}
	}
}

//////////////////////////////////////////////////////////////////////////////

void Compute()
{
	memset(hash_table, 0, sizeof(hash_table));
	enable_hash = true;

	srand(2);
	
	int i;

	for (i=0; i<MAX_SOLS_LEV2; i++)
	{
		all_sols[i].all_cost = MAX_COST;	// Remove all nodes
	}

	for (i=0; i<num_rows; i++)
	{
		ComputeLineOperations(i);
		
		CombineLineOperationsAll(i);
		ExecuteLineOperations(i);
	}

	//////////////////////////////////////////////////////////////////
	// Execute Operations

	FindSolutionLev1();

	//////////////////////////////////////////////////////////////////

	if (on_my_machine)
	{
		cout << "After Level 1: " << (clock()/CLOCKS_PER_SEC) << " secs" << endl;
		cout << "cost = " << best_sol.all_cost << endl << endl;
		cout << "Start Level 2:" << endl;
	}

	sort(all_sols, all_sols + MAX_SOLS_LEV2);

	///////////////////////////////////////////////////////////////////
	// Get Some memory

	num_sols = MAX_SOLS_LEV3;

	for (i=num_sols; i<MAX_SOLS_LEV2; i++)
	{
		all_sols[i].indexed_operations.clear();
		all_sols[i].str_moves = "";
		all_sols[i].all_cost = MAX_COST;
	}

	for (i=0; i<num_rows; i++)
	{
		all_operations[i].clear();
	}

	///////////////////////////////////////////////////////////////////

	for (i=0; i<num_sols; i++)
	{
		all_sols[i].last_move.type = NO_MOVE;
	}
	
	///////////////////////////////////////////////////////////////////

	Solution	all_sols_splitted[MAX_SOLS_LEV3];
	
	for (i=0; i<MAX_SOLS_LEV3; i++)
	{
		CopySolution(all_sols_splitted[i], all_sols[i]);
		SplitSolution(all_sols_splitted[i]);
	}

	///////////////////////////////////////////////////////////////////

	int iteration = 0;
	int no_change = 0;
	int last_best_cost = best_sol.all_cost;
	
	int adjust_events = 0;
	bool splitted = false;
	
	enable_hash = true;

	while(!WeShouldStop())
	{
		iteration++;

		if (!FindNewSolutionLev2())
		{
			if (WeShouldStop())
			{
				break;
			}
			else
			{
				no_change = NO_CHANGE_LIMIT;
				last_best_cost = best_sol.all_cost;
			}
		}

		if (best_sol.all_cost < last_best_cost)
		{
			last_best_cost = best_sol.all_cost;
			no_change = 0;
			adjust_events = 0;
		}
		else
		{
			no_change++;

			if (no_change >= NO_CHANGE_LIMIT)
			{
				no_change = 0;

				adjust_events++;

				if (adjust_events >= ADJUST_EVENT_LIMIT && !splitted && WeCanSplit())
				{
					splitted = true;

					memset(hash_table, 0, sizeof(hash_table));

					for (i=0; i<MAX_SOLS_LEV3; i++)
					{
						CopySolution(all_sols[i], all_sols_splitted[i]);
						all_sols[i].last_move.type = NO_MOVE;
					}
					CopySolution(restore_sol, all_sols[0]);

					if (on_my_machine)
					{
						cout << "Splitted!--------------------\n";
					}
				}
				else
				{
					for (i=0; i<num_sols; i++)
					{
						all_sols[i].all_cost = MAX_COST;
					}

					RestoreSolution(restore_sol);
					
					for (i=0; i<NUM_RANDOM_CHANGES; i++)
					{
						MakeRandomSwap();
						MakeRandomMove();
					}

					last_move.type = NO_MOVE;
					ResetCurrentSolution();
					ExecuteAllOperations();
					
					if (on_my_machine)
					{
						cout << "Adjusted cost = " << all_cost << " " << (clock()/CLOCKS_PER_SEC) << " secs" << endl;
					}
				}
			}
		}

		if (on_my_machine)
		{
			cout << "cost = " << best_sol.all_cost << " " << (clock()/CLOCKS_PER_SEC) << " secs" << endl;
		}
	}
	
	///////////////////////////////////////////////////////////////////

	if (on_my_machine)
	{
		cout << "cost = " << best_sol.all_cost << " " << (clock()/(double)CLOCKS_PER_SEC) << " secs" << endl << endl;
	}

	///////////////////////////////////////////////////////////////////

	cout << best_sol.str_moves << endl;
}

//////////////////////////////////////////////////////////////////////////////

int main(int argc, char* argv[])
{
	if (argc<2)	// The program is running on my machine
	{
		on_my_machine = true;

		//	m7 = m6 = Better Initial Solution + No Middle Faliure
		//	m8 = m7 + Fix two small bugs
													// 			m7
		//freopen("Tests/key1.in", "r", stdin);		// (201)	202*
		//freopen("Tests/key2.in", "r", stdin);		// (253)	253
		//freopen("Tests/key3.in", "r", stdin);		// (290)	291*
		//freopen("Tests/key4.in", "r", stdin);		// (284)	284
		//freopen("Tests/key5.in", "r", stdin);		// (356)	356
		//freopen("Tests/key6.in", "r", stdin);		// (374)	374
		//freopen("Tests/key7.in", "r", stdin);		// (246)	246
		//freopen("Tests/key8.in", "r", stdin);		// (388)	388
		//freopen("Tests/key9.in", "r", stdin);		// (383)	383
		//freopen("Tests/key10.in", "r", stdin);	// (327)	327
		//freopen("Tests/key11.in", "r", stdin);	// (419)	419
		//freopen("Tests/key12.in", "r", stdin);	// (221)	221
		freopen("Tests/key13.in", "r", stdin);	// (310)	312*
		//freopen("Tests/key14.in", "r", stdin);	// (277)	277
		//freopen("Tests/key15.in", "r", stdin);	// (321)	321
		//freopen("Tests/key16.in", "r", stdin);	// (349)	249
		//freopen("Tests/key17.in", "r", stdin);	// (317)	317
		//freopen("Tests/key18.in", "r", stdin);	// (271)	271
		//freopen("Tests/key19.in", "r", stdin);	// (459)	459
		//freopen("Tests/key20.in", "r", stdin);	// (309)	309
		//freopen("Tests/key21.in", "r", stdin);	// (289)	289
		//freopen("Tests/key22.in", "r", stdin);	// (276)	276
		//freopen("Tests/key23.in", "r", stdin);	// (366)	366

		//freopen("Tests/keyA.in", "r", stdin);		// (57)		57
		//freopen("Tests/keyB.in", "r", stdin);		// (49)		49
		//freopen("Tests/keyC.in", "r", stdin);		// (107)	108*
		//freopen("Tests/keyD.in", "r", stdin);		// (146)	146
		//freopen("Tests/keyE.in", "r", stdin);		// (218)	218

		//freopen("key.in", "r", stdin);

		freopen("key.out", "w", stdout);
	}
	else
	{
		on_my_machine = false;
		freopen(argv[1], "r", stdin);
	}

	int i;
	
	i = 0;
	
	while(true)
	{
		getline(cin, start_grid[i]);
		
		if (start_grid[i]=="" || !myisupper(start_grid[i][0]) || (i==5))
			break;

		i++;
	}

	num_rows = i;

	for (i=0; i<num_rows; i++)
	{
		getline(cin, goal_grid[i]);
	}

	//////////////////////////////////////////////////////////////////

	Compute();

	//////////////////////////////////////////////////////////////////

	if (on_my_machine)	// The program is running at my machine
	{
		if (TestOutput(best_sol.str_moves))
		{
			cout << "\nTestOutput Succeeded.\n";
			cout << endl;
		}
		else
		{
			cout << "\nTestOutput Failed FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF.\n\n";

			cout << "goal:\n";
			for (i=0; i<num_rows; i++)
				cout << goal_grid[i] << endl;

			cout << "result:\n";
			for (i=0; i<num_rows; i++)
				cout << test_grid[i] << endl;
	
			cout << endl;
		}
	}

	return 0;
}

//////////////////////////////////////////////////////////////////////////////
	// If we have a matching between the first char and a char in the goal
	//	other than the first, and first==0, we can not make benefit of this matching