#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
#define SZ(x) int((x).size())
#define all(x) (x).begin() , (x).end()
#define sep ' '
const int MAXN = 2e5 + 10;
const int MAXK = 110;
int n , k , dp[2][MAXK][MAXN] , mark[MAXN] , valid[MAXN];
void solve(int n , int k , string s , vector<int> c , int ind){
if(ind == 1){
reverse(all(s));
reverse(all(c));
}
dp[ind][0][0] = 1;
for(int i = 0 ; i <= k ; i++){
int l = 0;
for(int j = 1 ; j < n ; j++){
if(s[j] == '_') l = j;
if(s[j] == '_' || s[j] == '.'){
dp[ind][i][j] |= dp[ind][i][j - 1];
}
if((s[j] == 'X' || s[j] == '.') && i >= 1 && j - l >= c[i - 1]){
// cout << ind << sep << i << sep << j << sep << endl;
if(s[j - c[i - 1]] == 'X') continue;
dp[ind][i][j] |= dp[ind][i - 1][j - c[i - 1] - 1];
}
}
}
if(ind == 1){
for(int i = 0 ; i <= k ; i++){
reverse(dp[ind][i] , dp[ind][i] + n);
}
}
}
string solve_puzzle(string s, vector<int> c) {
s = "__" + s + "__"; n = SZ(s); k = SZ(c);
solve(n , k , s , c , 0);
solve(n , k , s , c , 1);
/* cout << n << endl;
for(int i = 0 ; i <= k ; i++){
for(int j = 0 ; j < n ; j++){
cout << dp[0][i][j] << sep;
}
cout << endl;
}
for(int i = 0 ; i <= k ; i++){
for(int j = 0 ; j < n ; j++){
cout << dp[1][i][j] << sep;
}
cout << endl;
}*/
for(int i = 0 ; i <= k ; i++){
for(int j = 2 ; j + 2 < n ; j++){
if(s[j] == 'X') continue;
if(dp[0][i][j - 1] && dp[1][k - i][j + 1]){
mark[j] |= 1;
}
}
}
for(int i = 0 ; i < k ; i++){
int l = 1;
fill(valid , valid + MAXN , 0);
for(int j = 2 ; j + 2 < n ; j++){
if(s[j] == '_'){
l = j;
continue;
}
if(j - l < c[i] || s[j + 1] == 'X' || s[j - c[i]] == 'X') continue;
if(dp[0][i][j - c[i] - 1] && dp[1][k - i - 1][j + 2]){
valid[j] = 1;
}
}
int sum = 0;
for(int j = n - 1 ; j >= 0 ; j--){
sum += valid[j];
if(j + c[i] < n) sum -= valid[j + c[i]];
if(sum) mark[j] |= 2;
}
}
for(int i = 0 ; i < n ; i++){
if(s[i] == '.'){
if(mark[i] == 1) s[i] = '_';
if(mark[i] == 2) s[i] = 'X';
if(mark[i] == 3) s[i] = '?';
}
}
return s.substr(2 , n - 4);
}
