#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int n, k;
string s;
vector<int> c;
vector<vector<bool>> calc(){
vector<vector<bool>> dp(n+1, vector<bool>(k+1, false));
dp[0][0] = true;
for(int i = 0; i < n; i++){
if(s[i] == 'X') break;
dp[i+1][0] = true;
}
int last_ = -1;
for(int i = 0; i < n; i++){
if(s[i] == '_') last_ = i;
for(int j = 0; j < k; j++){
int start = i+1-c[j];
if(start > last_){
if(start > 0) dp[i+1][j+1] = dp[start-1][j] && s[start-1] != 'X';
else if(j == 0) dp[i+1][j+1] = true;
}
if(s[i] != 'X') dp[i+1][j+1] = dp[i+1][j+1] || dp[i][j+1];
}
}
return dp;
}
string solve_puzzle(string S, vector<int> C){
s = S;
c = C;
n = (int)S.size();
k = (int)C.size();
auto dp1 = calc();
reverse(s.begin(), s.end());
reverse(c.begin(), c.end());
auto dp2 = calc();
reverse(s.begin(), s.end());
reverse(c.begin(), c.end());
string ans(n, ' ');
vector<bool> w(n), b(n);
for(int h = 0; h <= k; h++){
vector<bool> is_valid(n);
if(h > 0){
int under = 0;
for(int i = 0; i < c[h-1]; i++){
if(s[i] == '_') under++;
}
for(int i = 0; i+c[h-1]-1 < n; i++){
if(under == 0){
bool le = (i == 0 && h == 1) || (i > 0 && s[i-1] != 'X' && dp1[i-1][h-1]);
bool ri = (i == n-c[h-1] && h == k) || (i < n-c[h-1] && s[i+c[h-1]-1] != 'X' && dp2[n-1-i-c[h-1]][k-h]);
is_valid[i] = le && ri;
}
if(i+c[h-1] < n && s[i+c[h-1]] == '_') under++;
if(s[i] == '_') under--;
}
}
int valid = 0;
for(int i = 0; i < n; i++){
valid += is_valid[i];
if(h > 0 && i >= c[h-1]) valid -= is_valid[i-c[h-1]];
if(s[i] == '.'){
if(dp1[i][h] && dp2[n-i-1][k-h]) w[i] = true;
if(h > 0 && valid > 0) b[i] = true;
}
}
}
for(int i = 0; i < n; i++){
if(s[i] != '.') ans[i] = s[i];
else{
if(w[i] && b[i]) ans[i] = '?';
else ans[i] = w[i]?'_':'X';
}
}
return ans;
}
