#include "paint.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())
vi black_count, white_count;
// string s;
bool psbl_black(int a, int b)
{
return white_count[b] - white_count[a-1] == 0;
}
bool psbl_white(int a, int b)
{
return black_count[b] - black_count[a-1] == 0;
}
string solve_puzzle(string s, vi c_)
{
// cerr << "called\n";
int N = sz(s);
int K = sz(c_);
s = "z" + s + "z";
vi c{0};
for(int x: c_) c.push_back(x);
black_count = vi(1+N, 0);
white_count = vi(1+N, 0);
for(int i = 1; i <= N; i++)
{
black_count[i] = black_count[i-1];
white_count[i] = white_count[i-1];
if(s[i] == 'X') black_count[i]++;
else if(s[i] == '_') white_count[i]++;
}
// cerr << "A\n";
vvi dp(1+N, vi(1+K, 0));
dp[0][0] = 1;
//dp[0][j >= 1] == 0
for(int i = 1; i <= N; i++)
{
dp[i][0] = dp[i-1][0] && psbl_white(i, i);
for(int j = 1; j <= K; j++)
{
dp[i][j] = dp[i-1][j] && psbl_white(i, i);
if(i - c[j] >= 1)
dp[i][j] |= psbl_black(i - c[j] + 1, i) && psbl_white(i - c[j], i - c[j]) && dp[i - c[j] - 1][j-1];
else if(i - c[j] == 0)
dp[i][j] |= psbl_black(1, i) && (j == 1);
}
}
// cerr << "B\n";
vvi rev_dp(1+N+1, vi(1+K+1, 0));
rev_dp[N+1][K+1] = 1;
for(int i = N; i >= 1; i--)
{
rev_dp[i][K+1] = rev_dp[i+1][K+1] && psbl_white(i, i);
for(int j = K; j >= 1; j--)
{
rev_dp[i][j] = rev_dp[i+1][j] && psbl_white(i, i);
if(i + c[j] <= N)
rev_dp[i][j] |= psbl_black(i, i + c[j] - 1) && psbl_white(i + c[j], i + c[j]) && rev_dp[i + c[j] + 1][j+1];
else if(i + c[j] == N+1)
rev_dp[i][j] |= psbl_black(i, N) && (j == K);
}
}
// cerr << "C\n";
vi can_black(1+N, 0);
vi can_white(1+N, 0);
for(int i = 1; i <= N; i++)
{
for(int j = 0; j <= K; j++)
{
// cerr << i << ' ' << j << '\n';
can_white[i] |= dp[i-1][j] && rev_dp[i+1][j+1] && psbl_white(i, i);
}
}
// cerr << "D\n";
vi black_delta(1+N+1, 0);
for(int j = 1; j <= K; j++)
{
for(int i = 1; i + c[j] - 1 <= N; i++)
{
// cerr << j << ' ' << i << '\n';
if((i-2 == -1 && j == 1) || (i-2 >= 0 && dp[i-2][j-1]))
{
// cerr << "A\n";
if(s[i-1] != 'X')
{
// cerr << "B\n";
// cerr << int(i + c[j] - 1 + 2 == N+2 && j == K) << '\n';
// cerr << i + c[j] - 1 + 2 << '\n';
if((i + c[j] - 1 + 2 == N+2 && j == K) || (i + c[j] - 1 + 2 <= N+1 && rev_dp[i + c[j] - 1 + 2][j+1]))
{
// cerr << "C\n";
if(s[i + c[j] - 1 + 1] != 'X')
{
if(psbl_black(i, i + c[j] - 1))
{
black_delta[i]++;
black_delta[i+c[j]]--;
}
}
}
}
}
}
}
// cerr << "E\n";
int cr = 0;
for(int i = 1; i <= N; i++)
{
cr += black_delta[i];
can_black[i] = (cr >= 1) && (s[i] != '_');
}
string res;
for(int i = 1; i <= N; i++)
{
char c;
if(can_black[i] && can_white[i]) c = '?';
else if(can_black[i]) c = 'X';
else if(can_white[i]) c = '_';
res.push_back(c);
}
return res;
}
