#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define sp " "
#define N 200005
#define K 105
int dp[N][K][2], dp2[N][K][2];
int pre_one[K][N];
string solve_puzzle(string s, vector<int> c) {
int n = s.size();
int k = c.size();
vector<int> tmp;
tmp.pb(0);
for (auto i : c) tmp.pb(i);
c = tmp;
string t = ".";
t = t + s;
s = t;
vector<int> pre(n + 5, 0);
for (int i = 1; i <= n; i++)
{
pre[i] = pre[i - 1];
if (s[i] == '_') pre[i]++;
}
dp[n + 1][k + 1][0] = 1;
for (int i = n; i >= 1; i--){
for (int j = 1; j <= k + 1; j++){
if (s[i] == 'X'){
dp[i][j][0] = 0;
if (j == k + 1 || c[j] + i - 1 > n)
dp[i][j][1] = 0;
else
{
int p = pre[i + c[j] - 1] - pre[i - 1];
dp[i][j][1] = (dp[i + c[j]][j + 1][0]) & (p == 0);
}
}
else if (s[i] == '_'){
dp[i][j][1] = 0;
dp[i][j][0] = dp[i + 1][j][0] | dp[i + 1][j][1];
}
else{
dp[i][j][0] = dp[i + 1][j][0] | dp[i + 1][j][1];
if (j == k + 1 || c[j] + i - 1 > n)
dp[i][j][1] = 0;
else {
int p = pre[i + c[j] - 1] - pre[i - 1];
dp[i][j][1] = (dp[i + c[j]][j + 1][0]) & (p == 0);
}
}
//cout<<i<<sp<<j<<" : "<<dp[i][j][0]<<sp<<dp[i][j][1]<<endl;
}
}
dp2[0][0][0] = 1;
for (int i = 1; i <= n; i++){
for (int j = 0; j <= k; j++){
if (s[i] == 'X'){
dp2[i][j][0] = 0;
if (j == 0 || i < c[j]) dp2[i][j][1] = 0;
else{
int p = pre[i] - pre[i - c[j]];
dp2[i][j][1] = (p == 0) & dp2[i - c[j]][j - 1][0];
}
}
else if (s[i] == '_'){
dp2[i][j][1] = 0;
dp2[i][j][0] = dp2[i - 1][j][0] | dp2[i - 1][j][1];
}
else{
if (j == 0 || i < c[j]) dp2[i][j][1] = 0;
else{
int p = pre[i] - pre[i - c[j]];
dp2[i][j][1] = (p == 0) & dp2[i - c[j]][j - 1][0];
}
dp2[i][j][0] = dp2[i - 1][j][0] | dp2[i - 1][j][1];
}
//cout<<i<<sp<<j<<" : "<<dp2[i][j][0]<<sp<<dp2[i][j][1]<<endl;
}
}
string ans;
for (int i = 1; i <= k; i++){
for (int j = 1; j <= n; j++){
pre_one[i][j] = pre_one[i][j - 1];
int curr = dp2[j - 1][i - 1][0] & dp[j][i][1];
pre_one[i][j] += curr;
}
}
for (int i = 1; i <= n; i++){
int one = 0, zero = 0;
for (int j = 1; j <= k; j++){
/*
for (int l = max((int)0, i - c[j] + 1); l <= i; l++){
int curr = dp2[l - 1][j - 1][0] & dp[l][j][1];
one |= curr;
}*/
int tmp = pre_one[j][i] - pre_one[j][max((int)0, i - c[j])];
if (tmp > 0) one |= 1;
}
for (int j = 0; j <= k; j++){
int curr = dp2[i][j][0] & (dp[i + 1][j + 1][0] | dp[i + 1][j + 1][1]);
//cout<<i<<sp<<j<<sp<<curr<<endl;
zero |= curr;
}
if (one && zero) ans.pb('?');
else if (one) ans.pb('X');
else ans.pb('_');
}
return ans;
}
