#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
typedef long long ll;
ll n, k;
vector<ll> sumW;
vector<vector<bool>> possL, possR;
bool getPossL(int i, int j) {
if (i < 0) return j == 0;
return possL[i][j];
}
bool getPossR(int i, int j) {
if (i >= n) return j == 0;
return possR[i][j];
}
string solve_puzzle(string s, vector<int> c) {
n = s.size(), k = c.size();
sumW = vector<ll>(n+1);
for (int i = 1; i <= n; i++) sumW[i] = sumW[i-1] + (s[i-1] == '_');
possL = vector<vector<bool>>(n, vector<bool>(k+1));
possR = vector<vector<bool>>(n, vector<bool>(k+1));
possL[0][0] = s[0] != 'X';
for (int i = 1; i < n; i++) {
possL[i][0] = possL[i-1][0] && s[i] != 'X';
}
for (int i = 0; i < n; i++) {
for (int j = 1; j <= k; j++) {
possL[i][j] = s[i] != 'X' && getPossL(i-1, j);
if (i+1-c[j-1] < 0) continue;
possL[i][j] = possL[i][j] || ((sumW[i+1] - sumW[i+1-c[j-1]] == 0) && (i-c[j-1] < 0 || s[i-c[j-1]] != 'X') && getPossL(i-1-c[j-1], j-1));
}
}
possR[n-1][0] = s[n-1] != 'X';
for (int i = n-2; i >= 0; i--) {
possR[i][0] = possR[i+1][0] && s[i] != 'X';
}
for (int i = n-1; i >= 0; i--) {
for (int j = 1; j <= k; j++) {
possR[i][j] = s[i] != 'X' && getPossR(i+1, j);
if (i-1+c[k-j] >= n) continue;
possR[i][j] = possR[i][j] || ((sumW[i+c[k-j]] - sumW[i] == 0) && (i+c[k-j] >= n || s[i+c[k-j]] != 'X') && getPossR(i+1+c[k-j], j-1));
}
}
vector<ll> resB(n+1), resW(n+1);
for (int j = 0; j < k; j++) {
for (int i = 0; i+c[j] < n+1; i++) {
if (sumW[i+c[j]] - sumW[i] != 0) continue;
if (i-1 >= 0 && s[i-1] == 'X') continue;
if (i+c[j] < n && s[i+c[j]] == 'X') continue;
if (!getPossL(i-2, j) || !getPossR(i+1+c[j], k-j-1)) continue;
resB[i]++; resB[i+c[j]]--;
}
}
for (int i = 1; i < n; i++) resB[i] += resB[i-1];
for (int j = 0; j <= k; j++) {
for (int i = 0; i < n; i++) {
if (s[i] == 'X') continue;
if (!getPossL(i-1, j) || !getPossR(i+1, k-j)) continue;
resW[i] = 1;
}
}
string res;
for (int i = 0; i < n; i++) {
if (resB[i] > 0 && resW[i] > 0) res.push_back('?');
else if (resB[i] > 0) res.push_back('X');
else if (resW[i] > 0) res.push_back('_');
}
return res;
}
