#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]; }
pair<vector<vector<bool>>, 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));
D[0][0] = true;
for (int i = 1; i <= N; i++) D[i][0] = Wp(1, i);
// 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];
}
}
auto Da = D;
for (int j = 1; j <= K; j++) {
for (int i = 1; i <= N; i++) {
Da[i][j] = D[i][j] || (Da[i - 1][j] && Wp(i, i));
}
}
if (rev) {
reverse(iterall(s));
reverse(iterall(c));
}
return {D, Da};
}
string solve_puzzle(string s, vector<int> c) {
N = (int)s.size();
K = (int)c.size();
auto [Dfor, Dfa] = fill_dynamic(s, c);
auto [Drev, Dra] = 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 = 0; i < c[j - 1]; i++) cout << 0 << " ";
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 + 1);
for (int i = 1; i <= N; i++) {
bool flag = false;
for (int j = 0; j <= K; j++) {
flag = flag || (Dfa[i - 1][j] && Dra[N - i][K - j]);
}
if (!flag) res[i] = 2;
}
vector<vector<pi>> bex(N + 1, vector<pi>());
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> fl(N + 2, N + 1), fr(N + 2, N + 1);
for (int i = N; i >= 1; i--) {
if (D[i][j])
fr[i] = i;
else
fr[i] = fr[i + 1];
}
for (int i = 1; i <= N; i++) {
if (D[i][j])
fl[i] = i;
else
fl[i] = fl[i - 1];
}
for (int i = 1; i <= N; i++) {
if (s[i - 1] == 'X') {
int lb = fr[i];
int rb = fl[min(N, i + c[j - 1] - 1)];
// cout << lb << " " << rb << endl;
if (lb == N + 1 || rb == N + 1) continue;
bex[i].emplace_back(rb - c[j - 1] + 1, lb);
}
}
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]);
}
vector<pi> bmark;
for (int i = 1; i <= N; i++) {
if (s[i - 1] != 'X') continue;
int s = 0, e = N + 1;
for (auto [l, r] : bex[i]) s = max(s, l), e = min(e, r);
if (s <= e) bmark.emplace_back(s, e);
}
sort(iterall(bmark));
vector<pi> hap;
for (auto [s, e] : bmark) {
if (!hap.empty() && hap.back().second >= s)
hap.back().second = max(hap.back().second, e);
else
hap.emplace_back(s, e);
}
for (auto [s, e] : hap) {
for (int i = s; i <= e; i++) res[i] = 2;
}
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;
}
