#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10,maxk=200;
int n,k,dpps[maxn][maxk],dpsuf[maxn][maxk],vas[maxn],ted1[maxn],ted2[maxn],hey[maxn];
std::string solve_puzzle(std::string s, std::vector<int> c) {
n=(int)s.size();
k=(int)c.size();
s.push_back('.');
for(int i=1;i<=n;i++){
ted1[i]+=ted1[i-1];
ted2[i]+=ted2[i-1];
ted1[i]+=(s[i-1]=='X');
ted2[i]+=(s[i-1]=='_');
}
dpps[0][0]=1;
dpsuf[n+1][k+1]=dpsuf[n+2][k+1]=1;
for(int i=1;i<=n;i++){
if(s[i-1]!='X'){
dpps[i][0]|=dpps[i-1][0];
}
for(int j=1;j<=k;j++){
if(s[i-1]!='X'){
dpps[i][j]|=dpps[i-1][j];
}
if(i>=c[j-1]+(j>1)&&ted2[i]-ted2[i-c[j-1]]==0){
if(j>0&&s[i-c[j-1]-1]=='X'){
continue;
}
dpps[i][j]|=dpps[i-c[j-1]-(j>1)][j-1];
}
}
}
for(int i=n;i>=1;i--){
if(s[i-1]!='X'){
dpsuf[i][k+1]|=dpsuf[i+1][k+1];
}
for(int j=k;j>=1;j--){
if(s[i-1]!='X'){
dpsuf[i][j]|=dpsuf[i+1][j];
}
if(i+c[j-1]+(j<k)-1<=n&&ted2[i+c[j-1]-1]-ted2[i-1]==0){
if(j<k&&s[i+c[j-1]-1]=='X'){
continue;
}
dpsuf[i][j]|=dpsuf[i+c[j-1]+(j<k)][j+1];
}
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
if(dpps[i-1][j]==1&&dpsuf[i+1][j+1]==1){
vas[i]=1;
}
if(dpps[i][j]==1&&dpsuf[i+2][j+1]==1&&j>0&&dpps[i-c[j-1]-(j>1)][j-1]==1&&ted2[i]-ted2[i-c[j-1]]==0){
hey[i]++;
hey[i-c[j-1]]--;
}
}
}
for(int i=n;i>=0;i--){
hey[i]+=hey[i+1];
if(hey[i]!=0){
vas[i]+=2;
}
}
string ret;
ret.resize(n);
for(int i=0;i<n;i++){
if(s[i]=='X'||s[i]=='_'){
ret[i]=s[i];
continue;
}
if(vas[i+1]==0){
exit(0);
}
if(vas[i+1]==1){
ret[i]='_';
}else if(vas[i+1]==2){
ret[i]='X';
}else{
ret[i]='?';
}
}
return ret;
}
