#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);
}
vector<vector<int>> 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;
}
string solve_puzzle(string s, vector<int> c) {
int n = sz(s), k = sz(c);
vector<vector<int>> pref_dp = calc(s, c);
reverse(all(s)), reverse(all(c));
vector<vector<int>> suf_dp = calc(s, c);
reverse(all(s)), reverse(all(c));
vector<int> white(n + 5, 0), black(n + 5, 0);
for(int i = 0; i < n; ++i) {
white[i + 1] = white[i] + (s[i] == '_');
black[i + 1] = black[i] + (s[i] == 'X');
}
white[n + 1] += white[n];
white[n + 2] += white[n + 1];
black[n + 1] += black[n];
black[n + 2] += black[n + 1];
vector<bool> can_white(n + 5, false);
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= k; ++j) {
if(j == k && i == n) {
if(pref_dp[i - 1][j] && s[i - 1] != 'X') can_white[i] = true;
continue;
}
if(i == n) continue;
if(pref_dp[i - 1][j] && suf_dp[n - i][k - j] && s[i - 1] != 'X') can_white[i] = true;
}
}
vector<int> can_black(n + 5, 0);
for(int i = 1; i <= n; ++i) {
for(int j = 0; j < k; ++j) {
if(i + c[j] - 1 > n) continue;
if(query(i - 1, i - 1, black) || query(i + c[j], i + c[j], black)) continue;
if(query(i, i + c[j] - 1, white)) continue;
int p = i - 1 - (j != 0);
if(p < 0) continue;
if(j == k - 1) {
if(n - i - c[j] + 1 < 0 || n - i - c[j] + 1 > n) continue;
if(pref_dp[p][j] && suf_dp[n - i - c[j] + 1][k - j - 1]) {
++can_black[i];
--can_black[i + c[j]];
}
continue;
}
if(n - i - c[j] < 0) continue;
if(pref_dp[p][j] && suf_dp[n - i - c[j]][k - j - 1]) {
++can_black[i];
--can_black[i + c[j]];
}
}
}
for(int i = 1; i <= n; ++i) {
can_black[i] += can_black[i - 1];
}
string ans = "";
for(int i = 1; i <= n; ++i) {
if(s[i - 1] == '_') {
ans += '_';
} else if(s[i - 1] == 'X') {
ans += 'X';
} else {
if(can_black[i] && can_white[i]) {
ans += '?';
} else if(can_black[i]) {
ans += 'X';
} else ans += '_';
}
}
return ans;
}
