#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
//#define int long long
template <class _T>
bool chmin(_T &x, const _T &y){
bool flag = false;
if ( x > y ){
x = y; flag |= true;
}
return flag;
}
template <class _T>
bool chmax(_T &x, const _T &y){
bool flag = false;
if ( x < y ){
x = y; flag |= true;
}
return flag;
}
string solve_puzzle(string s, vector<int> c) {
int n = (int)s.size(), m = (int)c.size();
if ( n <= 100 ){
auto ok = [&](string s){
vector <vector<int>> dp(n + 1, vector <int> (m + 1));
dp[0][0] = true;
vector <int> pf(n + 1);
for ( int i = 0; i < n; i++ ){
pf[i + 1] = pf[i] + (s[i] == '_');
}
auto get = [&](int l, int r){
return pf[r] - pf[l - 1];
};
s = '#' + s;
for ( int i = 1; i <= n; i++ ){
for ( int j = 0; j <= m; j++ ){
if ( s[i] != 'X' ){
dp[i][j] |= dp[i - 1][j];
}
if ( !j ) continue;
int k = i - c[j - 1];
if ( k >= 0 && !get(k + 1, i) ){
if ( !k and j <= 1 ){
dp[i][j] = true;
} else if ( k and s[k] != 'X' ){
dp[i][j] |= dp[k - 1][j - 1];
}
}
}
}
return dp[n][m];
};
string ans = s;
for ( int i = 0; i < n; i++ ){
if ( s[i] != '.' ){
continue;
}
for ( auto j: {'_', 'X'} ){
s[i] = j;
if ( ok(s) ){
if ( ans[i] != '.' ){
ans[i] = '?';
} else ans[i] = j;
}
}
s[i] = '.';
}
return ans;
}
bool dp[n + 2][m + 1], dp2[n + 2][m + 1];
for ( int i = 0; i <= n + 1; i++ ){
for ( int j = 0; j <= m; j++ ){
dp[i][j] = dp2[i][j] = false;
}
}
vector <int> pf(n + 1);
for ( int i = 0; i < n; i++ ){
pf[i + 1] = pf[i] + (s[i] == '_');
}
auto get = [&](int l, int r){
return pf[r] - pf[l - 1];
};
s = '#' + s + '#';
dp[0][0] = true;
for ( int i = 1; i <= n; i++ ){
dp[i][0] = true;
for ( int j = 1; j <= m; j++ ){
if ( s[j] != 'X' ){
dp[i][j] |= dp[i - 1][j];
}
int k = i - c[j - 1];
if ( k >= 0 and !get(k + 1, i) ){
if ( s[k] == 'X' ){
continue;
}
dp[i][j] |= dp[max(0, k - 1)][j - 1];
}
}
}
dp2[n + 1][0] = true;
for ( int i = n; i > 0; i-- ){
dp2[i][0] = true;
for ( int j = 1; j <= m; j++ ){
if ( s[j] != 'X' ){
dp2[i][j] |= dp2[i + 1][j];
}
int k = i + c[m - j];
if ( k <= n + 1 and !get(i, k - 1) ){
if ( s[k] == 'X' ){
continue;
}
dp2[i][j] |= dp2[min(n + 1, k + 1)][j - 1];
}
}
}
vector <int> w(n + 2), b(n + 2);
for ( int i = 1; i <= n; i++ ){
if ( s[i] == 'X' ){
continue;
}
for ( int j = 0; j <= m; j++ ){
if ( dp[i - 1][j] && dp2[i + 1][m - j] ){
w[i] = true;
}
}
}
for ( int j = 1; j <= m; j++ ){
int t = c[j - 1];
for ( int i = 1; i + t <= n + 1; i++ ){
if ( get(i, i + t - 1) ){
continue;
}
if ( s[i - 1] == 'X' or s[i + t] == 'X' ){
continue;
}
if ( dp[max(0, i - 2)][j - 1] & dp2[min(n + 1, i + t + 1)][m - j] ){
b[i]++; b[i + t]--;
}
}
}
for ( int i = 1; i <= n; i++ ){
b[i] += b[i - 1];
}
string ans;
for ( int i = 1; i <= n; i++ ){
if ( b[i] && w[i] ){
ans += '?';
} else if ( b[i] ){
ans += 'X';
} else ans += '_';
}
return ans;
}
