#include <bits/stdc++.h>
using namespace std;
int query(string str);
string guess(int n, int s) {
vector<int> freq(s, 0);
int used = 0;
for (int c = 0; c < s; c++) {
int lo = 0, hi = n - used, best = 0;
while (lo <= hi) {
int mid = (lo + hi) / 2;
string t(mid, 'a' + c);
int res = query(t);
if (res == mid) {
best = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
freq[c] = best;
used += best;
}
string ans = "";
for (int c = 0; c < s; c++) {
int f = freq[c];
if (f == 0) continue;
vector<int> blocks(ans.size() + 1, 0);
int remaining = f;
for (int i = 0; i <= (int)ans.size() && remaining > 0; i++) {
int lo = 0, hi = remaining, best = 0;
while (lo <= hi) {
int mid = (lo + hi) / 2;
string t = "";
for (int j = 0; j <= (int)ans.size(); j++) {
if (j == i) t += string(mid, 'a' + c);
if (j < (int)ans.size()) t += ans[j];
}
int res = query(t);
if (res >= (int)ans.size() + mid) {
best = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
blocks[i] = best;
remaining -= best;
}
string new_ans = "";
for (int i = 0; i <= (int)ans.size(); i++) {
new_ans += string(blocks[i], 'a' + c);
if (i < (int)ans.size()) new_ans += ans[i];
}
ans = new_ans;
}
return ans;
}
