#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 = 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, bool t) {
if (t) l += 2, r += 2;
if (!l) return pX[r];
return pX[r] - pX[l-1];
};
auto q_ = [&](int l, int r, bool t) {
if (t) l += 2, r += 2;
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)), canX(K, vector<int>(N));
vector<int> canY(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++) { // precomputed on previous iteration of k????
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, 1) == 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--) { // precomputed on previous iteration of k????
if (!qX(i+C[k], j-1, 1) && !q_(i, i+C[k]-1, 1)) 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 k = 0; k < K; k++) {
queue<pair<int,int>> forw, del, bak;
int latest_ = -1;
for(int i = 0; i < N; i++) {
if (!canX[k][i]) latest_ = i;
else if (canX[k][i] && S[i] == '.') res[i] = 'X';
if (latest_ < i-C[k]+1) forw.push({i-C[k]+1, i});
}
for(int i = 0; i < N; i++) {
while (forw.size() && forw.front().first <= i) del.push(forw.front()), forw.pop();
while (del.size() && del.front().second < i) bak.push(del.front()), del.pop();
if (forw.size() || bak.size()) canY[i] = 1;
}
}
for(int i = 0; i < N; i++) {
if (canY[i]) {
if (res[i] == 'X') res[i] = '?';
else res[i] = '_';
}
}
return res;
}
