#include "paint.h"
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <bits/stdc++.h>
using namespace std;
std::string solve_puzzle(std::string s, std::vector<int> c) {
int k = c.size();
int n = s.size();
int ps[2][n]; // X _
ps[0][0] = (s[0] == 'X');
ps[1][0] = (s[0] == '_');
for(int i=1; i<n; i++) {
ps[0][i] = ps[0][i-1] + (s[i] == 'X');
ps[1][i] = ps[1][i-1] + (s[i] == '_');
}
int can[2][n]; // X _
for(int i=0; i<2; i++) {
for(int j=0; j<n; j++) {
can[i][j] = 0;
}
}
int mx[n];
int prv = 0;
for(int i=0; i<n; i++) {
if(s[i] == 'X') prv = i;
mx[i] = prv;
}
int mx2[n];
prv = n-1;
for(int i=n-1; i>=0; i--) {
if(s[i] == 'X') prv = i;
mx2[i] = prv;
}
bool dp_forward[k][n];
bool dp_backward[k][n];
for(int i=0; i<k; i++) {
for(int j=0; j<n; j++) {
dp_forward[i][j] = dp_backward[i][j] = 0;
}
}
int dp_forsum[k][n];
int dp_backsum[k][n];
for(int i=0; i<k; i++) {
for(int j=0; j<n; j++) {
dp_forsum[i][j] = dp_backsum[i][j] = 0;
}
}
int real_dp[k][n]; // The real answer to question "i-th black segment ENDING at j-th column?"
int real_sum[k][n];
for(int i=0; i<k; i++) {
for(int j=0; j<n; j++) {
real_dp[i][j] = 0;
real_sum[i][j] = 0;
}
}
for(int i=c[0]-1; i<n; i++) {
if(ps[1][i] - (i == c[0] - 1 ? 0 : ps[1][i - c[0]]) == 0) {
if(i == c[0] - 1 || ps[0][i - c[0]] == 0) {
dp_forward[0][i] = 1;
}
}
dp_forsum[0][i] = (i == 0 ? 0 : dp_forsum[0][i-1]) + dp_forward[0][i];
}
int cum = c[0] + 1;
for(int i=1; i<k; i++) {
cum += c[i];
for(int j=cum-1; j<n; j++) {
if(ps[1][j] - ps[1][j-c[i]] > 0) {
dp_forsum[i][j] = dp_forsum[i][j-1] + dp_forward[i][j];
continue;
}
if(s[j - c[i]] == 'X') {
dp_forsum[i][j] = dp_forsum[i][j-1] + dp_forward[i][j];
continue;
}
dp_forward[i][j] = (dp_forsum[i-1][j-c[i]-1] - (mx[j-c[i]] == 0 ? 0 : dp_forsum[i-1][mx[j-c[i]]-1]) > 0);
dp_forsum[i][j] = dp_forsum[i][j-1] + dp_forward[i][j];
}
cum++;
}
for(int i=0; i<n - c[k-1] + 1; i++) {
if(ps[1][i + c[k-1] - 1] - (i > 0 ? ps[1][i-1] : 0) == 0) {
if(ps[0][n-1] - ps[0][i + c[k-1] - 1] == 0) {
dp_backward[k-1][i] = 1;
}
}
dp_backsum[k-1][i] = (i == 0 ? 0 : dp_backsum[k-1][i-1]) + dp_backward[k-1][i];
}
for(int i=n-c[k-1]+1; i<n; i++) {
dp_backsum[k-1][i] = (i == 0 ? 0 : dp_backsum[k-1][i-1]) + dp_backward[k-1][i];
}
cum = c[k-1] + 1;
for(int i=k-2; i>=0; i--) {
cum += c[i] - 1;
for(int j=0; j<n-cum; j++) {
if(ps[1][j + c[i] - 1]-(j > 0 ? ps[1][j-1] : 0) > 0) {
dp_backsum[i][j] = (j==0 ? 0 : dp_backsum[i][j-1]) + dp_backward[i][j];
continue;
}
if(s[j + c[i]] == 'X') {
dp_backsum[i][j] = (j==0 ? 0 : dp_backsum[i][j-1]) + dp_backward[i][j];
continue;
}
dp_backward[i][j] = (dp_backsum[i+1][mx2[j + c[i]]] - dp_backsum[i+1][j+c[i]] > 0);
dp_backsum[i][j] = (j==0 ? 0 : dp_backsum[i][j-1]) + dp_backward[i][j];
}
for(int j=n-cum; j<n; j++) {
dp_backsum[i][j] = (j==0 ? 0 : dp_backsum[i][j-1]) + dp_backward[i][j];
}
cum += 2;
}
for(int i=0; i<k; i++) {
for(int j=0; j<n; j++) {
if(j+1<n && s[j+1] == 'X') {
real_sum[i][j] = (j == 0 ? 0 : real_sum[i][j-1]) + real_dp[i][j];
continue;
}
if(j == n-1) {
if(i == k-1) real_dp[i][j] = dp_forward[i][j];
real_sum[i][j] = (j == 0 ? 0 : real_sum[i][j-1]) + real_dp[i][j];
continue;
}
if(i == k-1) {
real_dp[i][j] = dp_forward[i][j] && (ps[0][n-1] - ps[0][j] == 0);
real_sum[i][j] = (j == 0 ? 0 : real_sum[i][j-1]) + real_dp[i][j];
continue;
}
real_dp[i][j] = dp_forward[i][j] && (dp_backsum[i+1][mx2[j+1]] - dp_backsum[i+1][j+1] > 0);
real_sum[i][j] = (j == 0 ? 0 : real_sum[i][j-1]) + real_dp[i][j];
if(real_dp[i][j]) assert(s[j] != '_');
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<k; j++) {
if(real_sum[j][min(n-1, i+c[j]-1)] - (i==0 ? 0 : real_sum[j][i-1]) > 0) {
can[0][i] = 1;
}
}
for(int j=0; j<k-1; j++) {
if(s[i] != 'X' && i>0 && dp_forsum[j][i-1] - (mx[i-1] == 0 ? 0 : dp_forsum[j][mx[i-1] - 1]) > 0 && i + c[j+1] < n && (dp_backsum[j+1][mx2[i]] - dp_backsum[j+1][i] > 0)) {
can[1][i] = 1;
// if(i == 4)cout << j<<"\n";
}
}
if(s[i] != 'X' && dp_backsum[0][mx2[i]] - dp_backsum[0][i] > 0 && (i == 0 || ps[0][i-1] == 0)) {
can[1][i] = 1;
// if(i==4) cout<<"A\n";
}
if(s[i] != 'X' && i > 0 && real_sum[k-1][i-1] && ps[0][n-1] - ps[0][i] == 0) {
can[1][i] = 1;
// if(i==4) cout<<"B\n";
}
}
for(int i=0; i<k; i++) {
for(int j=0; j<n; j++) {
if(real_dp[i][j]) assert(s[j] != '_');
}
}
string ans;
for(int i=0; i<n; i++) {
if(can[0][i] && can[1][i]) ans += "?";
else if(can[0][i]) ans += "X";
else ans += "_";
}
for(int i=0; i<n; i++) {
assert(!(s[i] == 'X' && ans[i] != 'X'));
assert(!(s[i] == '_' && ans[i] != '_'));
}
return ans;
}
