#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
int n, k;
int W[101], B[101];
bool white[101], black[101];
string cur;
void solve(int r, int i, string &s, vector<int> &c)
{
if (i == k)
{
for (int j = 1; j <= n; j++)
if (cur[j] == 'X')
black[j] = true;
else if (cur[j] == '_')
white[j] = true;
return;
}
for (int j = r + 2; j + c[i] - 1 <= n; j++)
if (W[j + c[i] - 1] - W[j - 1] == 0 && (B[j - 1] - B[r] == 0 || (r == -1 && B[j-1] == 0)))
{
for (int m = j; m <= j + c[i] - 1; m++)
cur[m] = 'X';
solve(j + c[i] - 1, i + 1, s, c);
for (int m = j; m <= j + c[i] - 1; m++)
cur[m] = '_';
}
}
string solve_puzzle(string s, vector<int> c)
{
n = s.size(), k = c.size();
s = "#" + s;
W[0] = B[0] = 0;
for (int i = 1; i <= n; i++)
{
W[i] = W[i-1] + (s[i] == '_');
B[i] = B[i-1] + (s[i] == 'X');
}
memset(white, false, sizeof(white));
memset(black, false, sizeof(black));
cur = "#" + string(n, '_');
solve(-1, 0, s, c);
string res = "";
for (int i = 1; i <= n; i++)
{
if (white[i] && black[i])
res += "?";
else if (white[i])
res += "_";
else if (black[i])
res += "X";
else
res += "F";
}
return res;
}
