/*------------------------------------------------------------
TEAM07
A
236
Target: MSVC9; Platform: Win32; Comment: MS Visual C++ 9
------------------------------------------------------------*/
// Random bot for "Breakthrough" game
// Ural Championship 2010 Game Tour
// Author: Igor Chevdar

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <queue>
#include <algorithm>

using namespace std;

#define BOARD_SIZE 8
#define MAX_MOVES (BOARD_SIZE*2*3)

#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

int n;


enum {EMPTY,WHITE,BLACK};

struct game_move {
	int sx,sy;
	int ex,ey;
	int is_capture;
};

inline int op_color(int color) {
	return color==WHITE ? BLACK : WHITE;
}

char board[BOARD_SIZE][BOARD_SIZE];
int color;

void init() {
	memset(board,EMPTY,sizeof(board));
	for(int i=0;i<BOARD_SIZE;++i) {
		board[0][i]=board[1][i]=WHITE;
		board[BOARD_SIZE-1][i]=board[BOARD_SIZE-2][i]=BLACK;
	}
	color=WHITE;
}

void make_move(game_move &move) {
	board[move.ex][move.ey]=board[move.sx][move.sy];
	board[move.sx][move.sy]=EMPTY;
	color=op_color(color);
}

void make_move(char *str) {
	char sy,ey;
	int sx,ex;
	sscanf(str,"%c%d%c%d",&sy,&sx,&ey,&ex);
	game_move move={sx-1,sy-'a',ex-1,ey-'a',board[ex-1][ey-'a']!=EMPTY};
	make_move(move);
}

const int white = 0 //empty
, gray = 1 //our
, black = 2,
op = 3;

int ourC = 7;

int ccolor[BOARD_SIZE][BOARD_SIZE];
const int inf = 0x0fffffff;

const int Dc[3] = {-1, 0, 1};
int d[BOARD_SIZE][BOARD_SIZE];
int p[BOARD_SIZE][BOARD_SIZE];
int f[BOARD_SIZE][BOARD_SIZE];

struct Point
{
	int r, c;
	Point(int r = 0, int c = 0) : r(r), c(c) {}
};

vector<vector<Point> > pl;;
bool operator==(const Point &a, const Point &b)
{
	return a.r == b.r && a.c == b.c;
}

void BFS(int r, int c, int color)
{
	int td = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
		{
			d[i][j] = inf;
			p[i][j] = inf;
			if(board[i][j] == color)
				ccolor[i][j] = gray;
			if(board[i][j] == EMPTY)
				ccolor[i][j] = white;
			f[i][j] = 0;
			if(board[i][j] == op_color(color))
			{
				ccolor[i][j] = op;
				f[i][j] = 1;
			}
		}
	queue<Point> q;
	d[r][c] = 0;
	p[r][c] = 0;
	q.push(Point(r, c));
	ccolor[r][c] = black;
	while(q.size())
	{
		Point u = q.front();
		q.pop();
		for(int i = 0; i < 3; i++)
		{
			Point v = Point(u.r + (color==WHITE ? 1 : -1), u.c + Dc[i]);
			if(v.r >= 0 && v.r < n && v.c >= 0 && v.c < n)
			{
				if(ccolor[v.r][v.c] != gray)
				{
					if(ccolor[v.r][v.c] != black)
						q.push(v);
					if(ccolor[v.r][v.c] == white)
						ccolor[v.r][v.c] = black;
					d[v.r][v.c] = d[u.r][u.c] + 1;
					p[v.r][v.c] = min(p[v.r][v.c], max(p[u.r][u.c], f[v.r][v.c]));
				}
			}
		}
		if(td < d[u.r][u.c])
		{
			td = d[u.r][u.c];
			vector<pair<Point, int > > v;
			for(int i = 0; i < n; i++)
				for(int j = 0; j < n; j++)
				{
					if(ccolor[i][j] >= op)
					{
						v.pb(mp(Point(i, j), f[i][j]));
					}
				}
			for(int i = 0; i < v.size(); i++)
			{
				Point u = v[i].first;
				int cost = v[i].second;
				for(int k = 0; k < 3; k++)
				{
					Point v = Point(u.r + (color==WHITE ? -1 : +1), u.c + Dc[k]);
					if(v.r >= 0 && v.r < n && v.c >= 0 && v.c < n)
					{
						if(ccolor[v.r][v.c] != gray)
							f[v.r][v.c] += cost;
					}
				}
			}
		}
	}
}



bool operator<(const Point &a, const Point &b)
{
	if(a.r == b.r)
		return a.c < b.c;
	return a.r < b.r;
}

bool comp(const Point &a, const Point &b)
{
	return !(a < b);
}



game_move ms[MAX_MOVES];
game_move msw[MAX_MOVES];

void gen_moves(game_move &res) 
{
	
	for(int i = 0; i < 4; i++)
	{
		vector<Point> have;
		for(int j = 0; j < 4; j++)
		{
			Point u = pl[i][j];
			if(board[u.r][u.c] == color)
			{
				have.pb(u);
			}
		}
		if(have.size())
			break;
	}

	for(int i = 3; i >= 0; i--)
	{
		for(int j = 0; j < 4; j++)
		{
			Point u = pl[i][j];
			if(board[u.r][u.c] != color)
				continue;
			for(int k = 0; k < 3; k++)
			{
				Point v = Point(u.r + (color==WHITE ? 1 : -1), u.c + Dc[k]);
				if(v.r >= 0 && v.c >= 0 && v.r < n && v.c < n)
				{
					if(board[v.r][v.c] == op_color(color))
					{
						pl[i][j] = v;
						game_move move = {u.r, u.c, v.r, v.c, 1};
						res = move;
						return;
					}
				}
			}
		}
	}

	for(int i = 0; i < 4; i++)
	{
		vector<Point> m;
		for(int j = 0; j < 4; j++)
		{
			Point u = pl[i][j];
			if(board[u.r][u.c] != color)
				continue;
			for(int k = 0; k < 3; k++)
			{
				Point v = Point(u.r + (color==WHITE ? 1 : -1), u.c + Dc[k]);
				if(v.r >= 0 && v.c >= 0 && v.r < n && v.c < n)
				{
					m.pb(u);
					break;
				}
			}
		}
		sort(all(m));
			if(color == WHITE)
		reverse(all(m));
	
		for(int k = 0; k < m.size(); k++)
		{
			Point u = m[k];
			Point v = Point(u.r + (color==WHITE ? 1 : -1), u.c);
			if(v.r >= 0 && v.c >= 0 && v.r < n && v.c < n)
			{
				if(board[v.r][v.c] == EMPTY)
				{
					for(int r = 0; r < 4; r ++)
						for(int c = 0; c < 4; c++)
						{
							if(pl[r][c] == u)
							{
								pl[r][c] = v;
								game_move move = {u.r, u.c, v.r, v.c, 0};
								res = move;
								return;
							}
						}
					throw "exc";
				}
			}
		}
		for(int k = 0; k < m.size(); k++)
		{
			Point u = m[k];
			for(int l = 0; l < 3; l++)
			{
				Point v = Point(u.r + (color==WHITE ? 1 : -1), u.c + Dc[l]);
				if(v.r >= 0 && v.c >= 0 && v.r < n && v.c < n)
				{
					if(board[v.r][v.c] == EMPTY)
					{
						for(int r = 0; r < 4; r ++)
							for(int c = 0; c < 4; c++)
							{
								if(pl[r][c] == u)
								{
									pl[r][c] = v;
						game_move move = {u.r, u.c, v.r, v.c, 0};
						res = move;
									return;
								}
							}
							throw "exc";
					}
				}
			}
		}
	}
/*	int cnt = 0;
	int cntw = 0;
	for(int i=0;i<BOARD_SIZE;++i) {
		for(int j=0;j<BOARD_SIZE;++j) {
			if(board[i][j]==color) {
				for(int dj=-1;dj<=1;++dj) {
					int ni=i+(color==WHITE ? 1 : -1);
					int nj=j+dj;
					if(ni>=0 && ni<BOARD_SIZE && nj>=0 && nj<BOARD_SIZE)
					{
						if(board[ni][nj]!=color && (dj || board[ni][nj]==EMPTY))
						{
							game_move move={i,j,ni,nj,board[ni][nj]!=EMPTY};
							if(board[ni][nj] == op_color(color))
							{
								msw[cntw++] =move;
							}
						}
					}
				}
			}
		}
	}
	if(cntw)
		res = msw[rand()%cntw];
	else
		res =  ms[rand()%cnt];
		*/

}

void think(char *str) {

	game_move move;
	gen_moves(move);
	sprintf(str,"%c%d%c%d",move.sy+'a',move.sx+1,move.ey+'a',move.ex+1);
	make_move(move);
}

int main() {
	n = 8;

	srand(time(0));
	init();
	pl.resize(4, vector<Point> (4));
	for(int i = 0; i < 4; i++)
		pl[0][i] = Point(6, i * 2);
	for(int i =0; i < 4; i++)
		pl[1][i] = Point(6, i * 2 + 1);
	for(int i = 0; i < 4; i++)
		pl[2][i] = Point(7, i * 2+1);
	for(int i =0; i < 4; i++)
		pl[3][i] = Point(7, i * 2);


	for(;;) {
		char str[100];
		gets(str);
		if(!strcmp(str,"Name")) {
			// Request for the bot name
			printf("MAGTU1s\n");
			fflush(stdout);
		}
		else if(!strcmp(str,"Quit")) {
			// Game is over
			break;
		}
		else {
		


			if(strcmp(str,"Start") != 0) {
				// Enemy's move
				make_move(str);
			}
			else
			{
				for(int i = 0; i < 4; i++)
					pl[0][i] = Point(1, i * 2);
				for(int i =0; i < 4; i++)
					pl[1][i] = Point(1, i * 2 + 1);
				for(int i = 0; i < 4; i++)
					pl[2][i] = Point(0, i * 2+1);
				for(int i =0; i < 4; i++)
					pl[3][i] = Point(0, i * 2);

				ourC = 0;
			}
			// Our move
			think(str);
			printf("%s\n",str);
			fflush(stdout);
		}
	}
	return 0;
}
