#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out() {cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 2e5 + 10;
const int maxk = 100 + 10;
int n, k, part[maxn], trap[maxn];
bool dp[maxn][maxk], pd[maxn][maxk];
string ans;
string solve_puzzle(std::string s, std::vector<int> c) {
n = s.size();
k = c.size();
int lst = 0;
dp[0][0] = true;
for (int i = 1; i <= n; i++){
if (s[i-1] == '_') lst = i;
if (dp[i-1][0] && s[i-1] != 'X') dp[i][0] = true;
for (int j = 1; j <= k; j++){
dp[i][j] = false;
if (s[i-1] != 'X' && dp[i-1][j]) dp[i][j] = true;
if (lst <= i-c[j-1] && (i == c[j-1] || s[i-c[j-1]-1] != 'X')){
bool ok = ((i == c[j-1] && j == 1) || (i > c[j-1] && dp[i-c[j-1]-1][j-1]));
if (ok) dp[i][j] = true;
}
//debug(i, j, dp[i][j]);
}
}
pd[n+1][k+1] = true;
lst = n+1;
for (int i = n; i; i--){
if (s[i-1] == '_') lst = i;
if (pd[i+1][k+1] && s[i-1] != 'X') pd[i][k+1] = true;
for (int j = 1; j <= k; j++){
pd[i][j] = false;
if (s[i-1] != 'X' && pd[i+1][j]) pd[i][j] = true;
if (lst >= i+c[j-1] && (n-i+1 == c[j-1] || s[i+c[j-1]-1] != 'X')){
bool ok = ((n-i+1 == c[j-1] && j == k) || (n-i+1 > c[j-1] && pd[i+c[j-1]+1][j+1]));
if (ok) pd[i][j] = true;
}
//debug(i, j, pd[i][j]);
}
}
lst = 0;
for (int i = 1; i <= n; i++){
if (s[i-1] == '_') lst = i;
for (int j = 1; j <= k; j++){
if (lst > i-c[j-1]) continue;
if ((((i == c[j-1] && j == 1) || (i > c[j-1] && s[i-c[j-1]-1] != 'X' && dp[i-c[j-1]-1][j-1]))) && ((i == n && j == k) || (i < n && s[i] != 'X' && pd[i+2][j+1]))){
part[i-c[j-1]+1]++;
part[i+1]--;
}
}
}
for (int i = 1; i <= n; i++){
if (s[i-1] == 'X') continue;
for (int j = 0; j <= k; j++){
//debug(i, j, dp[i-1][j], pd[i+1][j+1]);
if (dp[i-1][j] && pd[i+1][j+1]){
// debug(i, j);
trap[i]++;
}
}
}
ans = s;
for (int i = 1; i <= n; i++){
part[i] += part[i-1];
if (ans[i-1] != '.') continue;
//debug(part[i], trap[i]);
if (part[i] && trap[i]) ans[i-1] = '?';
else if (part[i]) ans[i-1] = 'X';
else ans[i-1] = '_';
}
return ans;
}
