#include<bits/stdc++.h>
#include"word.h"
using namespace std;

namespace Wallbreaker5th{

const int N=9000;
string s[N];int occ[N];
int n;
map<int,int>ch[26][N];int gue[26][N];int cnt[26];
mt19937 mt;
double gini(const vector<int>&v){
	double sum=0;for(int i:v)sum+=i;
//	double res=1;
//	for(int i:v)res-=pow(i/sum,2);
	double res=v.size()*0.2;
	for(int i:v)if(i)res-=log(i/sum)*(i/sum)*2;
	return res;
//	return v.size()+mt()%100000/100000.;
//	return -*max_element(v.begin(),v.end());
}
int res(int x,int ans){
	int r=0;
	for(int i=0;i<5;i++)r|=(s[x][i]==s[ans][i])<<i;
	for(int i=0;i<5;i++){
//		r|=(s[x][i]!=s[ans][i]&&((occ[ans]>>(s[x][i]-'a'))&1))<<(i+5);
		if((r>>i)&1)continue;
		for(int j=0;j<5;j++)if(!((r>>j)&1)&&s[x][i]==s[ans][j])r|=1<<(i+5);
	}
	return r;
}
double pred_score=0;
int sco[]={-1,150,120,100,90,85};
int qaq=0;
void build(int x,vector<int>w,int fi,int dep){
//	cerr<<"> "<<char('A'+fi)<<"  "<<x<<" "<<dep<<" "<<w.size()<<endl;
	if(w.size()==1||dep==5){
//		ch[fi][x][-1]=w[0];
		gue[fi][x]=w[mt()%w.size()];
		pred_score+=sco[dep];
		++qaq;
		if(w.size()>1)cerr<<"> "<<w.size()<<endl;
		return;
	}
	vector<pair<double,int>>cho;
	for(int i=0;i<n;i++){
		map<int,double>o;
		for(int j:w)o[res(i,j)]++;
		double g=0;
		if(o[31]){
			o[31]=0;
			int sum=0;for(auto i:o)sum+=i.second;
			o[31]=sum/(o.size()-1.);
			g++;
		}
		vector<int>v;for(auto i:o)v.push_back(i.second);
//		double g=gini(v);
		g+=gini(v);
//		g+=log(o.size());
		cho.push_back({g,i});
	}
	sort(cho.begin(),cho.end(),greater<pair<double,int>>());
//	int mxi=mt()%10<dep+5?cho[0].second:cho[1].second;
	int mxi=cho[0].second;

	gue[fi][x]=mxi;
	map<int,vector<int>>o;
	for(int j:w)o[res(mxi,j)].push_back(j);
	for(auto &i:o){
		if(i.first==31){
			pred_score+=sco[dep];
			++qaq;
			continue;
		}
		ch[fi][x][i.first]=++cnt[fi];
		build(cnt[fi],i.second,fi,dep+1);
	}
}
void init(int num_scramble, const char *scramble){
	n=num_scramble;
	for(int i=0;i<n;i++)for(int j=0;j<5;j++)s[i]+=scramble[i*5+j];
	for(int i=0;i<n;i++)for(int j=0;j<5;j++)occ[i]|=1<<(s[i][j]-'a');
	vector<int>w[26];
	for(int i=0;i<n;i++)w[s[i][0]-'a'].push_back(i);
	for(int i=0;i<26;i++)cerr<<"> "<<char(i+'a')<<endl,build(0,w[i],i,1);
	cerr<<"> "<<pred_score/n<<endl;
//	ofstream fout("tree.txt"); 
//	fout<<"> "<<qaq<<"/"<<accumulate(cnt,cnt+26,0)<<endl<<endl;
//	for(int i=0;i<26;i++){
//		fout<<cnt[i]<<endl;
//		for(int j=0;j<=cnt[i];j++){
//			fout<<gue[i][j]<<" "<<s[gue[i][j]]<<"  ";
//			fout<<ch[i][j].size()<<" ";
//			for(auto k:ch[i][j])fout<<k.first<<" "<<k.second;fout<<endl;
//		}
//	}
}

int cur=0;
const char *guess(int num_testcase, int remaining_guesses, char 
	initial_letter, bool *gold, bool *silver){
	if(remaining_guesses==5)cur=0;
	else{
		int v=0;
		for(int i=0;i<5;i++)v|=gold[i]<<i;
		for(int i=0;i<5;i++)v|=silver[i]<<(i+5);
//		if(!ch[initial_letter-'a'][cur].count(v))
//			cerr<<"! "<<cur<<" "<<remaining_guesses<<" "<<ch[initial_letter-'a'][cur].size()<<endl;
		cur=ch[initial_letter-'a'][cur][v];
	}
	return s[gue[initial_letter-'a'][cur]].c_str();
}

}

void init(int num_scramble, const char *scramble){
	Wallbreaker5th::init(num_scramble,scramble);
}
const char *guess(int num_testcase, int remaining_guesses, char 
	initial_letter, bool *gold, bool *silver){
	return Wallbreaker5th::guess(num_testcase, remaining_guesses, initial_letter, 
		gold, silver);
}