/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
typedef long long ll;
const int N_MAX = 200000;
const int K_MAX = 100;
int cntB[N_MAX + 2];
int cntW[N_MAX + 2];
int cntSeg (int vec[], int l, int r)
{
return vec[r] - vec[l - 1];
}
bool pref[N_MAX + 2][K_MAX + 2];
bool suff[N_MAX + 2][K_MAX + 2];
bool prefOr[N_MAX + 2][K_MAX + 2];
bool suffOr[N_MAX + 2][K_MAX + 2];
bool block[N_MAX + 2][K_MAX + 2];
int cntBlock[N_MAX + 2][K_MAX + 2];
bool B[N_MAX + 2];
bool W[N_MAX + 2];
string solve_puzzle (string s, vector <int> c)
{
int N = (int) s.size();
int K = (int) c.size();
for(int i = 1; i <= N; i++)
{
cntB[i] = cntB[i - 1] + (s[i - 1] == 'X');
cntW[i] = cntW[i - 1] + (s[i - 1] == '_');
}
pref[0][0] = true;
prefOr[0][0] = true;
for(int i = 1; i <= N; i++)
for(int j = 0; j <= K; j++)
{
pref[i][j] = false;
if(1 <= j)
{
int len = c[j - 1];
if(i - len + 1 >= 1
&& cntSeg(cntW, i - len + 1, i) == 0
&& (i - len == 0 || s[(i - len) - 1] != 'X'))
pref[i][j] |= prefOr[max(0, i - len - 1)][j - 1];
}
prefOr[i][j] = pref[i][j];
if(s[i - 1] != 'X')
prefOr[i][j] |= prefOr[i - 1][j];
}
suff[N + 1][K + 1] = true;
suffOr[N + 1][K + 1] = true;
for(int i = N; i >= 1; i--)
for(int j = K + 1; j >= 1; j--)
{
suff[i][j] = false;
if(j <= K)
{
int len = c[j - 1];
if(i + len - 1 <= N
&& cntSeg(cntW, i, i + len - 1) == 0
&& (i + len == N + 1 || s[(i + len) - 1] != 'X'))
suff[i][j] |= suffOr[min(N + 1, i + len + 1)][j + 1];
}
suffOr[i][j] = suff[i][j];
if(s[i - 1] != 'X')
suffOr[i][j] |= suffOr[i + 1][j];
}
for(int i = 1; i <= N; i++)
for(int j = 1; j <= K; j++)
{
if(i == N)
block[i][j] = (pref[i][j] & (j == K));
else if(s[(i + 1) - 1] != 'X')
block[i][j] = (pref[i][j] & suffOr[i + 2][j + 1]);
cntBlock[i][j] = cntBlock[i - 1][j] + block[i][j];
}
for(int i = 1; i <= N; i++)
{
if(s[i - 1] == '_')
{
W[i] = true;
continue;
}
if(s[i - 1] == 'X')
{
W[i] = false;
continue;
}
for(int j = 0; j <= K; j++)
W[i] |= (prefOr[i - 1][j] & suffOr[i + 1][j + 1]);
}
for(int i = 1; i <= N; i++)
{
if(s[i - 1] == 'X')
{
B[i] = true;
continue;
}
if(s[i - 1] == '_')
{
B[i] = false;
continue;
}
for(int j = 1; j <= K; j++)
B[i] |= (cntBlock[min(N, i + c[j - 1] - 1)][j] - cntBlock[i - 1][j] > 0);
}
string answer;
for(int i = 1; i <= N; i++)
{
if(W[i] == true && B[i] == true)
answer += '?';
else if(W[i] == true)
answer += '_';
else
answer += 'X';
}
return answer;
}
