#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
int pre[200005];
vector<vector<bool>> happy_lama(string bati, vector<int> c1){
int n = bati.size() - 1;
int m = c1.size() - 1;
vector<vector<bool>> dp(n+1, vector<bool>(m+1, 0));
dp[0][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= m; j++){
int hi = 0;
if(bati[i] != 'X' && dp[i-1][j]){
hi = 1;
}
if(j > 0){
int len = c1[j];
if(i >= len){
int pa = pre[i] - pre[i-len];
if(pa == 0){
if(i == len){
if(dp[0][j-1]) hi = 1;
} else {
if(bati[i-len] != 'X' && dp[i-len-1][j-1]){
hi = 1;
}
}
}
}
}
dp[i][j] = hi;
}
}
return dp;
}
string solve_puzzle(string s, vector<int> c) {
int n0 = s.size();
string bati = "*";
bati += s;
vector<int> c1 = {0};
for(int x : c) c1.push_back(x);
int n = n0;
int m = c.size();
for(int i = 1; i <= n; i++){
pre[i] = pre[i-1] + (bati[i] == '_');
}
auto dp1 = happy_lama(bati, c1);
string rs = s;
reverse(rs.begin(), rs.end());
string bati2 = "*";
bati2 += rs;
vector<int> c2 = {0};
reverse(c.begin(), c.end());
for(int x : c) c2.push_back(x);
memset(pre, 0, sizeof(pre));
for(int i = 1; i <= n; i++){
pre[i] = pre[i-1] + (bati2[i] == '_');
}
auto dp2 = happy_lama(bati2, c2);
vector<bool> canWhite(n+1, 0), canBlack(n+1, 0);
for(int i = 1; i <= n; i++){
if(bati[i] == 'X') continue;
for(int j = 0; j <= m; j++){
if(dp1[i-1][j] && dp2[n-i][m-j]){
canWhite[i] = 1;
}
}
}
for(int j = 1; j <= m; j++){
int len = c1[j];
for(int i = 1; i+len-1 <= n; i++){
int r = i+len-1;
if(pre[r] - pre[i-1] != 0) continue;
if(i > 1 && bati[i-1] == 'X') continue;
if(r < n && bati[r+1] == 'X') continue;
if(dp1[i-1][j-1] && dp2[n-r][m-j]){
for(int t = i; t <= r; t++){
canBlack[t] = 1;
}
}
}
}
string res = "";
for(int i = 1; i <= n; i++){
if(canWhite[i] && canBlack[i]) res += '?';
else if(canWhite[i]) res += '_';
else res += 'X';
}
return res;
}
