#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;
}
