// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,mmx,tune=native")
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
string S;
int N, K;
vector<int> C;
vector<int> pref_white, pref_black, lim, ans;
bitset<200000> can_white, can_black;
bitset<200000> memo[100][2], vis[100][2];
struct disj {
vector<int> p;
void init(int n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
int par(int n) {
return (p[n] == n)? n : p[n] = par(p[n]);
}
void join(int le, int ri) {
if (ri >= p.size()) return;
le = par(le);
ri = par(ri);
p[le] = ri;
}
} hop_white, hop_black;
inline bool check_white(int le, int ri) { //get number of white spaces in le...ri
if (ri >= N) return false;
if (le > ri) return true;
int res = pref_white[ri];
if (le > 0) res -= pref_white[le - 1];
return (res == 0);
}
inline bool check_black(int le, int ri) { //get number of black spaces in le...ri
if (ri >= N) return false;
if (le > ri) return true;
int res = pref_black[ri];
if (le > 0) res -= pref_black[le - 1];
return (res == 0);
}
inline int needed_left(int p) {
int res = lim[K - 1];
if (p > 0) res -= lim[p - 1];
return res;
}
bool dp(int n, int k, int last_black) {
if (k == K) {
if (check_black(n, N - 1)) {
for (int i = n; i < N; i++) {
can_white[i] = 1;
hop_white.join(i, i + 1);
i = hop_white.par(i);
// can_white[i] = 1;
}
return true;
}
return false;
}
if (n == N) return false;
if (N - n < needed_left(k)) return false;
if (vis[k][last_black][n]) return memo[k][last_black][n];
vis[k][last_black][n] = 1;
bool res_ = false, resX = false;
if (S[n] == '_') {
can_white[n] = 1;
hop_white.join(n, n + 1);
return memo[k][last_black][n] = dp(n + 1, k, 0);
} else if (S[n] == 'X') {
if (!last_black && check_white(n, n + C[k] - 1)) {
bool res = dp(n + C[k], k + 1, 1);
if (res) for (int i = n; i < n + C[k]; i++) {
for (int i = n; i < N; i++) {
can_black[i] = 1;
hop_black.join(i, i + 1);
i = hop_black.par(i);
// can_black[i] = 1;
}
}
return memo[k][last_black][n] = res;
} else {
return memo[k][last_black][n] = false;
}
}
res_ = dp(n + 1, k, 0);
if (!last_black && check_white(n, n + C[k] - 1)) resX = dp(n + C[k], k + 1, 1);
if (res_) can_white[n] = 1, hop_white.join(n, n + 1);
if (resX) for (int i = n; i < n + C[k]; i++) {
for (int i = n; i < N; i++) {
can_black[i] = 1;
hop_black.join(i, i + 1);
i = hop_black.par(i);
// can_black[i] = 1;
}
}
return memo[k][last_black][n] = (res_ || resX);
}
string solve_puzzle(string s, vector<int> c) {
S = s;
N = s.size();
K = c.size();
C = c;
pref_white.resize(N);
pref_black.resize(N);
ans.resize(N);
lim.resize(N);
for (int i = 0; i < N; i++) {
pref_white[i] = (S[i] == '_')? 1 : 0;
if (i > 0) pref_white[i] += pref_white[i - 1];
pref_black[i] = (S[i] == 'X')? 1 : 0;
if (i > 0) pref_black[i] += pref_black[i - 1];
if (S[i] == '.') {
ans[i] = 0;
} else if (S[i] == '_') {
ans[i] = 1;
} else if (S[i] == 'X') {
ans[i] = 2;
}
}
for (int i = 0; i < K; i++) {
lim[i] = C[i];
if (i > 0) lim[i] += lim[i - 1];
}
hop_white.init(N);
hop_black.init(N);
dp(0, 0, 0);
string res;
for (int i = 0; i < N; i++) {
ans[i] = can_white[i] | (can_black[i] << 1);
if (ans[i] == 0) {
res.push_back('E');
} else if (ans[i] == 1) {
res.push_back('_');
} else if (ans[i] == 2) {
res.push_back('X');
} else {
res.push_back('?');
}
}
return res;
}
