#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
/*
dp1[k][i] = can the kth block of black cells end at position i
dp1[k][i] |= dp1[k-1][j]
if j < i-C[k]
and [j+1, i-C[k]] has no black cells
and [i-C[k]+1, i] has no white cells
dp1[K][i] is valid if no black cells after i
*/
string solve_puzzle(string S, vector<int> C) {
int N = S.size(), K = C.size();
string res(N, ' ');
vector<int> pX(N+4), p_(N+4);
for(int i = 2; i <= N+1; i++) {
pX[i] += pX[i-1] + (S[i-2] == 'X');
p_[i] += p_[i-1] + (S[i-2] == '_');
}
for(int i = N+2; i <= N+3; i++) {
pX[i] += pX[i-1];
p_[i] += p_[i-1];
}
auto qX = [&](int l, int r, int add) {
l += add, r += add;
if (!l) return pX[r];
return pX[r] - pX[l-1];
};
auto q_ = [&](int l, int r, int add) {
l += add, r += add;
if (!l) return p_[r];
return p_[r] - p_[l-1];
};
vector<vector<int>> dp1(K+1, vector<int>(N+2)), dp2(K+1, vector<int>(N+2));
vector<vector<int>> dp3(K+1, vector<int>(N+1)), dp4(K+1, vector<int>(N+1));
vector<vector<int>> canX(K, vector<int>(N));
vector<int> can_1(N), can_2(N);
for(int i = 0; i <= N; i++) dp1[0][i] = qX(0, i+1, 0) == 0;
for(int k = 1; k <= K; k++) {
for(int i = 2; i <= N+1; i++) {
for(int j = 0; j < i-C[k-1]; j++) {
if (!qX(j+1, i-C[k-1], 0) && !q_(i-C[k-1]+1, i, 0)) dp1[k][i] |= dp1[k-1][j];
}
// cout << k-1 << ' ' << i-2 << ' ' << dp1[k][i] << endl;
}
queue<int> isX;
for(int i = N+1; i >= 2; i--) {
while(isX.size() && isX.front() >= i+C[k-1]) isX.pop();
int yes = dp1[k][i];
if (isX.size()) yes |= 1;
canX[k-1][i-2] |= yes;
if (dp1[k][i]) isX.push(i);
// cout << k-1 << ' ' << i-2 << ' ' << canX[k-1][i-2] << endl;
}
}
for(int i = 1; i <= N+1; i++) dp2[K][i] = qX(i-1, N+1, 2) == 0;
for(int k = K-1; k >= 0; k--) {
for(int i = N-1; i >= 0; i--) {
for(int j = N+1; j > i+C[k]; j--) {
if (!qX(i+C[k], j-1, 2) && !q_(i, i+C[k]-1, 2)) dp2[k][i] |= dp2[k+1][j];
}
// cout << k << ' ' << i << ' ' << dp2[k][i] << endl;
}
queue<int> isX;
for(int i = 0; i <= N-1; i++) {
while(isX.size() && isX.front() <= i-C[k]) isX.pop();
int yes = dp2[k][i];
if (isX.size()) yes |= 1;
canX[k][i] &= yes;
if (dp2[k][i]) isX.push(i);
// cout << k << ' ' << i << ' ' << canX[k][i] << endl;
}
}
for(int i = 0; i < N; i++) dp3[0][i] = qX(0, i, 1) == 0;
for(int k = 1; k <= K; k++) {
for(int i = 1; i <= N; i++) {
if (i-C[k-1]-1 >= 0 && !q_(i-C[k-1]-1, i, 1)) dp3[k][i] |= dp3[k-1][i-C[k-1]-1];
can_1[i-1] |= dp3[k][i];
}
}
for(int i = N; i > 0; i--) dp4[K][i] = qX(i, N, 1) == 0;
for(int k = K-1; k >= 0; k--) {
for(int i = N-1; i >= 0; i--) {
if (i+C[k]+1 <= N && !q_(i, i+C[k]+1, 2)) dp4[k][i] |= dp4[k+1][i+C[k]+1];
can_2[i] |= dp4[k][i];
}
}
for(int k = 0; k < K; k++) {
for(int i = 0; i < N; i++) {
// cout << k << ' ' << i << ' ' << dp3[k+1][i+1] << ' ' << dp4[k][i] << endl;
// cout << i << ' ' << can_1[i] << ' ' << can_2[i] << endl;
if (canX[k][i] && can_1[i] & can_2[i]) res[i] = '?';
else if (canX[k][i]) {
if (res[i] == '_' || res[i] == '?') res[i] = '?';
else res[i] = 'X';
} else if (can_1[i] & can_2[i]) {
if (res[i] == 'X' || res[i] == '?') res[i] = '?';
else res[i] = '_';
}
}
}
return res;
}
