#include "paint.h"
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <string>
using namespace std;
const int maxN = 5000;
const int maxK = 100;
int n, k;
int dp[2][maxN][maxK], pref[2][maxN][maxK];
int whites[maxN], blacks[maxN];
string s;
vector<int> c;
inline int Whites(int l, int r) { return l > r ? 0 : whites[r] - (l ? whites[l - 1] : 0); }
inline int Blacks(int l, int r) { return l > r ? 0 : blacks[r] - (l ? blacks[l - 1] : 0); }
void Init1(int dp[maxN][maxK], int pref[maxN][maxK])
{
for (int i = 0; i < n; ++i)
{
if (i - c[0] + 1 >= 0 && !Whites(i - c[0] + 1, i) && !Blacks(0, i - c[0]))
dp[i][0] = true;
for (int j = 1; j < k; ++j)
if (i - c[j] + 1 >= 0 && !Whites(i - c[j] + 1, i))
if (i - c[j] - 1 >= 0 && pref[i - c[j] - 1][j - 1])
if (i - c[j] < 0 || s[i - c[j]] != 'X')
dp[i][j] = true;
for (int j = 0; j < k; ++j)
pref[i][j] = ((i && s[i] != 'X') ? pref[i - 1][j] : false) | dp[i][j];
}
}
void Init2(int dp[maxN][maxK], int pref[maxN][maxK])
{
for (int i = n - 1; i >= 0; --i)
{
if (i + c[k - 1] - 1 < n && !Whites(i, i + c[k - 1] - 1) && !Blacks(i + c[k - 1], n - 1))
dp[i][k - 1] = true;
for (int j = k - 2; j >= 0; --j)
if (i + c[j] - 1 < n && !Whites(i, i + c[j] - 1))
if (i + c[j] + 1 < n && pref[i + c[j] + 1][j + 1])
if (i + c[j] >= n || s[i + c[j]] != 'X')
dp[i][j] = true;
for (int j = 0; j < k; ++j)
pref[i][j] = ((i + 1 < n && s[i] != 'X') ? pref[i + 1][j] : false) | dp[i][j];
}
}
string solve_puzzle(string s_, vector<int> c_) {
s = s_;
c = c_;
n = s.length(); k = c.size();
for (int i = 0; i < n; ++i)
whites[i] = (i ? whites[i - 1] : 0) + (s[i] == '_'),
blacks[i] = (i ? blacks[i - 1] : 0) + (s[i] == 'X');
Init1(dp[0], pref[0]);
Init2(dp[1], pref[1]);
/*for (int i = 0; i < n; ++i)
for (int j = 0; j < k; ++j)
cerr << "dp[0][" << i << "][" << j << "] = " << dp[0][i][j] << '\n';
for (int i = 0; i < n; ++i)
for (int j = 0; j < k; ++j)
cerr << "dp[1][" << i << "][" << j << "] = " << dp[1][i][j] << '\n';*/
vector<int> can_(n), canX(n);
for (int i = 0; i < n; ++i)
for (int j = 0; j < k; ++j)
{
bool poss = true;
if (j)
{
if (i - 2 < 0 || !pref[0][i - 2][j - 1]) poss = false;
}
else if (Blacks(0, i - 1))
poss = false;
if (j + 1 < k)
{
if (i + c[j] + 1 >= n || !pref[1][i + c[j] + 1][j + 1]) poss = false;
}
else if (Blacks(i + c[j], n - 1))
poss = false;
if (i + c[j] - 1 >= n || Whites(i, i + c[j] - 1))
poss = false;
if (i && s[i - 1] == 'X') poss = false;
if (i + c[j] < n && s[i + c[j]] == 'X') poss = false;
if (poss)
{
++canX[i];
if (i + c[j] < n) --canX[i + c[j]];
}
}
for (int i = 1; i < n; ++i)
canX[i] += canX[i - 1];
for (int i = 0; i < n; ++i)
{
if (i + 1 < n && pref[1][i + 1][0] && !Blacks(0, i))
{
can_[i] = true;
continue;
}
for (int j = 0; j + 1 < k; ++j)
if (i && s[i] != 'X' && pref[0][i - 1][j] && i + 1 < n && pref[1][i + 1][j + 1])
{
can_[i] = true;
break;
}
if (i && pref[0][i - 1][k - 1] && !Blacks(i, n - 1))
can_[i] = true;
}
string res(n, '?');
for (int i = 0; i < n; ++i)
if ((bool)can_[i] ^ (bool)canX[i])
res[i] = (canX[i] ? 'X' : '_');
return res;
}
