#include "paint.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 5005;
const int MAX_K = 105;
bool dp[MAX_N][MAX_K];
int n, k;
int next_bad[MAX_N];
bool Check(string &s, vi &c, int start) {
for (int i = start; i < n; i++) {
for (int j = 0; j < k; j++) {
dp[i][j] = false;
}
}
int ex = n;
next_bad[n] = n;
for (int i = n - 1; i >= 0; i--) {
next_bad[i] = next_bad[i + 1];
if (s[i] == 'X') ex = i;
else if (s[i] == '_') next_bad[i] = i;
}
for (int i = start; i < n; i++) {
if (s[i] != 'X') {
if (i) {
for (int j = 0; j < k; j++) {
dp[i][j] = dp[i - 1][j];
}
}
}
if (s[i] == '_') continue;
for (int j = 0, sum = -1; j < k; j++) {
sum += c[j] + 1;
if (sum > i + 1) break;
bool b = i - c[j] + 1 < 0 || next_bad[i - c[j] + 1] > i;
if (b && !j) {
dp[i][j] |= ex > i - c[j];
} else if (b && (i - c[j] < 0 || s[i - c[j]] != 'X') && (i - c[j] <= 0 || dp[i - c[j] - 1][j - 1])) {
dp[i][j] = true;
}
}
}
return dp[n - 1][k - 1];
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
n = s.size();
k = c.size();
string ans(n, '?');
int ex = n;
for (int i = n - 1; i >= 0; i--) {
if (s[i] == 'X') ex = i;
}
for (int i = 0; i < n; i++) {
if (s[i] != '.') ans[i] = s[i];
else {
s[i] = '_';
bool b1 = Check(s, c, i);
s[i] = 'X';
bool b2 = Check(s, c, i);
s[i] = '.';
if (b1 && !b2) ans[i] = s[i] = '_';
else if (!b1 && b2) ans[i] = s[i] = 'X';
}
if (s[i] != 'X') {
for (int j = 0; j < k; j++) {
dp[i][j] = i ? dp[i - 1][j] : false;
}
}
if (s[i] == '_') continue;
for (int j = 0, sum = -1; j < k; j++) {
sum += c[j] + 1;
if (sum > i + 1) break;
bool b = i - c[j] + 1 < 0 || next_bad[i - c[j] + 1] > i;
if (b && !j) {
dp[i][j] |= ex > i - c[j];
} else if (b && (i - c[j] < 0 || s[i - c[j]] != 'X') && (i - c[j] <= 0 || dp[i - c[j] - 1][j - 1])) {
dp[i][j] = true;
}
}
}
return ans;
}
