#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int a[200100];
int pref[200100][2], suf[200100];
int ok[200100][2];
int c[200100];
bool dpref[200100][101], dsuf[200100][101];
string solve_puzzle(string s, vector<int> C) {
int k = C.size();
int n = s.size();
for(int i=0; i<k; i++){
c[i+1] = C[i];
}
for(int i=0; i<n; i++){
if(s[i] == 88) a[i + 1] = 1;
if(s[i] == 95) a[i + 1] = 0;
if(s[i] == 46) a[i + 1] = -1;
}
for(int i=1; i<=n; i++){
pref[i][0] = pref[i-1][0] + (a[i] == 0);
}
for(int i=1; i<=n; i++){
pref[i][1] = pref[i-1][1] + (a[i] == 1);
}
dpref[0][0] = 1;
for(int i=0; i<=n; i++){
for(int j=0; j<=k; j++){
if(!dpref[i][j]) continue;
if(i + 1 <= n and a[i + 1] != 1) dpref[i + 1][j] = 1;
if(j + 1 <= k and i + c[j + 1] + 1 <= n and pref[i + c[j + 1]][0] - pref[i][0] == 0 and a[i + c[j + 1] + 1] != 1) dpref[i + 1 + c[j + 1]][j + 1] = 1;
}
}
dsuf[n+1][k+1] = 1;
for(int i=n+1; i>=1; i--){
for(int j=1; j<=k+1; j++){
if(!dsuf[i][j]) continue;
if(i - 1 >= 1 and a[i - 1] != 1) dsuf[i - 1][j] = 1;
if(j - 1 >= 1 and i - c[j - 1] - 1 >= 1 and pref[i-1][0] - pref[i-c[j-1]-1][0] == 0 and a[i - c[j - 1] - 1] != 1) dsuf[i - 1 - c[j - 1]][j-1] = 1;
}
}
//for(int i=1; i<=n; i++) cout<<dsuf[i][2];
for(int i=1; i<=n; i++){
for(int j=1; j<=k; j++){
int l=max(1, i-c[j]+1);
int r=min(i, n-c[j]+1);
for(int h=l; h<=r; h++){
if(dpref[h-1][j-1] and dsuf[h+c[j]][j+1] and pref[h+c[j]-1][0] - pref[h-1][0] == 0) ok[i][1] = 1;
}
if(dpref[i][j] and dsuf[i][j+1] and a[i] != 1) ok[i][0] = 1;
if(dpref[i][j-1] and dsuf[i][j] and a[i] != 1) ok[i][0] = 1;
}
}
string ans;
for(int i=1; i<=n; i++){
char c;
if(ok[i][1] and ok[i][0]) c = '?';
else if(ok[i][1]) c = 'X';
else c = '_';
ans.pb(c);
}
return ans;
}
