Runas mágicas

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

using i64 = long long;

int main() {
  cin.tie(0)->sync_with_stdio(0);

  string s; cin >> s;
  int d; cin >> d;
  int n = s.size();

  reverse(s.begin(), s.end());

  i64 curr = 0;
  for (int i = 0; i < (int)s.size(); ++i) {
    curr <<= 1;
    if (s[i] == 'B')
      curr += 1;
  }

  // cout << curr << '\n';

  curr += d;

  string res;
  while (curr > 0) {
    res += ((curr & 1) ? 'B' : 'A');
    curr >>= 1;
  }

  while (res.size() < n) res = res + 'A';
  while (res.size() > n) res.pop_back();

  cout << res << '\n';
}