#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)); // is there valid soln
vector<int> block(N, -1);
for(int i = 0; i <= N; i++) dp1[0][i] = qX(0, i, 0) == 0;
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]; // can the kth block end at i
}
}
for(int i = 1; i <= N+1; i++) dp2[K][i] = qX(i, N+1, 2) == 0;
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]; // can the kth block start at i
// cout << k << ' ' << i << ' ' << dp1[k][i+2] << ' ' << dp2[k][i] << endl;
if (S[i-1] != 'X' && dp2[k][i] && dp1[k][i-2+2]) { // valid starting point for kth block
block[i] = max(block[i], i+C[k]-1);
}
}
}
for(int k = 0; 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 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 (dp1[k][i-1+2] && dp2[k][i+1]) {
res[i] = '_';
}
}
}
for(int l = 0; l < N; l++) {
for(int x = l; x <= block[l]; x++) {
if (S[x] != '.') continue;
if (res[x] == '.' || res[x] == 'X') res[x] = 'X';
else res[x] = '?';
}
}
return res;
}
