#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
string solve_puzzle(string S, vector<int> C) {
int N = S.size(), K = C.size();
string res = S;
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)); // can the kth block of black cells end/start at i
vector<vector<int>> canX(K+1, vector<int>(N)); // can i be a black cell in the kth block of black cells
for(int i = 0; i <= N; i++) {
dp1[0][i] = qX(0, i+1, 0) == 0;
if (i != N) canX[0][i] |= dp1[0][i];
}
for(int k = 1; k <= K; k++) {
for(int i = 2; i <= N+1; i++) {
if (i-C[k-1]+1 >= 2 && !qX(i-C[k-1], i-C[k-1], 0) && !q_(i-C[k-1]+1, i, 0)) dp1[k][i] |= dp1[k-1][i-C[k-1]-1];
}
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);
}
}
for(int i = 1; i <= N+1; i++) {
dp2[K][i] = qX(i-1, N+1, 2) == 0;
if (i != 1) canX[K][i-2] &= dp2[K][i];
}
for(int k = K-1; k >= 0; k--) {
for(int i = N-1; i >= 0; i--) {
if (i+C[k]-1 < N && !qX(i+C[k], i+C[k], 2) && !q_(i, i+C[k]-1, 2)) dp2[k][i] |= dp2[k+1][i+C[k]+1];
}
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);
}
}
for(int k = 1; k <= K; k++) {
for(int i = 2; i <= N+1; i++) {
if (S[i-2] != 'X') dp1[k][i] |= dp1[k][i-1];
}
}
for(int k = K-1; k >= 0; k--) {
for(int i = N-1; i >= 0; i--) {
if (S[i] != 'X') dp2[k][i] |= dp2[k][i+1];
}
}
for(int i = 0; i < N; i++) {
if (S[i] != '.') continue;
for(int k = 0; k <= K; k++) {
if (dp2[k][i+1] && dp1[k][i-1+2]) {
res[i] = '_';
}
}
}
for(int i = 0; i < N; i++) {
if (S[i] != '.') continue;
for(int k = 0; k <= K; k++) {
if (canX[k][i]) {
if (res[i] == '.') res[i] = 'X';
else res[i] = '?';
}
}
}
return res;
}
