#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 10;
int dpL[mxN][100 + 10], dpR[mxN][100 + 10];
string solve_puzzle(string s, vector<int> c) {
int m = c.size();
int n = s.size();
s = ' ' + s;
c.insert(c.begin(), 0);
vector<int> sum(n + 10);
vector<int> d(n + 10, 0);
vector<int> check(n + 10, 0);
for(int i = 1; i <= n; i ++) sum[i] = sum[i - 1] + (s[i] == '_');
auto get = [&](int l, int r) {
return sum[r] - sum[l - 1];
};
dpR[n + 1][m] = 1;
for(int i = n; i >= 1; i --) {
for(int j = 0; j <= m; j ++) {
if(!dpR[i + 1][j]) continue ;
if(s[i] != 'X') dpR[i][j] = 1;
if(j > 0 && i - c[j] > 0 && s[i - c[j]] != 'X' && get(i - c[j] + 1, i) == 0) {
dpR[i - c[j]][j - 1] = 1;
}
}
}
dpL[0][1] = 1;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m + 1; j ++) {
if(!dpL[i - 1][j]) continue ;
if(j <= m && i + c[j] == n + 1 && get(i, n) == 0) {
if(dpR[i + c[j]][j]) {
d[i] ++ ;
d[i + c[j]] -- ;
}
} else
if(j <= m && i + c[j] <= n && s[i + c[j]] != 'X' && get(i, i + c[j] - 1) == 0) {
if(dpR[i + c[j]][j]) {
d[i] ++ ;
d[i + c[j]] -- ;
}
}
if(s[i] != 'X') dpL[i][j] = 1;
if(j <= m && i + c[j] <= n && s[i + c[j]] != 'X' && get(i, i + c[j] - 1) == 0) {
dpL[i + c[j]][j + 1] = 1;
}
}
for(int j = 1; j <= m; j ++) {
if(s[i] == '.') {
check[i] = check[i] || (dpL[i][j] && dpR[i][j - 1])
|| (dpL[i][j + 1] && dpR[i][j]);
}
}
}
string str = "";
for(int i = 1; i <= n; i ++) {
d[i] += d[i - 1];
if(s[i] == '.') {
if(check[i] && d[i]) str += '?'; else
if(check[i]) str += '_'; else
str += 'X';
} else
str += s[i];
}
return str;
}
