#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
#include "paint.h"
vector<vector<bool>> solve(string s, vi c) {
int N = s.size();
int K = c.size();
vi pfs1(N + 1, 0); // X's in prefix
vi pfs2(N + 1, 0); // _'s in prefix
for (int i = 1; i <= N; i++) {
pfs1[i] = pfs1[i - 1];
pfs2[i] = pfs2[i - 1];
if (s[i - 1] == 'X')
pfs1[i]++;
if (s[i - 1] == '_')
pfs2[i]++;
}
vector<vector<bool>> dp(N + 1, vector<bool>(K + 1, false));
// dp[i][j]: up to i (exclusive), do first j clues
dp[0][0] = true;
for (int i = 1; i <= N; i++) { // at s[i - 1]
// cout<<"at "<<i<<endl;
if (s[i - 1] != '_') { // try filled
dp[i][0] = (dp[i][0] || 0); // can't have nothing
for (int j = 1; j <= K; j++) {
// cout<<"j: "<<j<<endl;
// check if can add (j-1)st clue
if (j == 1) { // no need _ to left
int lb = i - c[j - 1]; // left index, all X
int ub = i - 1; // right index, all X
if ((lb >= 0) && (pfs1[lb] - pfs1[0] == 0) && (pfs2[ub + 1] - pfs2[lb] == 0))
dp[i][j] = (dp[i][j] || 1);
}
else {
int lb = i - c[j - 1]; // left index, all X
int ub = i - 1; // right index, all X
if (lb >= 1 && pfs2[ub + 1] - pfs2[lb] == 0 && s[lb - 1] != 'X')
dp[i][j] = (dp[i][j] || dp[i - c[j - 1] - 1][j - 1]);
}
}
}
if (s[i - 1] != 'X') { // try empty
for (int j = 0; j <= K; j++) {
dp[i][j] = (dp[i][j] || dp[i - 1][j]);
}
}
}
return dp;
}
string solve_puzzle(string s, vi c) {
int N = s.size();
int K = c.size();
for (int i = 0; i < N; i++) {
if (s[i] == '.')
s[i] = '?';
}
// try all combinations of _ and X
// check if each works
vector<vector<bool>> dp1 = solve(s, c);
/* cout<<"dp1: "<<endl;
for (int i = 0; i <= N; i++) {
cout<<i<<": ";
for (int j = 0; j <= K; j++) {
cout<<dp1[i][j]<<" ";
}
cout<<endl;
}*/
// calculate reverse dp
string s2 = s;
reverse(s2.begin(), s2.end());
vi c2 = c;
reverse(c2.begin(), c2.end());
vector<vector<bool>> dp2 = solve(s2, c2);
reverse(dp2.begin(), dp2.end());
/* cout<<"dp2: "<<endl;
for (int i = 0; i <= N; i++) {
cout<<i<<": ";
for (int j = 0; j <= K; j++) {
cout<<dp2[i][j]<<" ";
}
cout<<endl;
}*/
// dp2[i][j]: on s[i, N - 1], true if last j can be done
// check if can be blank
vector<bool> can1(N, false);
// can1[i] is true if s[i] can be '_'
for (int i = 0; i < N; i++) { // try splitting at i
for (int j = 0; j <= K; j++) { // this many to the left
if (s[i] != 'X' && dp1[i][j] && dp2[i + 1][K - j])
can1[i] = true;
}
}
/* cout<<"can1: ";
for (bool b : can1)
cout<<b<<" ";
cout<<endl;*/
vi pfs1(N + 1, 0); // X's in prefix
vi pfs2(N + 1, 0); // _'s in prefix
for (int i = 1; i <= N; i++) {
pfs1[i] = pfs1[i - 1];
pfs2[i] = pfs2[i - 1];
if (s[i - 1] == 'X')
pfs1[i]++;
if (s[i - 1] == '_')
pfs2[i]++;
}
// check if can be filled
vector<bool> can2(N, false);
for (int i = 0; i < K; i++) { // considering clue i
// cout<<"at "<<i<<endl;
for (int j = 0; j < N - c[i] + 1; j++) { // clue starts at j
// clue on [j, j + c[i] - 1]
// immediate left and right must possibly be '_'
bool works = true;
if (j > 0 && s[j - 1] == 'X')
works = false;
if ((j + c[i] - 1) < N - 1 && s[j + c[i]] == 'X')
works = false;
// all within clue must possibly be 'X'
if (pfs2[j + c[i]] - pfs2[j] != 0)
works = false;
if (!works)
continue;
// check for other clues to left and right
// check for left possible
bool canleft = false;
if ((j == 0 && i == 0))
canleft = true;
else if (j >= 1 && s[j - 1] != 'X' && dp1[j - 1][i])
canleft = true;
bool canright = false;
if ((j + c[i] - 1 == N - 1 && i == K - 1))
canright = true;
else if (j + c[i] - 1 < N - 1 && s[j + c[i]] != 'X' && dp2[j + c[i] + 1][K - 1 - i])
canright = true;
if (canleft && canright) { // actually works
// cout<<"works "<<i<<" "<<j<<endl;
for (int k = j; k <= j + c[i] - 1; k++) {
can2[k] = true;
}
}
}
}
/* cout<<"can2: ";
for (bool b : can2)
cout<<b<<" ";
cout<<endl;*/
string ans = "";
for (int i = 0; i < N; i++) {
if (can1[i] && can2[i]) // both
ans += '?';
else if (can1[i]) // only empty
ans += '_';
else if (can2[i]) // only filled
ans += 'X';
}
return ans;
}
