#include <iostream>
#include <algorithm>
#include <string>
#include <climits>
#include <cctype>
#include <sys/time.h>
#include "common.h"

using namespace std;

const int MMDEPTH=2;

int takeperc=0;

void search(int *best,Board &bd,int me,int win,int depth=MMDEPTH){
	int i;
	if(win!=-1||depth<=0){
		for(i=0;i<NPLAYERS;i++)best[i]=bd.ballcount(i)+rand()%2;
		if(win!=-1)best[win]=best[win]*11/10; //*=1.1
		return;
	}
	int res[NPLAYERS];
	for(i=0;i<WID*HEI;i++){
		Board bd2(bd);
		if(!bd2.put(i,me))continue;
		memset(res,0,NPLAYERS*sizeof(int));
		search(res,bd2,(me+1)%NPLAYERS,bd2.checkwin(),depth-1);
		if(res[me]>best[me]){
			memcpy(best,res,NPLAYERS*sizeof(int));
		}
	}
}

Move calcmove(Board &bd,int me){
	int i;
	int res[NPLAYERS];
	struct Item{
		int i,score;
	};
	Item scores[WID*HEI];
	int nposs=0;
	for(i=0;i<WID*HEI;i++){
		Board bd2=bd;
		scores[i].score=INT_MIN;
		if(!bd2.put(i,me))continue;
		memset(res,0,NPLAYERS*sizeof(int));
		search(res,bd2,(me+1)%NPLAYERS,bd2.checkwin());
		scores[i].i=i;
		scores[i].score=res[me];
		nposs++;
	}
	sort(scores,scores+WID*HEI,[](const Item &a,const Item &b){return a.score>b.score;}); //descending sort
	return Move(scores[(nposs-1)*takeperc/100].i);
}

int main(int argc,char **argv){
	struct timeval tv;
	gettimeofday(&tv,NULL);
	srand(tv.tv_sec*1000000+tv.tv_usec);
	{
		const int len=strlen(argv[0]);
		const char *p=argv[0]+len-1;
		while(isdigit(*p))p--;
		p++;
		if(*p!='\0'){
			takeperc=strtol(p,NULL,10);
		} else {
			if(argc==2)takeperc=strtol(argv[1],NULL,10);
			else takeperc=0;
		}
		takeperc=min(100,max(0,takeperc));
		cerr<<"Using takeperc "<<takeperc<<endl;
	}

	Board bd;
	char c;
	Move mv;
	cin>>c; cin.ignore(1024,'\n');
	int me=c-'A';
	int x,y,i;
	while(true){
		c=cin.peek();
		if(c=='q'||c=='Q')break;
		for(i=me+1;i%NPLAYERS!=me;i++){
			cin>>x>>y;
			if(x!=-1&&y!=-1)bd.put(x,y,i%NPLAYERS);
		}
		cin.ignore(1024,'\n');
		mv=calcmove(bd,me);
		cout<<mv.x<<' '<<mv.y<<endl;
		bd.put(mv.idx(),me);
	}
}