#include<bits/stdc++.h>
using namespace std;
#include "paint.h"
string solve_puzzle(string s, vector<int> c)
{
const int K = c.size();
const int N = s.size();
s = "_" + s + "_";
// Construct prefix sum
vector<int> preSum(N+3);
for (int i = 0; i < N + 2; i++)
preSum[i+1] = preSum[i] + (int)(s[i] == '_');
vector<vector<int>> DP_r(N+2, vector<int>(K+1));
DP_r[0][0] = 1;
for (int i = 0; i <= N; i++)
{
if (s[i] == 'X') continue;
for (int k = 0; k <= K; k++)
{
if (!DP_r[i][k]) continue;
if (s[i + 1] != 'X')
DP_r[i+1][k] = 1;
if (k == K || i + c[k] + 1 >= N + 2) continue;
if (preSum[i + c[k] + 1] - preSum[i + 1]) continue;
if (s[i + c[k] + 1] == 'X') continue;
DP_r[i + c[k] + 1][k + 1] = 1;
}
}
vector<vector<int>> DP_l(N+2, vector<int>(K+1));
DP_l[N+1][K] = 1;
for (int i = N+1; i >= 1; i--)
{
if (s[i] == 'X') continue;
for (int k = 0; k <= K; k++)
{
if (!DP_l[i][k]) continue;
if (s[i - 1] != 'X')
DP_l[i-1][k] = 1;
if (k == 0 || i - c[k-1] - 1 < 0) continue;
if (preSum[i] - preSum[i - c[k-1]]) continue;
if (s[i - c[k-1] - 1] == 'X') continue;
DP_l[i - c[k-1] - 1][k - 1] = 1;
}
}
vector<int> ps(N+2);
for (int i = 0; i < N + 2; i++)
{
if (s[i] == 'X') continue;
for (int k = 0; k < K; k++)
{
if (i + c[k] + 1 >= N + 2 || !DP_r[i][k] || !DP_l[i + c[k] + 1][k+1])
continue;
if (i + c[k] + 1 >= N + 2) continue;
if (preSum[i + c[k] + 1] - preSum[i + 1]) continue;
if (s[i + c[k] + 1] == 'X') continue;
ps[i+1]++;
ps[i+c[k]+1]--;
}
}
string res = "";
int sum = 0;
for (int i = 1; i <= N; i++)
{
sum += ps[i];
if (s[i] == 'X')
{
res += 'X';
continue;
}
if (sum)
{
bool ok = true;
for (int k = 0; k <= K; k++)
{
if (!DP_r[i][k] || !DP_l[i][k]) continue;
ok = false;
res += '?';
break;
}
if (ok) res += 'X';
}
else
res += '_';
}
return res;
}
