// code template is in https://github.com/drken1215/algorithm/blob/master/template_minimum.cpp #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include using namespace std; //------------------------------// // Utility //------------------------------// using ll = long long; using i128 = __int128_t; using u128 = __uint128_t; using pint = pair; using pll = pair; using tll = array; using fll = array; using vint = vector; using vll = vector; using dint = deque; using dll = deque; using vvint = vector>; using vvll = vector>; using vpll = vector>; template using min_priority_queue = priority_queue, greater>; template inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); } template inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); } template inline auto maxll(S a, T b) { return max(ll(a), ll(b)); } template inline auto minll(S a, T b) { return min(ll(a), ll(b)); } template auto max(const T &a) { return *max_element(a.begin(), a.end()); } template auto min(const T &a) { return *min_element(a.begin(), a.end()); } template auto argmax(const T &a) { return max_element(a.begin(), a.end()) - a.begin(); } template auto argmin(const T &a) { return min_element(a.begin(), a.end()) - a.begin(); } template auto accum(const vector &a) { return accumulate(a.begin(), a.end(), T()); } template auto accum(const deque &a) { return accumulate(a.begin(), a.end(), T()); } #define REP(i, a) for (long long i = 0; i < (long long)(a); i++) #define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++) #define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i) #define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i) #define EB emplace_back #define PF push_front #define PB push_back #define MP make_pair #define FI first #define SE second #define ALL(x) x.begin(), x.end() #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl // input template istream& operator >> (istream &is, vector &P) { for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; } template istream& operator >> (istream &is, deque &P) { for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; } template istream& operator >> (istream &is, vector> &P) { for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; } // output template ostream& operator << (ostream &s, const pair &P) { return s << '<' << P.first << ", " << P.second << '>'; } template ostream& operator << (ostream &s, const array &P) { return s << '<' << P[0] << "," << P[1] << '>'; } template ostream& operator << (ostream &s, const array &P) { return s << '<' << P[0] << "," << P[1] << "," << P[2] << '>'; } template ostream& operator << (ostream &s, const array &P) { return s << '<' << P[0] << "," << P[1] << "," << P[2] << "," << P[3] << '>'; } template ostream& operator << (ostream &s, const vector &P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template ostream& operator << (ostream &s, const deque &P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template ostream& operator << (ostream &s, const vector> &P) { for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; } template ostream& operator << (ostream &s, const set &P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template ostream& operator << (ostream &s, const multiset &P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template ostream& operator << (ostream &s, const unordered_set &P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template ostream& operator << (ostream &s, const map &P) { for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } template ostream& operator << (ostream &s, const unordered_map &P) { for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } void yes(bool a) { cout << (a ? "yes" : "no") << endl; } void YES(bool a) { cout << (a ? "YES" : "NO") << endl; } void Yes(bool a) { cout << (a ? "Yes" : "No") << endl; } const vector DX = {1, 0, -1, 0, 1, -1, 1, -1}; const vector DY = {0, 1, 0, -1, 1, -1, -1, 1}; // Segment Tree template struct SegmentTree { using Func = function; // core member int N; Func OP; Monoid IDENTITY; // inner data int log, offset; vector dat; // constructor SegmentTree() {} SegmentTree(const Func &op, const Monoid &identity) : OP(op), IDENTITY(identity) { } SegmentTree(int n, const Func &op, const Monoid &identity) { init(n, op, identity); } SegmentTree(const vector &v, const Func &op, const Monoid &identity) { init(v, op, identity); } void init(const Func &op, const Monoid &identity) { OP = op; IDENTITY = identity; } void init(int n) { N = n; log = 0, offset = 1; while (offset < N) ++log, offset <<= 1; dat.assign(offset * 2, IDENTITY); } void init(const vector &v) { init((int)v.size()); build(v); } void init(int n, const Func &op, const Monoid &identity) { init(op, identity); init(n); } void init(const vector &v, const Func &op, const Monoid &identity) { init((int)v.size(), op, identity); build(v); } int size() const { return N; } // pull, build void pull(int k) { dat[k] = OP(dat[k * 2], dat[k * 2 + 1]); } void build(const vector &v) { assert(N == (int)v.size()); for (int i = 0; i < N; ++i) dat[i + offset] = v[i]; for (int k = offset - 1; k > 0; --k) pull(k); } // setter and getter, set: update A[i], i is 0-indexed, O(log N) void set(int i, const Monoid &v) { assert(0 <= i && i < N); int k = i + offset; dat[k] = v; while (k >>= 1) pull(k); } Monoid get(int i) const { assert(0 <= i && i < N); return dat[i + offset]; } Monoid operator [] (int i) const { return get(i); } // get [l, r), l and r are 0-indexed, O(log N) Monoid prod(int l, int r) { assert(0 <= l && l <= r && r <= N); Monoid val_left = IDENTITY, val_right = IDENTITY; l += offset, r += offset; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) val_left = OP(val_left, dat[l++]); if (r & 1) val_right = OP(dat[--r], val_right); } return OP(val_left, val_right); } Monoid all_prod() { return dat[1]; } // get max r that f(get(l, r)) = True (0-indexed), O(log N) // f(IDENTITY) need to be True int max_right(const function f, int l = 0) { if (l == N) return N; l += offset; Monoid sum = IDENTITY; do { while (l % 2 == 0) l >>= 1; if (!f(OP(sum, dat[l]))) { while (l < offset) { l = l * 2; if (f(OP(sum, dat[l]))) { sum = OP(sum, dat[l]); ++l; } } return l - offset; } sum = OP(sum, dat[l]); ++l; } while ((l & -l) != l); // stop if l = 2^e return N; } // get min l that f(get(l, r)) = True (0-indexed), O(log N) // f(IDENTITY) need to be True int min_left(const function f, int r = -1) { if (r == 0) return 0; if (r == -1) r = N; r += offset; Monoid sum = IDENTITY; do { --r; while (r > 1 && (r % 2)) r >>= 1; if (!f(OP(dat[r], sum))) { while (r < offset) { r = r * 2 + 1; if (f(OP(dat[r], sum))) { sum = OP(dat[r], sum); --r; } } return r + 1 - offset; } sum = OP(dat[r], sum); } while ((r & -r) != r); return 0; } // debug friend ostream& operator << (ostream &s, const SegmentTree &seg) { for (int i = 0; i < (int)seg.size(); ++i) { s << seg[i]; if (i != (int)seg.size() - 1) s << " "; } return s; } // dump void dump() { int pt = 1; for (int h = 0; h <= log; h++) { for (int i = 0; i < (1<> N >> M >> S >> T; int all_anum = 0, all_wnum = 0, all_qnum = 0, sub_anum = 0, sub_wnum = 0, sub_qnum = 0; REP(i, N) { if (S[i] == 'A') all_anum++; else if (S[i] == 'W') all_wnum++; else all_qnum++; } REP(i, M) { if (S[i] == 'A') sub_anum++; else if (S[i] == 'W') sub_wnum++; else sub_qnum++; } if (T == "Warong") { // 最初の M 文字が A and それ以外の中に W が含まれる // 最初の M 文字は A にしておく REP(i, M) S[i] = 'A'; // A が N - 1 文字の場合のみ、残りが W であることが確定する if (all_anum == N - 1) { REP(i, N) if (S[i] == '?') S[i] = 'W'; } } else { // 「最初の M 文字に W が含まれる」 or 「すべてが A である」 // 最初の M 文字がすべて A であるとき -> 全部 A でなければならない if (sub_anum == M) { REP(i, N) S[i] = 'A'; } // 最初の M 文字の中に W が含まれるとき else if (sub_wnum > 0) { // 何も決まらないはず } // 最初の M 文字が A と ? であって、? が含まれるとき else { // S が W を含むとき -> 最初の M 文字はすべて A でなければならない if (all_wnum > 0) { REP(i, M) S[i] = 'A'; } // それ以外のとき -> 何も決まらないはず } } cout << S << endl; }