//#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<bool>> DP[105];
int C[105];
bool D[105][105];
int k;
int N;
bool pos(string s) {
int i, j;
for(i=0;i<=N;i++) {
for(j=0;j<=k;j++) D[i][j] = false;
}
for(i=0;i<N;i++) {
for(j=0;j<k;j++) {
for(int m = 0; m < C[j];m++) DP[i][j][m] = false;
}
}
//cout << s << ' ' << "init\n";
for(i=0;i<=N;i++) {
for(j=0;j<k;j++) {
//cout << i << "th : " << j << '\n';
if(i!=N) {
for(int m = 0; m < C[j]; m++) {
if(m==0) {
if(!j||(i&&D[i-1][j-1])) {
if(s[i]!='_') {
DP[i][j][m] = true;
}
}
}
else {
if(i&&DP[i-1][j][m-1]&&(s[i]!='_')) {
DP[i][j][m] = true;
}
}
//cout << DP[i][j][m] <<' ';
}
//cout << '\n';
}
//cout << "init3\n";
if(i&&(DP[i-1][j][C[j]-1])&&(i==N||s[i]!='X')) {
//cout << "connected on " << i << ' ' << j << '\n';
D[i][j] = true;
//cout << D[i][j] << '\n';
}
if(i&&(i==N||s[i]!='X')&&D[i-1][j]) D[i][j] = true;
//cout << "init4\n";
}
}
/*for(i=0;i<=N;i++) {
for(j=0;j<k;j++) cout << D[i][j];
cout << '\n';
}
cout << D[N][k-1] << '\n';*/
return D[N][k-1];
}
string solve_puzzle(string s, vector<int> _C) {
k = _C.size();
N = s.length();
int i, j;
for(i=0;i<k;i++) C[i] = _C[i];
N = s.length();
for(i=0;i<N;i++) {
DP[i].resize(k);
for(j=0;j<k;j++) {
DP[i][j].resize(C[j]);
}
}
string s2;
s2.resize(N);
string ans;
ans.resize(N);
//.cout << "init\n";
for(i=0;i<N;i++) {
if(s[i]!='.') {
ans[i] = s[i];
continue;
}
for(j=0;j<N;j++) s2[j] = s[j];
s2[i] = 'X';
bool p1 = pos(s2);
s2[i] = '_';
bool p2 = pos(s2);
//cout << i << ' ' << p1 << ' ' << p2 << '\n';
if(p1&&p2) ans[i] = '?';
else if(p1) ans[i] = 'X';
else ans[i] = '_';
}
return ans;
}
