#include "bits/stdc++.h"
#include "paint.h"
// #include "grader.cpp"
using namespace std;
#define SZ(s) (int)s.size()
string solve_puzzle(string s, vector<int> c) {
int n = (int)s.size(), k = (int)c.size();
vector <vector <bool>> dp(n+1, vector <bool> (k+1, 0)), dp1(n+1, vector <bool> (k+1, 0)),
dp2(n+1, vector <bool> (k+1, 0)), dp3(n+1, vector <bool> (k+1, 0));
vector <int> p_(n+1, 0), px(n+1, 0);
for(int i = 0; i < n; i++) {
p_[i] = (!i ? 0 : p_[i-1]) + (s[i] == '_');
px[i] = (!i ? 0 : px[i-1]) + (s[i] == 'X');
}
vector <int> p(n+1, 0), v;
string ans = "";
for(int i = 0; i < n; i++) {
ans += '_';
}
if(!p_[c[0]-1]) dp[c[0]-1][0] = true, v.push_back(c[0]-1), dp2[c[0]-1][0] = true;
for(int i = c[0]; i < n; i++) {
if(!(px[i - c[0]]) and !(p_[i] - p_[i - c[0]])) dp[i][0] = true, v.push_back(i), dp2[i][0] = true;
if(dp[i-1][0] and s[i] != 'X') dp[i][0] = true;
}
if(k == 1) {
int cnt = 0;
for(auto i : v) {
if(px[n-1] - px[i]) continue;
p[i-c[0]+1]++, p[i+1]--;
cnt++;
}
for(int i = 0; i < n; i++) {
p[i] += (!i ? 0 : p[i-1]);
if(p[i] == cnt) ans[i] = 'X';
else if(p[i]) ans[i] = '?';
}
return ans;
}
for(int j = 1; j < k; j++) {
for(int i = c[j] + 1; i < n; i++) {
if(dp[i - c[j] - 1][j-1] and s[i - c[j]] != 'X' and !(p_[i] - p_[i - c[j]])) dp[i][j] = dp2[i][j] = true;
if(dp[i-1][j] and s[i] != 'X') dp[i][j] = true;
}
}
if(!(p_[n-1] - p_[n-1-c[k-1]])) dp1[n-c[k-1]][k-1] = dp3[n-c[k-1]][k-1] = true;
for(int i = n-c[k-1]; i >= 0; i--) {
if(!(px[n-1] - px[i + c[k-1] - 1]) and !(p_[i + c[k-1] - 1] - (!i ? 0 : p_[i-1]))) dp1[i][k-1] = dp3[i][k-1] = true;
if(dp1[i+1][k-1] and s[i] != 'X') dp1[i][k-1] = true;
}
for(int j = k-2; j >= 0; j--) {
for(int i = n-c[j]-2; i >= 0; i--) {
if(dp1[i + c[j] + 1][j+1] and s[i + c[j]] != 'X' and !(p_[i + c[j] - 1] - (!i ? 0 : p_[i-1]))) dp1[i][j] = dp3[i][j] = true;
if(dp1[i+1][j] and s[i] != 'X') dp1[i][j] = true;
}
}
for(int j = 0; j < k-1; j++) {
for(int i = c[j] - 1; i + 2 < n; i++) {
if(dp2[i][j] and dp1[i + 2][j+1] and s[i+1] != 'X') p[i+1]--, p[i-c[j]+1]++;
}
}
for(int i = c[k-1] - 1; i < n; i++) {
if(dp2[i][k-1] and !(px[n-1] - px[i])) p[i+1]--, p[i-c[k-1]+1]++;
}
for(int i = n-1; i >= 0; i--) {
if(dp3[i][0] and !((!i ? 0 : px[i-1]))) p[i]++, p[i+c[0]]--;
}
for(int i = 0; i < n; i++) {
p[i] += (!i ? 0 : p[i-1]);
if(p[i]) {
ans[i] = 'X';
for(int j = 0; j < k-1; j++) {
if(i and i < n-1 and s[i] != 'X' and dp[i-1][j] and dp1[i+1][j+1]) ans[i] = '?';
}
if(i and dp[i-1][k-1] and s[i] != 'X' and !(px[n-1] - px[i])) ans[i] = '?';
if(i < n-1 and dp1[i+1][0] and !(px[i])) ans[i] = '?';
}
}
return ans;
}
