#include "paint.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
// #define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 200'000;
const int MAXK = 100;
int dp[MAXK + 10][MAXN + 10];
int last_white[MAXN + 10];
int last_black[MAXN + 10];
int owo[MAXN + 10];
int tag[MAXN + 10]; // 0 = no, 1 = white, 2 = black, 1|2 = both
string solve_puzzle(string s, vector<int32_t> c) {
s = '_' + s;
int n = sz(s);
int k = sz(c);
memset(dp , 0, sizeof(dp ));
memset(tag, 0, sizeof(tag));
// build table for next/previous white/black cells
last_white[0] = last_black[0] = 0;
For(i, 1, n) {
if(s[i - 1] == 'X') last_black[i] = i;
else last_black[i] = last_black[i - 1];
if(s[i - 1] == '_') last_white[i] = i;
else last_white[i] = last_white[i - 1];
}
// walk from beginning
For(i, 0, n) {
if(i && last_black[i] == i) break;
dp[0][i] = 1;
}
For(j, 1, k) {
int len = c[j - 1];
For(i, 1, n) {
if(i >= len &&
i - last_white[i] >= len &&
last_black[i - len] != i - len &&
dp[j - 1][i - len - 1]) {
dp[j][i] |= 2;
}
if(last_black[i] != i &&
dp[j][i - 1]) {
dp[j][i] |= 1;
}
}
}
// restore transitions
dp[k][n] |= 4;
Forr(j, k, 0) {
int len = j ? c[j - 1] : 0;
Forr(i, n, 2) if(dp[j][i] & 4) {
if(dp[j][i] & 2) {
dp[j - 1][i - len - 1] |= 4;
owo[i - len + 1] = max(owo[i - len + 1], len);
tag[i - len] |= 1;
}
if(dp[j][i] & 1) {
dp[j][i - 1] |= 4;
tag[i] |= 1;
}
}
}
int now = 0;
For(i, 1, n) {
now = max(now - 1, owo[i]);
if(now) tag[i] |= 2;
}
string ans;
For(i, 2, n) {
if(tag[i] == 3) ans.push_back('?');
if(tag[i] == 2) ans.push_back('X');
if(tag[i] == 1) ans.push_back('_');
}
return ans;
}
