#include <bits/stdc++.h>
using namespace std;
#include "paint.h"
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
bool P[200005][105], S[200005][105], pos[200005][105];
int lst[105], ptr1[105], ptr2[105], cnt[105];
std::string solve_puzzle(std::string s, std::vector<int> c) {
int n = (int)s.length(), k = (int)c.size();
string ans;
P[0][0] = 1;
S[n+1][k+1] = 1;
for(int i=1;i<=k;i++)ptr1[i] = ptr2[i] = 1;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
if(s[i-1] != 'X')P[i][j] |= P[i-1][j];
bool f = 1;
if(!j || c[j-1] > i - 1)continue;
while(ptr1[j] <= i - 1){
if(s[ptr1[j] - 1] == '_')cnt[j]++;
ptr1[j]++;
}
while(ptr2[j] < i - c[j-1]){
if(s[ptr2[j] - 1] == '_')cnt[j]--;
ptr2[j]++;
}
//for(int a=i-1;a>=i-c[j-1];a--)if(s[a-1] == '_')f = 0;
if(cnt[j])f = 0;
if(s[i-1] == 'X')f = 0;
if(f){
P[i][j] |= P[i - c[j-1] - 1][j - 1];
}
}
}
for(int i=1;i<=k;i++)ptr1[i] = ptr2[i] = n, cnt[i] = 0;
for(int i=n;i>=1;i--){
for(int j=k+1;j>=1;j--){
if(s[i-1] != 'X')S[i][j] |= S[i+1][j];
bool f = 1;
if(j == k + 1 || i + c[j-1] > n)continue;
while(ptr1[j] >= i + 1){
if(s[ptr1[j] - 1] == '_')cnt[j]++;
ptr1[j]--;
}
while(ptr2[j] > i + c[j-1]){
if(s[ptr2[j] - 1] == '_')cnt[j]--;
ptr2[j]--;
}
//for(int a=i+1;a<=i+c[j-1];a++)if(s[a-1] == '_')f = 0;
if(cnt[j])f = 0;
if(s[i-1] == 'X')f = 0;
if(f){
S[i][j] |= S[i + c[j-1] + 1][j + 1];
}
}
}
//cerr << "brozo";
for(int j=1;j<=k;j++){
int in = 1, in2 = in;
int sm = 0;
for(int a=1;a<=n-c[j-1]+1;a++){
bool f2 = 1;
while(in <= a+c[j-1]-1){
if(s[in-1] == '_')sm++;
in++;
}
while(in2 < a){
if(s[in2-1] == '_')sm--;
in2++;
}
if(sm)f2 =0 ;
//for(int b=a;b<=a+c[j-1]-1;b++)if(s[b-1] == '_')f2 = 0;
if(a > 1 && s[a-2] == 'X')f2 = 0;
if(a + c[j-1] - 1 < n && s[a + c[j-1] - 1] == 'X')f2 = 0;
if(!f2)continue;
if(P[a-1][j-1] && S[a + c[j-1]][j+1]){
//cout << i << ' ' << j << ' ' << a << '\n';
pos[a][j] = 1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
if(pos[i][j])lst[j] = i;
}
if(s[i-1] == 'X' || s[i-1] == '_'){
ans += s[i-1];
continue;
}
bool f = 0;
for(int j=0;j<=k;j++)if(P[i][j] && S[i][j+1])f = 1;
bool brub = 0;
for(int j=1;j<=k;j++){
int lb = max(1, i - c[j-1] + 1);
if(lst[j] >= lb)brub = 1;
}
if(brub && f)ans += "?";
else if(f)ans += "_";
else ans += "X";
}
return ans;
}
