#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 = 1, 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 = "";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
for (int c = 0; c < s; c++) {
int f = freq[c];
if (f == 0) continue;
int remaining = f;
int m = ans.size();
vector<int> add(m + 1, 0);
vector<int> order(m + 1);
iota(order.begin(), order.end(), 0);
shuffle(order.begin(), order.end(), rng);
for (int idx : order) {
if (remaining == 0) break;
int lo = 1, hi = remaining, best = 0;
while (lo <= hi) {
int mid = (lo + hi) / 2;
string t = "";
for (int j = 0; j <= m; j++) {
if (j == idx) t += string(mid, 'a' + c);
if (j < m) t += ans[j];
}
int res = query(t);
if (res >= (int)ans.size() + mid) {
best = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
add[idx] = best;
remaining -= best;
}
string new_ans = "";
for (int i = 0; i <= m; i++) {
new_ans += string(add[i], 'a' + c);
if (i < m) new_ans += ans[i];
}
ans = new_ans;
}
return ans;
}
