#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
string solve_puzzle(string s, vector<int> c) {
int n = sz(s) , m = sz(c);
int ans[2][n+1] = {0};
memset(ans , 0 , sizeof(ans));
int pre[n+1] = {0};
pre[0] = 0;
for(int i = 0;i<n;i++){
pre[i+1] = pre[i] + (s[i] == '_');
}
auto getsum = [&](int ql , int qr){// 0 indexed
return pre[qr+1] - pre[ql];
};
bool dp[n+1][m+1] , vis[n+1][m+1];
memset(dp , 0 , sizeof(dp));
memset(vis , 0 , sizeof(vis));
vis[0][0] = 1;
for(int i = 0;i<n;i++){
for(int j = 0;j<=m;j++){
// alma
if(s[i] != 'X'){
vis[i+1][j] |= vis[i][j];
}
// al
if(j < m and i + c[j] - 1 < n and getsum(i , i + c[j] - 1) == 0){
if((i + c[j] - 1) == n-1){
vis[i + c[j]][j+1] |= vis[i][j];
}
else if((i + c[j] - 1) < n-1 and s[i + c[j]] != 'X'){
vis[i + c[j] + 1][j+1] |= vis[i][j];
}
}
// cout << i << " " << j << " : " << vis[i][j] << endl;
}
}
dp[n][m] = vis[n][m];
for(int i = n-1;i>=0;i--){
for(int j = 0;j<=m;j++){
if(vis[i][j] == 0)continue;
// alma
if(s[i] != 'X' and dp[i+1][j]){
dp[i][j] = 1;
ans[0][i] = 1;
// cout << "flag 0 : " << i << " " << j << endl;
}
// al
if(j < m and i + c[j] - 1 < n and getsum(i , i + c[j] - 1) == 0){
if((i + c[j] - 1) == n-1 and dp[i + c[j]][j+1]){
dp[i][j] = 1;
ans[1][i]++;
ans[1][i + c[j]]--;
// cout << "flag 1 : " << i << " " << j << endl;
}
else if((i + c[j] - 1) < n-1 and s[i + c[j]] != 'X' and dp[i + c[j] + 1][j+1]){
dp[i][j] = 1;
ans[1][i]++;
ans[1][i + c[j]]--;
ans[0][i + c[j]] = 1;
// cout << "flag 2 : " << i << " " << j << endl;
}
}
}
}
for(int i = 1;i<n;i++){
ans[1][i] += ans[1][i-1];
}
string ret = s;
for(int i = 0;i<n;i++){
if(s[i] != '.')ret[i] = s[i];
else {
if(ans[0][i] and ans[1][i])ret[i] = '?';
if(!ans[0][i] and ans[1][i])ret[i] = 'X';
if(ans[0][i] and !ans[1][i])ret[i] = '_';
}
}
return ret;
}
