#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=2e5+5, kx=105;
bool dp[nx][kx][2], r[nx], vs[nx][kx][2];
int f[nx], p[nx];
std::string solve_puzzle(std::string s, std::vector<int> c) {
c.push_back(0);
int n=s.size(), k=c.size();
s=' '+s;
for (int i=1; i<=n; i++)
{
if (s[i]=='.'||s[i]=='X') f[i]=f[i-1]+1;
else f[i]=0;
for (int j=0; j<k; j++)
{
if (s[i]=='.'||s[i]=='_')
{
if (i==1&&j!=0) continue;
if (i==1) 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][1]||dp[i-1][j][0];
//cout<<i<<' '<<j<<' '<<0<<' '<<dp[i][j][0]<<'\n';
}
if (s[i]=='.'||s[i]=='X')
{
if (j==k-1) continue;
if (f[i]>=c[j]&&i-c[j]==0&&j==0) dp[i][j][1]=1;
if (f[i]>=c[j]&&i-c[j]>0) dp[i][j][1]=dp[i-c[j]][j][0];
//cout<<i<<' '<<j<<' '<<1<<' '<<dp[i][j][1]<<'\n';
}
}
}
queue<pair<int, pair<int, int>>> q;
if (dp[n][k-1][0]) q.push({n, {k-1, 0}});
if (dp[n][k-2][1]) q.push({n, {k-2, 1}});
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;
vs[ci][cj][cl]=1;
if (cl==0) r[ci]=1;
else p[ci-c[cj]+1]++, p[ci+1]--;
if (ci==1) 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][1]) q.push({ci-1, {cj-1, 1}});
}
if ((s[ci]=='.'||s[ci]=='X')&&cl!=0)
{
if (dp[ci-c[cj]][cj][0]) q.push({ci-c[cj], {cj, 0}});
}
}
for (int i=1; i<=n; i++)
{
p[i]+=p[i-1];
if (r[i]&&p[i]>0) s[i-1]='?';
else if (r[i]) s[i-1]='_';
else s[i-1]='X';
}
s.pop_back();
return s;
}
