#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n, k;
int pref_[N], prefX[N];
bool fin[105][N];
int canX[N], can_[N];
int st[105][N];
int state[105][N];
char arr[N];
int sz[N];
string solve_puzzle(string s, vector<int> C) {
memset(state, -1, sizeof state);
n = s.size(), k = C.size();
for(int i = 0; i < n; ++i) arr[i+2] = s[i];
for(int i = 0; i < k; ++i) sz[i+1] = C[i];
for(int i = 2; i <= n+1; ++i) pref_[i] = pref_[i-1] + (arr[i] == '_' ? 1 : 0);
for(int i = 2; i <= n+1; ++i) prefX[i] = prefX[i-1] + (arr[i] == 'X' ? 1 : 0);
pref_[n+2] = pref_[n+1], prefX[n+2] = prefX[n+1];
state[0][0] = true;
for(int i = 1; i <= k; ++i) {
int lst = -1;
for(int j = sz[i]+1; j <= n+1; ++j) {
if(state[i-1][j-sz[i]-1] != -1) lst = j-sz[i]-1;
if(lst != -1 && (prefX[j-sz[i]] - prefX[lst] == 0) && (pref_[j] - pref_[j-sz[i]] == 0)
&& (prefX[(i == k ? n : j) + 1] - prefX[j] == 0)) state[i][j] = lst;
}
}
for(int i = k; i >= 1; --i) {
for(int j = n+1; j > 1; --j) {
if(i == k) st[i][j] = n+1;
if(st[i][j] == 0) st[i][j] = st[i][j+1];
if(state[i][j] != -1 && prefX[st[i][j]] - prefX[j] == 0 && st[i][j]) {
canX[j-sz[i]+1]++, canX[j+1]--;
can_[j+1]++, can_[st[i][j]+1]--;
can_[state[i][j]+1]++, can_[j-sz[i]+1]--;
st[i-1][state[i][j]] = j - sz[i];
}
}
}
for(int j = 2; j <= n+1; ++j) canX[j] += canX[j-1], can_[j] += can_[j-1];
string str;
for(int j = 2; j <= n+1; ++j) {
if(canX[j] && can_[j]) str.push_back('?');
else if(canX[j]) str.push_back('X');
else str.push_back('_');
}
return str;
}
