#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
mt19937 _rand(time(NULL));
const int mxn = 5e3 + 3;
#include "paint.h"
#include <cstdlib>
int n;
int k;
bool emp[mxn][mxn];
bool exs[mxn][mxn];
bool dp1[mxn][mxn];
bool dp2[mxn][mxn];
bool DP1[mxn][mxn];
bool DP2[mxn][mxn];
int aux1[mxn];
int aux2[mxn];
std::string solve_puzzle(std::string s, std::vector<int> c){
n = (int)s.size();
k = (int)c.size();
fr(i, 0, n){
fr(j, i, n){
if(s[j] == 'X') break;
emp[i][j] = true;
}
fr(j, i, n){
if(s[j] == '_') break;
exs[i][j] = true;
}
}
fr(i, 0, n){
fr(j, 0, k){
if(i-c[j] + 1 >= 0 && exs[i-c[j]+1][i]){
if(j == 0){
if(i-c[j] < 0 || emp[0][i-c[j]]) dp1[i][j] = true;
}
else{
if(i - c[j] > 0 && s[i-c[j]] != 'X' && DP1[i-c[j]-1][j-1]){
dp1[i][j] = true;
}
}
}
}
fr(j, 0, k){
DP1[i][j] = dp1[i][j];
}
if(s[i] != 'X' && i > 0){
fr(j, 0, k){
DP1[i][j] |= DP1[i-1][j];
}
}
}
for(int i = n-1; i >= 0; i --){
for(int j = k-1; j >= 0; j--){
if(i + c[j] - 1 < n && exs[i][i+c[j]-1]){
if(j == k-1){
if(i+c[j]>= n || emp[i+c[j]][n-1]) dp2[i][j] = true;
}
else{
if(i + c[j] + 1 < n && s[i+c[j]] != 'X' && DP2[i+c[j]+1][j+1]){
dp2[i][j] = true;
}
}
}
}
fr(j, 0, k){
DP2[i][j] = dp2[i][j];
}
if(s[i] != 'X' && i + 1 < n){
fr(j, 0, k){
DP2[i][j] |= DP2[i+1][j];
}
}
}
fr(i, 0, n){
fr(j, 0, k){
bool t1 = dp1[i][j];
bool t2 = true;
if(i + 1 < n) t2 = emp[i+1][n-1];
if(j+1< k){
t2 = false;
if(i + 2 < n && s[i+1] != 'X'){
t2 = DP2[i+2][j+1];
}
}
if(t1 && t2){
aux1[i-c[j]+1] ++;
aux1[i+1] --;
}
}
}
for(int i = n-1; i >= 0; i--){
fr(j, 0, k){
bool t1 = dp2[i][j];
bool t2 = true;
if(i > 0) t2 = emp[0][i-1];
if(j-1>=0){
t2 = false;
if(i-2>=0 && s[i-1] != 'X'){
t2 = DP1[i-2][j-1];
}
}
if(t1 && t2){
aux1[i] ++;
aux1[i+c[j]]--;
}
}
}
fr(i, 0, n){
if(s[i] == 'X') continue;
fr(j, -1, k){
bool lef = emp[0][i];
if(j > -1){
lef = false;
if(i > 0 && DP1[i-1][j]){
lef = true;
}
}
bool rig = emp[i][n-1];
if(j+1<k){
rig = false;
if(i+1<n && DP2[i+1][j+1]){
rig = true;
}
}
if(lef && rig){
aux2[i] ++;
aux2[i+1] --;
break;
}
}
}
string ans = s;
int sum1 = 0;
int sum2 = 0;
fr(i, 0, n){
sum1 += aux1[i];
sum2 += aux2[i];
if(s[i] != '.') continue;
if(sum1 && sum2) ans[i] = '?';
else if(sum1) ans[i] = 'X';
else ans[i] = '_';
}
return ans;
}
/*
int main(){
cout<<solve_puzzle("...........__..........._._._......._.............._.XX.XX.........X.X.XX.X..._..", {2, 6, 8});
}
???????????__???????????_____???????_??????????????_?XX?XX????_____XXXXXXXX______
???????????__???????????_____???????_??????????????_?XX?XX?????????X?XXXXXX??____
*/
