#include <bits/stdc++.h>
using namespace std;
int query(string str);
void solve_positions(char c,string &res,int l,int r,int pl,int pr,vector<int> &resvec){
int len=(l+r)/2;
int lo=pl,hi=pr;
string qs;
while(lo<hi){
qs.clear();
int mid=(lo+hi)/2+1;
for(int i=0;i<mid;i++)
qs.push_back(res[i]);
for(int i=0;i<len;i++)
qs.push_back(c);
int smqres=query(qs);
if(smqres==(int)qs.size())
lo=mid;
else
hi=mid-1;
}
resvec.push_back(lo);
if(len-1>=l)
solve_positions(c,res,l,len-1,lo,pr,resvec);
if(len+1<=r)
solve_positions(c,res,len+1,r,pl,lo,resvec);
}
string guess(int n,int s){
string res;
string qs;
vector<int> cnts(s);
for(int cc=0;cc<s;cc++){
char c=(char)('a'+cc);
qs.clear();
for(int i=0;i<n;i++)
qs.push_back(c);
int qres=query(qs);
cnts[cc]=qres;
}
vector<pair<int,int>> srt;
for(int i=0;i<s;i++)
srt.push_back(make_pair(cnts[i],i));
sort(begin(srt),end(srt),greater<pair<int,int>>());
for(int cc=0;cc<s;cc++){
char c=(char)('a'+srt[cc].second);
int maxcount=srt[cc].first;
qs.clear();
if(res.size()==0){
int qres=maxcount;
for(int i=0;i<qres;i++)
res.push_back(c);
}
else
if((int)res.size()<n){
int qres=maxcount;
if(qres==0)
continue;
vector<int> pos;
solve_positions(c,res,1,qres,0,res.size(),pos);
sort(begin(pos),end(pos));
string new_res;
for(int i=res.size();i>=0;i--){
while(pos.size()>0&&pos.back()>=i)
new_res.push_back(c),pos.pop_back();
if(i!=0)
new_res.push_back(res[i-1]);
}
reverse(begin(new_res),end(new_res));
res=new_res;
}
}
return res;
}
