#include<bits/stdc++.h>
#include "paint.h"
#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k)) & 1)
#define any STRANGE
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 2e5 + 10, maxk = 110, mod = 1e9 + 7, inf = 1e9 + 10;
bool dp[2][maxk][maxn], slf[2][maxk][maxn];
int sm[maxn];
bool any(int l, int r){
return sm[r] - sm[l-1] > 0;
}
void solve(string &s, vector<int> &c, bool dp[maxk][maxn], bool slf[maxk][maxn]){
dp[0][0] = 1;
for(int i = 0; i <= sz(c); i++){
for(int j = 1; j <= sz(s); j++){
dp[i][j] = 0;
slf[i][j] = 0;
if(s[j-1] != 'X')
dp[i][j]|= dp[i][j-1];
if(i > 0 && s[j-1] != '_'){
if(j > c[i-1])
slf[i][j]|= !any(j-c[i-1]+1, j) && s[j-1-c[i-1]] != 'X' && dp[i-1][j-c[i-1]-1];
if(j == c[i-1])
slf[i][j]|= !any(1, j) && i == 1;
dp[i][j]|= slf[i][j];
}
}
}
}
bool part[maxk][maxn], part2[maxk][maxn];
string solve_puzzle(string s, vector<int> c){
for(int i = 1; i <= sz(s); i++){
sm[i] = sm[i-1] + (s[i-1] == '_');
}
solve(s, c, dp[0], slf[0]);
reverse(s.begin(), s.end());
reverse(c.begin(), c.end());
solve(s, c, dp[1], slf[1]);
reverse(s.begin(), s.end());
reverse(c.begin(), c.end());
for(int i = 1; i <= sz(s); i++){
if(s[i-1] == 'X')
continue;
for(int j = 0; j <= sz(c); j++)
part[j][i] = dp[0][j][i-1] && dp[1][sz(c)-j][sz(s)-i];
}
part2[sz(c)][sz(s) + 1] = slf[0][sz(c)][sz(s)];
for(int i = 1; i <= sz(s); i++){
if(s[i-1] == 'X')
continue;
for(int j = 0; j <= sz(c); j++)
part2[j][i] = slf[0][j][i-1] && dp[1][sz(c)-j][sz(s)-i];
}
string ans = s;
for(int i = 0; i < sz(s); i++){
if(s[i] == '.'){
bool A = 0, B = 0;
for(int j = 0; j < sz(c); j++){
for(int w = i+2; w <= i+1+c[j] && w <= sz(s) + 1; w++)
A|= part2[j + 1][w];
}
for(int j = 0; j <= sz(c); j++){
B|= part[j][i+1];
}
if(A && B)
ans[i] = '?';
else if(A)
ans[i] = 'X';
else if(B)
ans[i] = '_';
else
assert(0);
}
}
return ans;
}
