#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int query(string str); int N; int getQ(string s) { if(s.size() > N) return N+20; return query(s); } string cdq(int n, int S, string doklej) { N=n; if(n==0) return doklej; vector<int> cnt(S); string alph = "abcdefghijklmnopqrstuvwxyz"; vector<int> V; for(int i=0; i<S; ++i) { string s = ""; s.push_back(alph[i]); while(getQ(s+doklej)==s.size()) s.push_back(alph[i]); cnt[i] = s.size() - 1; if(cnt[i]) V.push_back(i); } sort(V.begin(), V.end(), [&](int a, int b){ string s(cnt[a], alph[a]); s.push_back(alph[b]); if(getQ(s+doklej)==s.size()) return true; return false; }); vector<int> bloki; for(int i=V.size()-1; i>=0; --i) { if(i==0) bloki.push_back(cnt[V[i]]); else { int v = V[i]; int u = V[i-1]; int lo = 1; int hi = n; while(lo < hi) { string s = ""; for(int x=0; x<cnt[u]; ++x) s.push_back(alph[u]); int mid = (lo+hi+1)/2; for(int x=0;x<mid;++x) s.push_back(alph[v]); if(getQ(s+doklej)==s.size()) lo = mid; else hi=mid-1; } bloki.push_back(lo); } } reverse(bloki.begin(), bloki.end()); string res = "", stos=""; for(int i=0; i<bloki.size(); ++i) for(int x=0; x<bloki[i]; ++x) res.push_back(alph[V[i]]); for(int i=res.size()-1; i>=0; --i) { for(int lit : V) { string old_res = res; stos = ""; for(int x=res.size()-1; x>=i; --x) { stos.push_back(res[x]); res.pop_back(); } reverse(stos.begin(), stos.end()); res.push_back(alph[lit]); res += stos; if(getQ(res+doklej)!=res.size()) { res = old_res; } else i++; } } return cdq(n-res.size(), S, res); } string guess(int n, int S) { return cdq(n,S,""); }