#include <bits/stdc++.h>
using namespace std;
#include "paint.h"
string solve_puzzle(string s,vector<int> A){
int n = s.size(),m = A.size(); ++m;
bitset<102> tmp;
vector<int> B(1);
for (int i(0);i < n;++i) B.emplace_back(B.back()+(s[i]=='_'));
vector<bitset<102>> dpl0(1),dpl1(1); dpl0[0][0] = dpl1[0][0] = 1;
for (int i(0);i < n;++i){
tmp.reset();
if (s[i]!='X'&&dpl1.back()[0]) tmp[0] = 1;
for (int k(0);k < m-1;++k) if (i-A[k]+1-(bool)k>=0&&B[i+1]-B[i-A[k]+1]==0&&(k==0||s[i-A[k]]!='X')) tmp[k+1] = dpl1[i-A[k]+1-(bool)k][k];
dpl0.emplace_back(tmp);
if (s[i]=='X') dpl1.emplace_back(tmp);
else dpl1.emplace_back(dpl1.back()|tmp);
}
vector<bitset<102>> dpr0(1),dpr1(1); dpr0[0][m] = dpr1[0][m] = 1;
for (int i(0);i < n;++i){
tmp.reset();
if (s[n-i-1]!='X'&&dpr1.back()[m]) tmp[m] = 1;
for (int k(0);k < m-1;++k) if (i-A[k]+1-(k!=m-2)>=0&&B[n-i+A[k]-1]-B[n-i-1]==0&&(k==m-2||s[n-i-1+A[k]]!='X')) tmp[k+1] = dpr1[i-A[k]+1-(k!=m-2)][k+2];
dpr0.emplace_back(tmp);
if (s[n-i-1]=='X') dpr1.emplace_back(tmp);
else dpr1.emplace_back(dpr1.back()|tmp);
}
reverse(dpr0.begin(),dpr0.end()),reverse(dpr1.begin(),dpr1.end());
string ans = "._X?";
vector<int> R(n);
for (int i(0);i < n;++i) if (s[i]!='X'){
for (int k(0);k < m;++k) if (dpl1[i][k]&&dpr1[i+1][k+1]) R[i] |= 1;//,(cout<<i<<' '<<k<<endl);
}
vector<int> D(n+1);
for (int k(1);k < m;++k){
for (int i(0);i < n-(k!=m-1);++i) if (dpl0[i+1][k]&&dpr1[i+1+(k!=m-1)][k+1]&&s[i+1]!='X'){
//cout << i << ' ' << k << endl;
++D[max(i-A[k-1]+1,0)],--D[i+1];
//for (int j(i);j > i-A[k-1]&&(R[j]>>1)==0;--j) R[j] |= 2;
}
}
for (int i(0),k(D[0]);i < n;++i) R[i] |= 2*(k!=0),k += D[i+1];
string res;
for (int i(0);i < n;++i) res += ans[R[i]];
return res;
}
