#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;
bool dp1[MAXK + 10][MAXN + 10];
bool dp2[MAXK + 10][MAXN + 10];
bool dp[MAXK + 10][MAXN + 10];
int last_white[MAXN + 10];
int last_black[MAXN + 10];
int next_white[MAXN + 10];
int next_black[MAXN + 10];
int tag[MAXN + 10]; // 0 = no, 1 = white, 2 = black, 1|2 = both
string solve_puzzle(string s, vector<int32_t> c) {
int n = sz(s);
int k = sz(c);
memset(dp1, 0, sizeof(dp1));
memset(dp2, 0, sizeof(dp2));
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];
}
next_white[n + 1] = next_black[n + 1] = n + 1;
Forr(i, n, 1) {
if(s[i - 1] == 'X') next_black[i] = i;
else next_black[i] = next_black[i + 1];
if(s[i - 1] == '_') next_white[i] = i;
else next_white[i] = next_white[i + 1];
}
// debug
// For(i, 1, n) cerr << last_black[i] << " \n"[i == n];
// For(i, 1, n) cerr << last_white[i] << " \n"[i == n];
// For(i, 1, n) cerr << next_black[i] << " \n"[i == n];
// For(i, 1, n) cerr << next_white[i] << " \n"[i == n];
// walk from beginning
dp1[0][0] = 1;
For(j, 1, k) {
int len = c[j - 1];
queue<int> que;
if(dp1[j - 1][0]) que.emplace(0);
For(i, 1, n) {
if(dp1[j - 1][i]) que.emplace(i);
if(i == len && j == 1 && last_white[i] == 0) {
dp1[j][i] = 1;
} else if(i > len && i - last_white[i] >= len && last_black[i - len] != i - len) {
while(sz(que) && que.front() < last_black[i - 1 - len]) {
que.pop();
}
if(sz(que) && que.front() < i - len) dp1[j][i] = 1;
}
}
}
// walk from the end
dp2[k + 1][n + 1] = 1;
Forr(j, k, 1) {
int len = c[j - 1];
queue<int> que;
if(dp2[j + 1][n + 1]) que.emplace(n + 1);
Forr(i, n, 1) {
if(dp2[j + 1][i]) que.emplace(i);
if(i == n - len + 1 && j == k && next_white[i] == n + 1) {
dp2[j][i] = 1;
} else if(i < n - len + 1 && next_white[i] - i >= len && next_black[i + len] != i + len) {
while(sz(que) && que.front() > next_black[i + 1 + len]) {
que.pop();
}
if(sz(que) && que.front() > i + len) dp2[j][i] = 1;
}
}
}
// merge results
For(j, 1, k) {
int len = c[j - 1];
bool ok = false;
For(i, len, n) {
dp[j][i] = (dp1[j][i] && dp2[j][i - len + 1]);
ok = ok || dp[j][i];
}
assert(ok);
}
// debug
// For(j, 0, k + 1) {
// For(i, 0, n + 1) {
// if(dp[j][i]) cerr << "*";
// else cerr << ".";
// }
// cerr << "\n";
// }
// can some cells be black?
For(j, 1, k) {
int len = c[j - 1];
queue<int> que;
For(i, len, n) if(dp[j][i]) {
que.emplace(i);
}
For(i, 1, n) {
while(sz(que) && que.front() < i) que.pop();
if(sz(que) && que.front() < i + len) tag[i] |= 2;
}
}
// can some cells be white?
For(j, 0, k) {
int mnl, mxr;
if(j == 0) {
mnl = 0;
} else {
int len = c[j - 1];
mnl = len;
while(!dp[j][mnl]) mnl++;
}
if(j == k) {
mxr = n + 1;
} else {
int len = c[j];
mxr = n;
while(!dp[j + 1][mxr]) mxr--;
mxr = mxr - len + 1;
}
For(i, mnl + 1, mxr - 1) tag[i] |= 1;
}
// report answer
string ans;
For(i, 1, 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;
}
