#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)(v.size())
const int maxn=2e5+10;
const int maxk=110;
int dpl[maxn][maxk], dpr[maxn][maxk], sp[maxn], v[maxn], tam[maxk], white[maxn], black[maxn];
int sum(int l, int r){
if(l>r) swap(l,r);
return sp[r]-sp[l-1];
}
void calc(int n, int k){
memset(dpl,0,sizeof(dpl)); memset(dpl,0,sizeof(dpr));
dpl[0][0]=1; // no 0 pego 0 caras
for(int i=0;i<n;i++){
for(int j=0;j<=k;j++){ // ja coloquei j caras
if(!v[i+1]) dpl[i+1][j]|=dpl[i][j]; // posso deixar branco
if(j!=k&&i+tam[j+1]<=n&&sum(i+1,i+tam[j+1])==0&&v[i+tam[j+1]+1]==0) dpl[i+tam[j+1]+1][j+1]|=dpl[i][j];
}
}
dpr[n+1][k+1]=1;
for(int i=n+1;i>1;i--){
for(int j=k+1;j>=1;j--){
if(!v[i-1]) dpr[i-1][j]|=dpr[i][j];
if(j!=1&&i-tam[j-1]>=1&&sum(i-tam[j-1],i-1)==0&&v[i-tam[j-1]-1]==0) dpr[i-tam[j-1]-1][j-1]|=dpr[i][j];
}
}
}
string solve_puzzle(string s, vector<int> c){
int n=s.size(), k=c.size();
s='a'+s; // 1 indexed
for(int i=1;i<=k;i++) tam[i]=c[i-1];
for(int i=1;i<=n;i++){
sp[i]=sp[i-1];
if(s[i]=='X') v[i]=1;
if(s[i]=='_') sp[i]++;
}
calc(n,k);
memset(white,0,sizeof(white)); memset(black,0,sizeof(black));
for(int i=1;i<=n;i++){
for(int j=1;j<=k+1;j++) if(dpl[i][j-1]&&dpr[i][j]) white[i]++; // checando se pode ser branco
}
for(int j=1;j<=k;j++){
for(int i=1;i+tam[j]-1<=n;i++){
// vou brutar se o j-esimo intervalo estiver em [i,i+tam[j]-1], ainda eh possivel completar o resto?
if(sum(i,i+tam[j]-1)==0&&dpl[i-1][j-1]&&dpr[i+tam[j]][j+1]) black[i]++, black[i+tam[j]]--;
}
}
string ret="";
int sum=0;
for(int i=1;i<=n;i++){
sum+=black[i];
if(s[i]!='.') ret.push_back(s[i]);
else{
if(sum&&white[i]) ret.push_back('?');
else if(sum) ret.push_back('X');
else ret.push_back('_');
}
}
return ret;
}
