#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=105;
bool dp[nx][nx][nx], r[nx][2], vs[nx][nx][nx];
std::string solve_puzzle(std::string s, std::vector<int> c) {
c.push_back(0);
int n=s.size(), k=c.size();
for (int i=0; i<n; i++)
{
for (int j=0; j<k; j++)
{
if (s[i]=='.'||s[i]=='_')
{
if (i==0&&j!=0) continue;
if (i==0) dp[i][j][0]=1;
else if (j==0) dp[i][j][0]=dp[i-1][j][0];
else dp[i][j][0]=dp[i-1][j-1][c[j-1]]||dp[i-1][j][0];
}
if (s[i]=='.'||s[i]=='X')
{
if (i==0&&j!=0) continue;
if (i==0) dp[i][j][1]=1;
else for (int l=1; l<=c[j]; l++) dp[i][j][l]|=dp[i-1][j][l-1];
}
}
}
queue<pair<int, pair<int, int>>> q;
if (dp[n-1][k-1][0]) q.push({n-1, {k-1, 0}});
if (dp[n-1][k-2][c[k-2]]) q.push({n-1, {k-2, c[k-2]}});
while (!q.empty())
{
int ci=q.front().first, cj=q.front().second.first, cl=q.front().second.second;
q.pop();
if (vs[ci][cj][cl]) continue;
//cout<<ci<<' '<<cj<<' '<<cl<<'\n';
vs[ci][cj][cl]=1;
if (cl==0) r[ci][0]=1;
else r[ci][1]=1;
if (ci==0) continue;
if ((s[ci]=='.'||s[ci]=='_')&&cl==0)
{
if (dp[ci-1][cj][0]) q.push({ci-1, {cj, 0}});
if (cj!=0&&dp[ci-1][cj-1][c[cj-1]]) q.push({ci-1, {cj-1, c[cj-1]}});
}
if ((s[ci]=='.'||s[ci]=='X')&&cl!=0)
{
if (dp[ci-1][cj][cl-1]) q.push({ci-1, {cj, cl-1}});
}
}
string ans;
for (int i=0; i<n; i++)
{
if (r[i][0]&&r[i][1]) ans=ans+'?';
else if (r[i][0]) ans=ans+'_';
else ans=ans+'X';
}
return ans;
}
