/// Prosta
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int N, K;
vector<int> sum[2];
int getsum(int id, int st, int dr)
{
if(st > dr) return 0;
if(st < 0) return 0;
if(st == 0) return sum[id][dr];
return sum[id][dr] - sum[id][st - 1];
}
void makesum(string s)
{
sum[0].resize(N);
sum[1].resize(N);
for(int i = 0; i < N; i++)
{
if(i > 0)
{
sum[0][i] = sum[0][i - 1];
sum[1][i] = sum[1][i - 1];
}
if(s[i] == '_') sum[0][i]++;
if(s[i] == 'X') sum[1][i]++;
}
}
void solve(string s, vector<int> c, vector< vector<int> > &can)
{
makesum(s);
can.resize(N);
auto getcan = [&](int x, int y)
{
if(y >= 0 && x >= 0) return can[x][y];
if(y == 0)return 1;
if(y > 0) return 0;
return 0;
};
for(int i = 0; i < N; i++)
{
can[i].resize(K + 1);
can[i][0] = getsum(1, 0, i) == 0;
for(int j = 1; j <= K; j++)
{
int l = c[j - 1];
can[i][j] = 0;
if(s[i] == '_')
can[i][j] |= (i > 0 ? can[i - 1][j] : 0);
else if(s[i] == 'X')
can[i][j] |= ( (i >= l - 1 && getsum(0, i - l + 1, i) == 0 && getsum(1, i - l, i - l) == 0) ? getcan(i - l - 1, j - 1) : 0);
else
{
can[i][j] |= (i > 0 ? can[i - 1][j] : 0);
can[i][j] |= ( (i >= l - 1 && getsum(0, i - l + 1, i) == 0 && getsum(1, i - l, i - l) == 0) ? getcan(i - l - 1, j - 1) : 0);
}
}
}
}
string solve_puzzle(string s, vector<int> c)
{
N = s.size(), K = c.size();
vector< vector<int> > pfx, sfx;
solve(s, c, pfx);
reverse(begin(s), end(s));
reverse(begin(c), end(c));
solve(s, c, sfx);
reverse(begin(s), end(s));
reverse(begin(c), end(c));
makesum(s);
string sol = "";
vector<int> blk(N + 2), wht(N + 2);
for(int i = 0; i < N; i++)
{
bool white = false;
for(int j = 0; j <= K; j++)
{
bool left = false;
if(i == 0) left = (j == 0 ? 1 : 0);
else left = pfx[i - 1][j];
bool right = false;
if(i == N - 1) right = (j == K ? 1 : 0);
else right = sfx[N - i - 2][K - j];
if(left && right)
{
white = true;
break;
}
}
wht[i] = white;
for(int j = 0; j < K; j++)
{
if(i + c[j] > N) continue;
bool left = false;
if(i == 0) left = (j == 0 ? 1 : 0);
else if(i == 1) left = (j == 0 ? pfx[i - 1][0] : 0);
else left = (pfx[i - 2][j] & (s[i - 1] != 'X'));
i += c[j] - 1;
j++;
bool right = false;
if(i == N - 1) right = (j == K ? 1 : 0);
else if(i == N - 2) right = (j == K ? sfx[N - i - 2][0] : 0);
else right = (sfx[N - i - 3][K - j] & (s[i + 1] != 'X'));
j--;
i -= c[j] - 1;
if(!left || !right) continue;
if(getsum(0, i, i + c[j] - 1) > 0) continue;
blk[i]++;
blk[i + c[j]]--;
}
}
for(int i = 0; i < N; i++)
{
if(i > 0) blk[i] += blk[i - 1];
if(s[i] != '.')
sol.push_back(s[i]);
else if(wht[i] && blk[i] > 0)
sol.push_back('?');
else if(wht[i])
sol.push_back('_');
else
sol.push_back('X');
}
return sol;
}
