#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#include <cstdlib>
const int N = 2e5 + 5, K = 105;
int dp[N][K], dp2[N][K], ok[N];
std::string solve_puzzle(std::string s, std::vector<int> c) {
int n = s.size();
s = '1' + s + '1';
int m = c.size();
int prev = 0;
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
if (s[i] == '_') {
prev = i;
for (int j = 0; j <= m; j++) dp[i][j] = dp[i - 1][j];
continue;
}
if (s[i] == '.')
for (int j = 0; j <= m; j++) dp[i][j] = dp[i - 1][j];
for (int j = 1; j <= m; j++) {
if (c[j - 1] <= i && prev <= i - c[j - 1] && s[i - c[j - 1]] != 'X') {
dp[i][j] |= dp[max(0, i - c[j - 1] - 1)][j - 1];
}
}
}
prev = n + 1;
dp2[n + 1][m + 1] = 1;
for (int i = n; i >= 1; i--) {
if (s[i] == '_') {
prev = i;
for (int j = 1; j <= m + 1; j++) dp2[i][j] = dp2[i + 1][j];
continue;
}
if (s[i] == '.')
for (int j = 1; j <= m + 1; j++) dp2[i][j] = dp2[i + 1][j];
for (int j = 1; j <= m; j++) {
if (c[j - 1] + i - 1 <= n && prev > c[j - 1] + i - 1 && s[i + c[j - 1]] != 'X') {
dp2[i][j] |= dp2[min(n + 1, i + c[j - 1] + 1)][j + 1];
if ((dp2[min(n + 1, i + c[j - 1] + 1)][j + 1] && dp[max(0, i - 2)][j - 1] && s[i - 1] != 'X')) {
ok[i]++; ok[i + c[j - 1]]--;
}
}
}
}
string ans = "";
for (int i = 1; i <= n; i++) {
ok[i] += ok[i - 1];
if (s[i] == 'X') ans += 'X';
else if (s[i] == '_') ans += '_';
else {
if (!ok[i]) ans += '_';
else {
int f = 0;
for (int j = 0; j <= m; j++) {
f |= dp[i - 1][j] & dp2[i + 1][j + 1];
}
if (!f) ans += 'X';
else ans += '?';
}
}
}
return ans;
}
