#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;
bitset<MAX_K> dp[MAX_N];
bitset<MAX_K> dpr[MAX_N];
int n, k;
int next_bad[MAX_N];
bool Check(string &s, vi &c, int start) {
for (int i = start; i < n; i++) {
dp[i].reset();
}
int ex = 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' && i) {
dp[i] = dp[i - 1];
}
if (s[i] == '_') continue;
for (int j = 0, sum = -1; j < k; j++) {
sum += c[j] + 1;
if (dp[i][j]) continue;
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];
}
bitset<MAX_N> check_;
std::string solve_puzzle(std::string s, std::vector<int> c) {
n = s.size();
k = c.size();
string ans(n, '?');
int ex = 0;
next_bad[0] = s[0] == 'X' ? 0 : -1;
for (int i = 0; i < n; i++) {
next_bad[i] = next_bad[i + 1];
if (s[i] == 'X') ex = i;
else if (s[i] == '_') next_bad[i] = i;
}
dpr[n][k] = true;
for (int i = n - 1; i >= 0; i--) {
if (s[i] != 'X') {
dpr[i] = dpr[i + 1];
}
if (s[i] == '_') continue;
for (int j = k - 1, sum = -1; j >= 0; j--) {
sum += c[j] + 1;
if (dpr[i][j]) continue;
if (sum > n - i) break;
bool b = next_bad[i + c[j] - 1] < i;
if (b && j == k) {
dpr[i][j] = ex < i + c[j];
} else if (b && (i + c[j] >= n || s[i + c[j]] != 'X') && (i + c[j] + 1 >= n || dpr[i + c[j] + 1][j + 1])) {
dpr[i][j] = true;
}
}
}
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 = 0; i < n; i++) {
if (s[i] != 'X' && i) {
dp[i] = dp[i - 1];
}
if (s[i] == '_') continue;
for (int j = 0, sum = -1; j < k; j++) {
sum += c[j] + 1;
if (dp[i][j]) continue;
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;
}
}
}
if (dpr[1][0]) check_[0] = true;
for (int i = 1; i < n; i++) {
for (int j = 0; j < k; j++) {
if (dp[i - 1][j] && dpr[i + 1][j + 1]) {
check_[i] = true;
break;
}
}
if (dpr[i + 1][0] && ex > i) check_[i] = true;
}
for (int i = 0; i < n; i++) {
if (s[i] != '.') ans[i] = s[i];
else {
s[i] = 'X';
bool b2 = Check(s, c, 0);
s[i] = '.';
if (check_[i] && !b2) ans[i] = s[i] = '_';
else if (!check_[i] && b2) {
ans[i] = s[i] = 'X';
chkmin(ex, i);
}
}
for (int j = n - 1; j >= 0; j--) {
next_bad[j] = next_bad[j + 1];
if (s[j] == 'X') ex = j;
else if (s[j] == '_') next_bad[j] = j;
}
dp[i].reset();
if (s[i] != 'X' && i) {
dp[i] = dp[i - 1];
}
if (s[i] == '_') continue;
for (int j = 0, sum = -1; j < k; j++) {
sum += c[j] + 1;
if (dp[i][j]) continue;
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;
}
