#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
vector<vector<bool>> gen_dp(string s, vector<int> c) {
//cout << s << "\n";
int n_cells = s.size(), n_blocks = c.size();
vector<int> pref0(n_cells + 1), pref1(n_cells + 1);
for (int i = 0; i < n_cells; i++) {
pref0[i + 1] = pref0[i] + (s[i] == '_');
pref1[i + 1] = pref1[i] + (s[i] == 'X');
}
vector<vector<bool>> dp(n_blocks + 1, vector<bool>(n_cells + 1));
for (int i = 0; i <= n_cells; i++) {
dp[0][i] = (pref1[i] == 0);
}
for (int i = 0; i < n_blocks; i++) {
for (int j = 0; j < n_cells; j++) {
if ((s[j] == 'X' || s[j] == '.') && j + 1 - c[i] >= 0 && pref0[j + 1] - pref0[j + 1 - c[i]] == 0 && s[j - c[i]] != 'X')
dp[i + 1][j + 1] = dp[i][j - c[i]];
if (s[j] == '_' || s[j] == '.') dp[i + 1][j + 1] = dp[i + 1][j + 1] || dp[i + 1][j];
}
}
/*for (int i = 0; i <= n_blocks; i++) {
for (int j = 0; j <= n_cells; j++) {
cout << dp[i][j] << " ";
}
cout << "\n";
}*/
return dp;
}
string solve_puzzle(string s, vector<int> c) {
s = "_" + s + "_";
int n_cells = s.size(), n_blocks = c.size();
vector<vector<bool>> dp = gen_dp(s, c);
reverse(s.begin(), s.end());
reverse(c.begin(), c.end());
vector<vector<bool>> dpr = gen_dp(s, c);
reverse(s.begin(), s.end());
reverse(c.begin(), c.end());
for (vector<bool> dprv : dpr) reverse(dprv.begin(), dprv.end());
vector<int> pref0(n_cells + 1), pref1(n_cells + 1);
for (int i = 0; i < n_cells; i++) {
pref0[i + 1] = pref0[i] + (s[i] == '_');
pref1[i + 1] = pref1[i] + (s[i] == 'X');
}
vector<bool> wok(n_cells), bok(n_cells);
for (int i = 0; i < n_cells; i++) {
if (s[i] != 'X') {
for (int k = 0; k <= n_blocks; k++) {
wok[i] = wok[i] || (dp[k][i] && dpr[n_blocks - k][n_cells - i - 1]);
}
}
}
for (int j = 0; j < n_blocks; j++) {
vector<int> sok(n_cells);
int len = c[j];
for (int i = 1; i < n_cells - 1; i++) {
if (s[i - 1] == 'X' || s[i + len] == 'X') continue;
if (pref0[i + len] - pref0[i] != 0) continue;
sok[i] = sok[i] || (dp[j][i - 1] && dpr[n_blocks - j - 1][n_cells - i - len - 1]);
}
int charge = 0;
for (int i = 0; i < n_cells; i++) {
if (sok[i]) charge = len;
if (charge > 0) bok[i] = 1;
charge--;
}
}
string ans;
for (int i = 1; i < n_cells - 1; i++) {
if (bok[i] && wok[i]) ans += "?";
else if (wok[i]) ans += "_";
else if (bok[i]) ans += "X";
else throw 1;
}
return ans;
}
