#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
auto get_white_black(string s, vector<int> c) {
int n = s.size();
int k = c.size();
vector<int> cnt_(n+1);
vector<int> cntX(n+1);
for (int i = 0; i < n; ++i) {
cnt_[i+1] = cnt_[i] + (s[i] == '_');
cntX[i+1] = cntX[i] + (s[i] == 'X');
}
auto anywhite = [&](int l, int r) -> bool {
l = max(l, 0);
return cnt_[r+1] - cnt_[l] > 0;
};
vector<vector<bool>> white(n, vector<bool>(k+1, false));
vector<vector<bool>> black(n, vector<bool>(k+1, false));
// white[n][k]: può essere white e avere k blocchi completati?
// black[n][k]: può essere black e la fine del k-esimo blocco?
for (int i = 0; i < n; ++i) white[i][0] = (s[i] != 'X' && (!i || white[i-1][0]));
for (int j = 1; j <= k; ++j) {
white[0][j] = false;
black[0][j] = (j == 1 && c[0] == 1);
for (int i = 1; i < n; ++i) {
white[i][j] = (s[i] != 'X') && (white[i-1][j] || black[i-1][j]);
if (j == 1) {
black[i][j] = !anywhite(i-c[j-1]+1, i) && (i+1 >= c[j-1] && (i+1 == c[j-1] || white[i-c[j-1]][j-1]));
} else {
black[i][j] = !anywhite(i-c[j-1]+1, i) && (i >= c[j-1] && white[i-c[j-1]][j-1]);
}
}
}
return make_pair(white, black);
}
string solve_puzzle(string s, vector<int> c) {
int n = s.size();
int k = c.size();
auto [white, black] = get_white_black(s, c);
auto ss = s; reverse(ss.begin(), ss.end());
auto cc = c; reverse(cc.begin(), cc.end());
auto [rwhite, rblack] = get_white_black(ss, cc);
auto rev = [&](int i) -> int { return n - 1 - i; };
for (int j = 0; j < k; ++j) {
white[n-1][j] = black[n-1][j] = false;
}
for (int j = 0; j <= k; ++j) {
for (int i = 0; i < n-1; ++i) {
white[i][j] = white[i][j] && (rwhite[rev(i+1)][k-j] || rblack[rev(i+1)][k-j]);
black[i][j] = black[i][j] && rwhite[rev(i+1)][k-j];
}
}
#ifdef LORENZO
for (int j = 0; j <= k; ++j) {
for (int i = 0; i < n; ++i) {
cout << white[i][j] << black[i][j] << " ";
}
cout << "\n";
}
#endif
// return "O_o";
vector<vector<int>> pblack(n+1, vector<int>(k+1));
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= k; ++j) {
pblack[i+1][j] = pblack[i][j] + black[i][j];
}
}
auto anyblack = [&](int l, int r, int j) -> bool {
r = min(r, n-1);
return (pblack[r+1][j] - pblack[l][j]) > 0;
};
// ans:
// i can be _ if white[i][j] for any j
// i can be X if black[i][j] for any j for any i \in [i, i+c[j-1]]
vector<bool> ww(n, false);
vector<bool> bb(n, false);
string ans(n, '*');
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= k; ++j) ww[i] = ww[i] || white[i][j];
for (int j = 1; j <= k; ++j) {
bb[i] = bb[i] || anyblack(i, i+c[j-1]-1, j);
}
if (ww[i] && bb[i]) ans[i] = '?';
else if (ww[i]) ans[i] = '_';
else if (bb[i]) ans[i] = 'X';
else ans[i] = '*';
}
return ans;
}
