#include "paint.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mxN = 2e5 + 5;
const int mxK = 105;
bool pdp[mxK][mxN];
bool sdp[mxK][mxN];
int prefX[mxN], pref_[mxN];
string solve_puzzle(string s, vector<int> c) {
int k = c.size();
c.insert(c.begin(), 0);
int n = s.size();
s = '#' + s;
s = s + '#';
for (int i = 1; i <= n; i++) {
prefX[i] = prefX[i - 1] + (s[i] == 'X');
pref_[i] = pref_[i - 1] + (s[i] == '_');
}
pdp[0][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
if (j == 0) {
pdp[j][i] = true;
if (s[i] == 'X') pdp[j][i] = false;
pdp[j][i] &= pdp[j][i - 1];
continue;
}
if (s[i] != 'X') {
pdp[j][i] |= pdp[j][i - 1];
}
if (s[i] != '_') {
if (i - c[j] == 0 && j != 1) continue;
if (i - c[j] == 0) {
if (pref_[i] - pref_[i - c[j]] > 0) continue;
if (s[i + 1] == 'X') continue;
pdp[j][i] = true;
continue;
}
if (i - c[j] < 0 || pref_[i] - pref_[i - c[j]] > 0 || s[i - c[j]] == 'X' || s[i + 1] == 'X') continue;
pdp[j][i] |= pdp[j - 1][i - c[j] - 1];
}
}
}
sdp[k + 1][n + 1] = true;
for (int i = n; i >= 1; i--) {
for (int j = k + 1; j >= 1; j--) {
if (j == k + 1) {
sdp[j][i] = true;
if (s[i] == 'X') sdp[j][i] = false;
sdp[j][i] &= sdp[j][i + 1];
continue;
}
if (s[i] != 'X') {
sdp[j][i] |= sdp[j][i + 1];
}
if (s[i] != '_') {
if (i + c[j] == n + 1 && j != k) continue;
if (i + c[j] == n + 1) {
if (pref_[i + c[j] - 1] - pref_[i - 1] > 0) continue;
if (s[i - 1] == 'X') continue;
sdp[j][i] = true;
continue;
}
if (i + c[j] > n + 1 || pref_[i + c[j] - 1] - pref_[i - 1] > 0 || s[i + c[j]] == 'X' || s[i - 1] == 'X') continue;
sdp[j][i] |= sdp[j + 1][i + c[j] + 1];
}
}
}
bool off[n + 1], on[n + 1];
memset(off, false, sizeof off);
memset(on, false, sizeof on);
for (int i = 1; i <= n; i++) {
if (s[i] != '.') continue;
for (int j = 0; j <= k; j++) {
if (pdp[j][i - 1] && sdp[j + 1][i + 1]) off[i] = true;
}
}
vector<int> add(n + 2);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (i - c[j] == 0 && j != 1) continue;
if (i - c[j] == 0) {
if (pref_[i] - pref_[i - c[j]] > 0) continue;
if (i == n && j != k) continue;
if (i < n && !sdp[j + 1][i + 2]) continue;
if (s[i + 1] == 'X') continue;
add[i]++;
add[i - c[j]]--;
}
if (i - c[j] < 0 || pref_[i] - pref_[i - c[j]] > 0 || s[i - c[j]] == 'X') continue;
if (!pdp[j - 1][i - c[j] - 1]) continue;
if (i == n && j != k) continue;
if (i < n && !sdp[j + 1][i + 2]) continue;
if (s[i + 1] == 'X') continue;
add[i]++;
add[i - c[j]]--;
}
}
for (int i = n; i >= 1; i--) {
add[i] += add[i + 1];
on[i] = add[i];
}
string ret;
for (int i = 1; i <= n; i++) {
if (s[i] == 'X') ret += s[i];
if (s[i] == '_') ret += s[i];
if (s[i] == '.') {
if (off[i] && on[i]) ret += '?';
else if (off[i]) ret += '_';
else ret += 'X';
}
}
return ret;
}
