#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
const int maxn = 2e5+10;
int soma[2][maxn], pref[110];
bool can[2][maxn][110];
int black[maxn], white[maxn];
int get(int l, int r, int q)
{
return soma[q][r] - soma[q][l-1];
}
string solve_puzzle(string s, vector<int> c)
{
int n = (int) s.size(), k = (int) c.size();
for (int i = 1; i <= n; i++)
{
soma[0][i] = soma[0][i-1] + (s[i-1] == '_');
soma[1][i] = soma[1][i-1] + (s[i-1] == 'X');
}
for (int i = 1; i <= k; i++)
pref[i] = pref[i-1] + c[i-1];
for (int j = 0; j <= k; j++)
{
can[0][0][0] = 1;
for (int i = 1; i <= n; i++)
{
if (s[i-1] != 'X') can[0][i][j] = can[0][i-1][j];
if (j > 0 && i-c[j-1] >= 0 && get(i-c[j-1]+1, i, 0) == 0 && get(1, i, 1) <= pref[j] && get(i+1, n, 1) <= pref[k]-pref[j])
can[0][i][j] |= can[0][max(i-c[j-1]-1, 0)][j-1];
}
}
for (int j = k+1; j >= 1; j--)
{
can[1][n+1][k+1] = 1;
for (int i = n; i >= 1; i--)
{
if (s[i-1] != 'X') can[1][i][j] = can[1][i+1][j];
if (j <= k && i+c[j-1] <= n+1 && get(i, i+c[j-1]-1, 0) == 0 && get(1, i-1, 1) <= pref[j-1] && get(i, n, 1) <= pref[k]-pref[j-1])
can[1][i][j] |= can[1][min(n, i+c[j-1]+1)][j+1];
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= k; j++)
{
if (s[i-1] == '.' && can[0][i-1][j] && can[1][i+1][j+1])
white[i] = 1;
if (j > 0 && i+c[j-1]-1 <= n && get(i, i+c[j-1]-1, 0) == 0 && can[0][max(0, i-2)][j-1] && can[1][min(n+1, i+c[j-1]+1)][j+1])
black[i]++, black[i+c[j-1]]--;
}
}
for (int i = 1; i <= n; i++)
black[i] += black[i-1];
string ans;
for (int i = 1; i <= n; i++)
{
if (s[i-1] == 'X') ans += 'X';
else if (s[i-1] == '_') ans += '_';
else if (white[i] && !black[i]) ans += '_';
else if (!white[i] && black[i]) ans += 'X';
else ans += '?';
}
return ans;
}
