#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
const int N = 110, K = 110;
bool d[N][K], w[N][K];
int cb[N], cw[N];
vector<int> c;
bool check(string s) {
int n = s.size();
for (int i = 0; i < n; i++)
for (int j = 0; j < (int)c.size(); j++)
d[i][j] = w[i][j] = 0;
cb[0] = s[0] == 'X', cw[0] = s[0] == '_';
for (int i = 1; i < n; i++)
cb[i] = cb[i - 1] + (s[i] == 'X'), cw[i] = cw[i - 1] + (s[i] == '_');
for (int i = 0; i < n; i++) {
int k0 = i - c[0];
if (k0 >= 0)
d[i][0] = cb[k0] == 0 && cw[i] - cw[k0] == 0;
else if (k0 == -1)
d[i][0] = cw[i] == 0;
for (int j = 1; j < (int)c.size(); j++) {
int k = i - c[j];
if (k >= 0)
d[i][j] = w[k][j - 1] && (cw[i] - cw[k] == 0);
}
if (s[i] == 'X' || i == 0)
continue;
for (int j = 0; j < (int)c.size(); j++)
w[i][j] = w[i - 1][j] || d[i - 1][j];
}
for (int i = 0; i < n; i++)
if (d[i][(int)c.size() - 1] && cb[n - 1] - cb[i] == 0)
return 1;
return 0;
}
string solve_puzzle(std::string s, std::vector<int> _c) {
c = _c;
string ans = s;
for (int i = 0; i < (int)s.size(); i++) {
if (s[i] != '.')
continue;
s[i] = 'X';
bool tx = check(s);
s[i] = '_';
bool t_ = check(s);
s[i] = '.';
assert(tx || t_);
if (tx && t_)
ans[i] = '?';
else if (tx)
ans[i] = 'X';
else
ans[i] = '_';
}
return ans;
}
