#include "paint.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int MAXN = 2e5+5;
const int MAXK = 105;
const int INF = 1e9+10;
typedef pair<int,int> pii;
/* idea:
dpP[i][j] = can 's[i]' be black if you only consider the first 'j' segments
ans it is the end of the 'j'th segment
canP[i][j] = can the prefix i indexes be valid if you only consider the first 'j' segments
dpS[i][j] = can 's[i]' be black if you only consider the last 'j, j+1... k' segments
ans it is the start of the 'j'th segment
canP[i][j] = can the idx 'i, i+1,...,n' be valid if you only consider the
'j, j+1, ..., k' segments
to answer:
check if idx 'i' can be black and/or white
*/
int n;
string s, ANS;
int cnt[MAXN];
int dpP[MAXN][MAXK], dpS[MAXN][MAXK], bl[MAXN], wh[MAXN];
bool canP[MAXN][MAXK], canS[MAXN][MAXK];
vector <int> c; int k;
string solve_puzzle(string S, vector<int> C) {
s = '_'+S+'_'; n = s.size()-2;
for(int i=1; i<=n; i++) cnt[i] = cnt[i-1] + (s[i]=='_');
c.pb(-1);
for(auto in : C) c.pb(in);
k = c.size()-1;
dpP[0][0] = 1; canP[0][0] = 1;
for(int i=1; i<=n; i++){
for(int j=1; j<=k; j++){
int len = c[j];
// we want to put the segment on [i-c[j]+1, ..., i]
if(i-c[j]+1 <= 0) continue;
if(cnt[i]-cnt[i-c[j]] != 0) continue; // there is white
if(s[i-c[j]] == 'X') continue; // can't make the segment
if(i-c[j]==0){ // extreme case
if(canP[i-c[j]][j-1])
dpP[i][j] = 1;
} else if(canP[i-c[j]-1][j-1]){ // if j-1 segment is valid
dpP[i][j] = 1;
}
}
// build canP
for(int j=0; j<=k; j++){ // a[i] becomes ending of segment j
if(s[i] != 'X'){ // use last canP and this dpP
canP[i][j] = canP[i-1][j] | dpP[i][j];
} else { // has to be X, so check dpP
canP[i][j] = dpP[i][j];
}
}
}
dpS[n+1][k+1] = 1; canS[n+1][k+1] = 1;
for(int i=n; i>=1; i--){
for(int j=k; j>=1; j--){ // a[i] becomes start of segment j
int len = c[j];
// we want to put segment on [i, ..., i+c[j]-1]
if(i+c[j]-1 > n) continue;
if(cnt[i+c[j]-1]-cnt[i-1] != 0) continue;
if(s[i+c[j]] == 'X') continue; // can't
if(i+c[j]==n+1){ // extreme case
if(canS[i+c[j]][j+1])
dpS[i][j] = 1;
} else if(canS[i+c[j]+1][j+1]){
dpS[i][j] = 1;
}
}
// build canS
for(int j=k+1; j>=1; j--){
if(s[i] != 'X'){
canS[i][j] = canS[i+1][j] | dpS[i][j];
} else {
canS[i][j] = dpS[i][j];
}
}
}
for(int i=1; i<=n-1; i++){
for(int j=1; j<=k; j++){
if(dpP[i][j] && canS[i+2][j+1] && s[i+1] != 'X'){
// if the prefix [1, ..., i] and suffix [i+2, ... , n] is valid
bl[i-c[j]+1]++; bl[i+1]--;
// prefix difference to update quickly
}
}
}
{
int i=n; // extreme case
if(dpP[i][k]){
bl[i-c[k]+1]++; bl[i+1]--;
}
}
for(int i=1; i<=n; i++){
for(int j=0; j<=k; j++){
if(canP[i-1][j] && canS[i+1][j+1]){
// if [1, ..., i-1] and [i+1, ..., n] can put all segments
wh[i] = 1;
}
}
}
for(int i=1; i<=n; i++) bl[i] += bl[i-1]; // prefix difference
for(int i=1; i<=n; i++){
if(s[i] != '.'){
ANS += s[i]; continue;
}
if(bl[i] && wh[i]) ANS += '?';
else if(bl[i]) ANS += 'X';
else if(wh[i]) ANS += '_';
else assert(false);
}
return ANS;
}
