#include <iostream>
#include <iomanip>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cassert>

using namespace std;

const int NPLAYERS=2;
const int WID=8,HEI=9;


template <typename T>
ostream& operator<<(ostream &os,const vector<T> &v){
	const int sz=v.size();
	if(sz==0)return os;
	os<<v[0];
	for(int i=1;i<sz;i++)os<<' '<<v[i];
	return os;
}


struct Move{
	int x,y;

	Move(void):x(-1),y(-1){}
	Move(int idx):x(idx%WID),y(idx/WID){}
	Move(int _x,int _y):x(_x),y(_y){}

	int idx(void){return WID*y+x;}
};

class Board{
	int balls[WID*HEI],colour[WID*HEI];
	int wonby=-1; //kept up-to-date by stabilise()
	int nballs=0;

public:
	inline Board(void){
		memset(balls,0,WID*HEI*sizeof(int));
		memset(colour,0,WID*HEI*sizeof(int));
	}
	inline Board(const Board &other):wonby(other.wonby){
		memcpy(balls,other.balls,WID*HEI*sizeof(int));
		memcpy(colour,other.colour,WID*HEI*sizeof(int));
	}

	inline int getballs(int idx){return balls[idx];}
	inline int getballs(int x,int y){return getballs(WID*y+x);}
	inline int getcolour(int idx){return colour[idx];}
	inline int getcolour(int x,int y){return getcolour(WID*y+x);}

	inline bool put(int x,int y,int c){
		const int idx=WID*y+x;
		if(balls[idx]&&colour[idx]!=c)return false;
		balls[idx]++;
		colour[idx]=c;
		nballs++;
		stabilise();
		return true;
	}
	inline bool put(int idx,int c){return put(idx%WID,idx/WID,c);}

	inline bool putq(int idx,int c) const{return !balls[idx]||colour[idx]==c;}
	inline bool putq(int x,int y,int c) const{return putq(WID*y+x,c);}

	inline void stabilise(void){
		int nballs[WID*HEI],ncolour[WID*HEI]; //new values
		bool changed;
		int x,y;
		do {
			changed=false;
			memcpy(nballs,balls,WID*HEI*sizeof(int));
			memcpy(ncolour,colour,WID*HEI*sizeof(int));

			for(y=0;y<HEI;y++)for(x=0;x<WID;x++){
				const int idx=WID*y+x;
				const int nnei=(y>0)+(x>0)+(y<HEI-1)+(x<WID-1);
				if(balls[idx]>=nnei){
					const int quo=balls[idx]/nnei;
					nballs[idx]-=nnei*quo;
					if(y>0){nballs[idx-WID]+=quo;ncolour[idx-WID]=colour[idx];}
					if(x>0){nballs[idx-1]+=quo;ncolour[idx-1]=colour[idx];}
					if(y<HEI-1){nballs[idx+WID]+=quo;ncolour[idx+WID]=colour[idx];}
					if(x<WID-1){nballs[idx+1]+=quo;ncolour[idx+1]=colour[idx];}
					changed=true;
				}
			}
			wonby=-1;
			for(int i=0;i<WID*HEI;i++){
				if(nballs[i]==0)continue;
				if(wonby==-1)wonby=ncolour[i];
				else if(wonby!=ncolour[i]){
					wonby=-1;
					break;
				}
			}

			memcpy(balls,nballs,WID*HEI*sizeof(int));
			memcpy(colour,ncolour,WID*HEI*sizeof(int));
		} while(changed&&wonby==-1);
	}

	//returns -1 for no win yet, >=0 for that colour
	inline int checkwin(void) const{return wonby;}

	inline int ballcount(int c) const{
		int i,count=0;
		for(i=0;i<WID*HEI;i++){
			count+=balls[i]*(colour[i]==c);
		}
		return count;
	}

	inline int totalballcount(void) const{return nballs;}

	void print(ostream &os){
		int x,y;
		for(y=0;y<HEI;y++){
			for(x=0;x<WID;x++){
				if(balls[WID*y+x]){
					os<<"\x1B[3"<<colour[WID*y+x]+1<<'m'<<setw(2)<<balls[WID*y+x]<<"\x1B[0m ";
				} else os<<".. ";
			}
			os<<endl;
		}
	}
};

Move randommove(const Board &bd,int c){
	Move poss[WID*HEI];
	int nposs=0;
	int i;
	for(i=0;i<WID*HEI;i++){
		if(bd.putq(i,c)){
			poss[nposs].x=i%WID;
			poss[nposs].y=i/WID;
			nposs++;
		}
	}
	if(nposs==0)return Move();
	return poss[rand()%nposs];
}