#include "paint.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;
#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed
vector<int> WpfS, BpfS;
int N, K;
// W를 [l, r]에 놓는 게 가능한가?
bool Wp(int l, int r) { return l == 0 || l > r || BpfS[r] == BpfS[l - 1]; }
// B를 [l, r]에 놓는 게 가능한가?
bool Bp(int l, int r) { return l == 0 || l > r || WpfS[r] == WpfS[l - 1]; }
vector<vector<bool>> fill_dynamic(string &s, vector<int> &c, bool rev = false) {
if (rev) {
reverse(iterall(s));
reverse(iterall(c));
}
WpfS.resize(N + 1, 0);
BpfS.resize(N + 1, 0);
fill(iterall(WpfS), 0);
fill(iterall(BpfS), 0);
for (int i = 0; i < N; i++) {
if (s[i] == '_') WpfS[i + 1] = 1;
if (s[i] == 'X') BpfS[i + 1] = 1;
WpfS[i + 1] += WpfS[i];
BpfS[i + 1] += BpfS[i];
}
vector<vector<bool>> D(N + 1, vector<bool>(K + 1));
vector<vector<bool>> F(N + 1, vector<bool>(K + 1));
for (int i = 0; i <= N; i++) D[i][0] = true;
// for (int i = 0; i <= K; i++) D[0][i] = true;
for (int i = c[0]; i <= N; i++) {
F[i][1] = Wp(1, i - c[0]);
D[i][1] = F[i][1] && Bp(i - c[0] + 1, i);
}
for (int j = 2; j <= K; j++) {
for (int i = c[j - 1] + 1; i <= N; i++) {
F[i][j] = Wp(i - c[j - 1], i - c[j - 1]) &&
(F[i - 1][j] || D[i - c[j - 1] - 1][j - 1]);
D[i][j] = Bp(i - c[j - 1] + 1, i) && F[i][j];
}
}
if (rev) {
reverse(iterall(s));
reverse(iterall(c));
}
return D;
}
string solve_puzzle(string s, vector<int> c) {
N = (int)s.size();
K = (int)c.size();
auto Dfor = fill_dynamic(s, c);
auto Drev = fill_dynamic(s, c, true);
vector<vector<bool>> D(N + 1, vector<bool>(K + 1));
for (int j = 1; j <= K; j++) {
for (int i = c[j - 1]; i <= N; i++)
D[i][j] = (Dfor[i][j] && Drev[N - i + c[j - 1]][K - j + 1]);
}
vector<int> res(N);
for (int i = 1; i <= N; i++)
if (s[i - 1] == 'X') res[i] = 2;
for (int j = 1; j <= K; j++) {
vector<int> p(N + 1);
for (int i = 1; i <= N; i++) p[i] = p[i - 1] + D[i][j];
vector<int> tmp(N + 1);
for (int i = 1; i <= N; i++) {
int r = min(N, i + c[j - 1] - 1);
int l = i - 1;
int d = p[r] - p[l];
if (d == p.back())
tmp[i] = 2;
else if (d != 0)
tmp[i] = 1;
}
for (int i = 1; i <= N; i++) res[i] = max(res[i], tmp[i]);
}
string ret;
vector<char> mp = {'_', '?', 'X'};
for (int i = 1; i <= N; i++) ret.push_back(mp[res[i]]);
assert(ret.size() == N);
return ret;
}
