#include "paint.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXK = 100 + 10;
const int INF = 1e9;
int n, k;
std::string s;
int lens[MAXK];
bool dp[MAXN][MAXK];
bool bl[MAXN][MAXK];
bool dp2[MAXN][MAXK];
bool bl2[MAXN][MAXK];
int max[MAXN];
int can2[MAXN];
int can[MAXN];
bool f(int pos, int curr)
{
if (pos >= n)
{
return (curr == k);
}
if (bl[pos][curr])
{
return dp[pos][curr];
}
bl[pos][curr] = true;
dp[pos][curr] = false;
if (s[pos] != '_' && curr < k && can[pos] >= lens[curr] && (pos + lens[curr] == n || s[pos + lens[curr]] != 'X'))
{
dp[pos][curr] |= f(pos + lens[curr] + 1, curr + 1);
}
if (s[pos] != 'X')
{
dp[pos][curr] |= f(pos + 1, curr);
}
return dp[pos][curr];
}
bool hasX[MAXN];
bool f2(int pos, int curr)
{
if (pos < 0)
{
return (curr == -1);
}
if (curr == -1)
{
return !hasX[pos];
}
if (bl2[pos][curr])
{
return dp2[pos][curr];
}
bl2[pos][curr] = true;
dp2[pos][curr] = false;
if (s[pos] != '_' && curr < k && can2[pos] >= lens[curr] && (pos - lens[curr] == -1 || s[pos - lens[curr]] != 'X'))
{
dp2[pos][curr] |= f2(pos - lens[curr] - 1, curr - 1);
}
if (s[pos] != 'X')
{
dp2[pos][curr] |= f2(pos - 1, curr);
}
return dp2[pos][curr];
}
bool canBeBlack[MAXN];
bool canBeWhite[MAXN];
std::string solve_puzzle(std::string S, std::vector <int> c)
{
s = S;
n = s.size();
k = c.size();
for (int i = 0 ; i < k ; ++i)
{
lens[i] = c[i];
}
for (int i = 0 ; i < n ; ++i)
{
hasX[i] = ((i != 0 && hasX[i - 1]) || s[i] == 'X');
if (s[i] == '_') can2[i] = 0;
else if (i == 0) can2[i] = 1;
else can2[i] = can2[i - 1] + 1;
}
for (int i = n - 1 ; i >= 0 ; --i)
{
if (s[i] == '_') can[i] = 0;
else can[i] = can[i + 1] + 1;
}
for (int i = 0 ; i < n ; ++i)
{
if (s[i] == 'X') continue;
for (int j = 0 ; j <= k ; ++j)
{
if (f2(i - 1, j - 1) && f(i + 1, j))
{
canBeWhite[i] = true;
}
}
}
for (int i = 0 ; i < n ; ++i)
{
if (s[i] == '_' || (i > 0 && s[i - 1] == 'X')) continue;
for (int j = 0 ; j < k ; ++j)
{
if (f2(i - 2, j - 1) && can[i] >= lens[j] && i + lens[j] <= n && (i + lens[j] == n || s[i + lens[j]] != 'X') && f(i + lens[j] + 1, j + 1))
{
max[i] = std::max(max[i], lens[j]);
}
}
}
int left = 0;
for (int i = 0 ; i < n ; ++i)
{
left = std::max(left - 1, max[i]);
if (left > 0) canBeBlack[i] = true;
}
std::string ans;
ans.resize(n);
for (int i = 0 ; i < n ; ++i)
{
if (canBeBlack[i] && canBeWhite[i]) ans[i] = '?';
else if (canBeBlack[i]) ans[i] = 'X';
else if (canBeWhite[i]) ans[i] = '_';
else assert(false);
}
return ans;
}
