#include "paint.h"
#include "bits/stdc++.h"
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(),a.end()
using ll = long long;
using namespace std;
const int N = 505, K = 105;
map<int, int> dp[N][K], sufdp[N][K];
bool compute_pref(string s, vector<int> c) {
for(int i = 0; i < N; ++i) for(int j = 0; j < K; ++j) dp[i][j].clear();
s += '_';
dp[0][0][0] = 1;
c.pb(0);
int n = s.size(), k = c.size();
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= k; ++j) {
for(int cur = 0; cur <= c[j]; ++cur) {
char x = s[i - 1];
if(x == 'X' || x == '.') {
if(cur >= 1) {
dp[i][j][cur] |= dp[i - 1][j][cur - 1];
}
}
if(x == '_' || x == '.') {
if(cur == 0) {
if(j) dp[i][j][cur] |= dp[i - 1][j - 1][c[j - 1]];
dp[i][j][cur] |= dp[i - 1][j][cur];
}
}
}
}
}
return dp[n][k - 1][0];
}
bool compute_suf(string s, vector<int> c) {
for(int i = 0; i < N; ++i) for(int j = 0; j < K; ++j) sufdp[i][j].clear();
s = "_" + s;
c.insert(c.begin(), 0);
int n = s.size(), k = c.size();
sufdp[n][k - 1][0] = 1;
for(int i = n - 1; i >= 0; --i) {
for(int j = 0; j < k; ++j) {
for(int cur = 0; cur <= c[j]; ++cur) {
char x = s[i];
if(x == 'X' || x == '.') {
if(cur) {
sufdp[i][j][cur] |= sufdp[i + 1][j][cur - 1];
}
}
if(x == '_' || x == '.') {
if(cur == 0) {
if(j + 1 < k) sufdp[i][j][cur] |= sufdp[i + 1][j + 1][c[j + 1]];
sufdp[i][j][cur] |= sufdp[i + 1][j][cur];
}
}
}
}
}
return sufdp[0][0][0];
}
string solve_puzzle(string s, vector<int> c) {
string ans = "";
int n = sz(s);
for(int i = 0; i < n; ++i) {
if(s[i] == 'X') {
ans += 'X';
} else if(s[i] == '_') {
ans += '_';
} else {
s[i] = 'X';
bool ok1 = compute_suf(s, c);
s[i] = '_';
bool ok2 = compute_suf(s, c);
assert(ok1 || ok2);
if(ok1 && ok2) {
ans += '?';
} else if(ok1) {
ans += 'X';
} else {
ans += '_';
}
s[i] = '.';
}
}
return ans;
}
