#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;
int query(int l, int r, vector<int>& p) {
assert(l >= 0 && r >= 0 && l < sz(p) && r < sz(p));
assert(l <= r);
return p[r] - (l ? p[l - 1]: 0);
}
bool calc(string s, vector<int> c) {
int n = sz(s), k = sz(c);
vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
vector<int> black(n + 1, 0), white(n + 1, 0);
dp[0][0] = 1;
for(int i = 0; i < n; ++i) {
black[i + 1] = black[i] + (s[i] == 'X');
white[i + 1] = white[i] + (s[i] == '_');
if(!black[i + 1]) dp[i + 1][0] = 1;
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= k; ++j) {
if(s[i - 1] == 'X' || s[i - 1] == '.') {
int p = i - c[j - 1];
if(p - (j != 1) < 0 || query(p + 1, i, white) || query(p, p, black)) {
//Purice Chad
} else dp[i][j] |= dp[p - (j != 1)][j - 1];
}
if(s[i - 1] == '_' || s[i - 1] == '.') {
dp[i][j] |= dp[i - 1][j];
}
}
}
return dp[n][k];
}
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 = calc(s, c);
s[i] = '_';
bool ok2 = calc(s, c);
assert(ok1 || ok2);
if(ok1 && ok2) {
ans += '?';
} else if(ok1) {
ans += 'X';
} else {
ans += '_';
}
s[i] = '.';
}
}
return ans;
}
