#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int mxN = 2e5 + 10;
bool dp[2][mxN][102][2]; // dp[pre/suf][pos][kth segment][X/_]
int checkps[mxN];
int cross[mxN];
string solve_puzzle(string s, vector<int> c) {
int n = s.length();
s = '!' + s + '!';
int k = c.size();
c.insert(c.begin(), -1);
checkps[0] = 0;
for (int i = 1; i <= n; i++) {
checkps[i] = checkps[i - 1] + (s[i] == '_');
}
dp[0][0][0][0] = dp[0][0][0][1] = 1;
// sweep forward
for (int i = 1; i <= n; i++) {
dp[0][i][0][0] = 0; dp[0][i][0][1] = (dp[0][i - 1][0][1] && (s[i] != 'X'));
for (int j = 1; j <= k; j++) {
int prev = i - c[j];
if (prev < 0 || checkps[i] - checkps[prev] != 0) {
dp[0][i][j][0] = 0;
} else {
dp[0][i][j][0] = dp[0][prev][j - 1][1];
}
dp[0][i][j][1] = ((dp[0][i - 1][j][0] | dp[0][i - 1][j][1]) && (s[i] != 'X'));
}
}
// sweep backward
dp[1][n + 1][k + 1][0] = dp[1][n + 1][k + 1][1] = 1;
for (int i = n; i >= 1; i--) {
dp[1][i][k + 1][0] = 0; dp[1][i][k + 1][1] = (dp[1][i + 1][k + 1][1] && (s[i] != 'X'));
for (int j = k; j >= 1; j--) {
int prev = i + c[j];
if (prev > n + 1 || checkps[prev - 1] - checkps[i - 1] != 0) {
dp[1][i][j][0] = 0;
} else {
dp[1][i][j][0] = dp[1][prev][j + 1][1];
}
dp[1][i][j][1] = ((dp[1][i + 1][j][0] | dp[1][i + 1][j][1]) && (s[i] != 'X'));
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (i + c[j] - 1 > n) continue;
if (!dp[0][i - 1][j - 1][1] || !dp[1][i + c[j]][j + 1][1]) continue;
if (checkps[i + c[j] - 1] - checkps[i - 1] != 0) continue;
// [i, i + c[j]) can be 'X'
cross[i]++; cross[i + c[j]]--;
}
}
string ans = s;
for (int i = 1; i <= n; i++) {
int msk = 0;
// check for 'X'
cross[i] += cross[i - 1];
if (cross[i] > 0) msk |= 1;
// check for '_'
for (int j = 0; j <= k; j++) {
if (dp[0][i][j][1] && dp[1][i][j + 1][1]) {
msk |= 2;
break;
}
}
if (ans[i] != '.') continue;
if (msk == 0) throw runtime_error("invalid solution?");
if (msk == 1) ans[i] = 'X';
if (msk == 2) ans[i] = '_';
if (msk == 3) ans[i] = '?';
}
ans.erase(ans.begin());
ans.erase(--ans.end());
return ans;
}
