#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
#define pii pair<int, int>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define fi first
#define se second
using namespace std;
string solve_puzzle(string s, vector<int> c) {
int n=s.size(), k=c.size(), lst=0;
int dp[n+1][k+1]{};
bool vis[n+1][k+1]{};
dp[0][0]=3;
rep(i,1,n+1){
if(s[i-1]=='_') lst=i;
rep(j,0,k+1){
if((s[i-1]=='_' || s[i-1]=='.') && dp[i-1][j]) dp[i][j]|=1;
if(j && i>=c[j-1] && lst<=i-c[j-1]){
if(i>c[j-1] && dp[i-c[j-1]-1][j-1] && s[i-c[j-1]-1]!='X') dp[i][j]|=2;
else if(i==c[j-1] && j==1) dp[i][j]|=2;
}
}
}
int x, y, p[n]{};
rep(i,0,n) s[i]='X';
vis[n][k]=true;
repr(i,n+1,1){
repr(j,k+1,0){
if(!vis[i][j]) continue;
if(dp[i][j]&1) vis[i-1][j]=true, p[i-1]|=1;
cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
if(dp[i][j]&2){
p[i-1]|=2;
if(i>c[j-1]){
p[i-c[j-1]-1]|=1;
vis[i-c[j-1]-1][j-1]=true;
}
rep(z,i-c[j-1],i) p[z]|=2;
}
}
}
rep(i,0,n){
if(p[i]==3) s[i]='?';
else if(p[i]==0) s[i]='X';
else if(p[i]==2) s[i]='X';
else s[i]='_';
}
return s;
}
