#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=105;
string v, respf;
vector<int> qv;
short dp[MAXN][105];
int soma[2][MAXN];
int n, q;
int psum(int ini, int fim, int k) {
if(fim>=n) return MAXN;
return soma[k][fim]- (ini==0 ? 0 : soma[k][ini-1]);
}
short fazdp(int ind, int k) {
if(ind>=n) return k>=q;
if(v[ind]=='X'&&k>=q) return 0;
if(dp[ind][k]!=-1) return dp[ind][k];
// printf("call %d %d\n",ind, k);
dp[ind][k]=0;
int fim=ind+qv[k]-1;
int val=psum(ind, fim, 0);
int val2=psum(ind, fim, 1);
if(val==0&&v[fim+1]!='X') dp[ind][k]|=fazdp(fim+2, k+1);
if(v[ind]!='X') dp[ind][k]|=fazdp(ind+1, k);
// printf("dp %d %d >> %d // %d %d\n", ind, k, dp[ind][k], val, val2);
return dp[ind][k];
}
void recalc() {
soma[0][0]=soma[1][0]=0;
for(int i=0; i<n; i++) {
if(i!=0) soma[0][i]=soma[0][i-1], soma[1][i]=soma[1][i-1];
soma[0][i]+=(v[i]=='_');
soma[1][i]+=(v[i]=='X');
}
memset(dp, -1, sizeof(dp));
fazdp(0, 0);
}
bool testa(int ind, char tipo) {
v[ind]=tipo;
recalc();
v[ind]='.';
return dp[0][0];
}
string solve_puzzle(string s, vector<int> c) {
n=s.size(); v=s; v.push_back('_');
respf=s;
qv=c; q=qv.size();
for(int i=0; i<n; i++) {
if(s[i]!='.') continue;
bool a=testa(i, '_');
bool b=testa(i, 'X');
// printf("%d >> ab %d %d\n\n", i, a, b);
if(a&&b) respf[i]='?';
else if(a) respf[i]='_';
else respf[i]='X';
}
return respf;
}
