#include "paint.h"
using namespace std;
bool dp[4][200005][105];
bool dp2[200005][105];
int last2[200005][105];
int last[2][200005];
inline bool query(int l, int r, bool x)
{
return r < last[x][l] ? false : true;
}
inline bool query2(int l, int r, int j)
{
return last2[l][j] <= r ? true : false;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
int N = s.size();
int K = c.size();
int cur[2] = {N, N};
for (int i = N - 1; i >= 0; i--) {
if (s[i] == '_') cur[0] = i;
if (s[i] == 'X') cur[1] = i;
last[0][i] = cur[0], last[1][i] = cur[1];
}
for (int i = 0; i < N; i++) {
if (s[i] == 'X') break;
dp[1][i][0] = true;
}
if (s[0] != '_' && c[0] == 1) dp[0][0][1] = true;
for (int i = 1; i < N; i++) {
if (s[i] != 'X') {
for (int j = 1; j <= K; j++) {
dp[1][i][j] = dp[1][i-1][j] | dp[0][i-1][j];
}
}
for (int j = 1; j <= K; j++) {
if (i >= c[j-1] - 1 && !query(i - c[j-1] + 1, i, 0)) {
if (i == c[j-1] - 1) dp[0][i][j] = j == 1 ? true : false;
else dp[0][i][j] = dp[1][i-c[j-1]][j-1];
}
}
}
for (int i = N - 1; i >= 0; i--) {
if (s[i] == 'X') break;
dp[3][i][K+1] = true;
}
if (s[N-1] != '_' && c[K-1] == 1) dp[2][N-1][K] = true;
for (int i = N - 2; i >= 0; i--) {
if (s[i] != 'X') {
for (int j = 1; j <= K; j++) {
dp[3][i][j] = dp[2][i+1][j] | dp[3][i+1][j];
}
}
for (int j = 1; j <= K; j++) {
if (i + c[j-1] - 1 < N && !query(i, i + c[j-1] - 1, 0)) {
if (i + c[j-1] == N) dp[2][i][j] = j == K ? true : false;
else dp[2][i][j] = dp[3][i+c[j-1]][j+1];
}
}
}
string ans = "";
for (int j = 1; j <= K; j++) {
for (int i = 0; i < N; i++) {
if (i + c[j-1] - 1 >= N) break;
dp2[i][j] = dp[0][i+c[j-1]-1][j] & dp[2][i][j];
}
}
for (int j = 1; j <= K; j++) {
int cur = N;
for (int i = N - 1; i >= 0; i--) {
if (dp2[i][j]) cur = i;
last2[i][j] = cur;
}
}
for (int i = 0; i < N; i++) {
if (s[i] == 'X') {
ans += 'X';
continue;
}
if (s[i] == '_') {
ans += '_';
continue;
}
bool ok[2] = {};
for (int j = 0; j <= K; j++) {
ok[0] |= dp[1][i][j] & dp[3][i][j+1];
}
for (int j = 1; j <= K; j++) {
ok[1] |= query2(max(0, i - c[j-1] + 1), i, j);
}
if (ok[0] ^ ok[1]) {
ans += ok[0] ? '_' : 'X';
}
else ans += '?';
}
return ans;
}
