## C - アメージングな文字列は、きみが作る！

### 実装

#include <iostream>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
vector<int> suffix_rank(string const & s) { // O(nloglogn)
int n = s.length();
vector<int> sa(n+1);
vector<int> rank(n+1);
repeat (i,n+1) {
sa[i] = i;
rank[i] = i < n ? s[i] : -1;
}
for (int k = 1; k <= n; k *= 2) {
auto compare = [&](int i, int j) {
int ri = i + k <= n ? rank[i + k] : -1;
int rj = j + k <= n ? rank[j + k] : -1;
return make_pair(rank[i], ri) < make_pair(rank[j], rj);
};
sort(sa.begin(), sa.end(), compare);
vector<int> dp(n+1);
dp[sa[0]] = 0;
repeat (i,n) dp[sa[i+1]] = dp[sa[i]] + compare(sa[i], sa[i+1]);
rank = dp;
}
return rank;
}

int main() {
string s; int k; cin >> s >> k;
int n = s.size();
if (n - count(s.begin(), s.end(), 'a') <= k) {
cout << string(n-k, 'a') << endl;
} else {
vector<int> rank = suffix_rank(s);
int a = k, b = 0;
int x = k, y = 0;
repeat (i,n) {
if (s[i] == 'a') {
++ b;
} else {
-- a;
++ b;
if (a < 0) break;
}
if (x < a+b) {
x = a+b;
y = i+1;
} else if (x == a+b and rank[i+1] < rank[y]) {
y = i+1;
}
}
cout << string(x, 'a') << s.substr(y) << endl;
}
return 0;
}