#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
vector<int> prefX={0};
vector<int> pref_={0};
int n;
int getX(int l, int r) {
//get X in the interval inclusive
return prefX[min(r+1,n)] - prefX[l];
}
int get_(int l, int r) {
//get _ in the interval inclusive
return pref_[r+1] - pref_[l];
}
vector<vector<bool>> getdp(string s, vector<int> &prefX, vector<int> &pref_, vector<int> c) {
int k=c.size();
vector<vector<bool>> dp(n+2, vector<bool>(k+1));
dp[0][0] = 1;
//with the last segment covering i-2 (so can start at i) and having covered j segments already
for (int j=0; j<=k; j++) {
for (int i=0; i<n; i++) {
if (!getX(i,i)) dp[i+1][j] = dp[i+1][j] | dp[i][j];
}
if (j==k) {
break;
}
for (int i=0; i<n-c[j]+1; i++) {
if (!get_(i, i+c[j]-1) && !getX(i+c[j], i+c[j])) dp[i+c[j]+1][j+1] = dp[i+c[j]+1][j+1] | dp[i][j];
}
}
for (int i=0; i<n+2; i++) {
for (int j=0; j<=k; j++) {
//cout << dp[i][j] << " ";
}
//cout << endl;
}
return dp;
}
void update_pref(string s) {
prefX = vector<int>(n+1,0);
pref_ = vector<int>(n+1,0);
for (int i=0; i<n; i++) {
prefX[i+1] = prefX[i]+(s[i]=='X');
pref_[i+1] = pref_[i]+(s[i]=='_');
}
}
string solve_puzzle(string s, vector<int> c) {
n=s.size();
update_pref(s);
vector<vector<bool>> forwarddp = getdp(s,prefX, pref_, c);
//forwarddp[index][j] = is it possible to get next pos start at index, with j used to the left
reverse(s.begin(), s.end());
update_pref(s);
reverse(c.begin(), c.end());
//cout << endl;
vector<vector<bool>> backwarddp = getdp(s,prefX, pref_, c);
//backward[index][j] = is it possible to get next pos start at n-index-1, with j used to the right
reverse(s.begin(), s.end());
update_pref(s);
reverse(c.begin(), c.end());
vector<pair<int,int>> goodxint;
int k=c.size();
vector<int> answers(n,0); //0 = fail both, 1 = X, 2 = _, 3 = X or _
for (int j=0; j<=k; j++) {
for (int start=0; start<n; start++) {
//consider putting a whitespace in start
if (getX(start, start)==0 && forwarddp[start+1][j] && backwarddp[n-(start-1)-1][k-j]) {
answers[start] |= 2;
}
if (!(start<n-c[j]+1) || j==k) {
continue;
}
int end = start+c[j]-1;
//cout << start << " " << end << " " << j << endl;
//fw[start+1] and bw[end-1]
if (get_(start,end)==0 && forwarddp[start][j] && backwarddp[n-(end)-1][k-j-1]) {
goodxint.push_back({start,end}); //everything in these bounds inclusive is good
////cout << "adding" << " " << start << " " << end << endl;
}
}
}
//cout << "ANSWERS1 ";
for (int i=0; i<n; i++) {
//cout <<answers[i] << " ";
}
//cout << endl;
vector<pair<int,int>> finalint;
sort(goodxint.begin(), goodxint.end());
for (int i=0; i<goodxint.size(); i++) {
int fi,se;
fi=goodxint[i].first;
se=goodxint[i].second;
if (!finalint.size()) {
finalint.push_back(goodxint[i]);
}
else {
if (fi>finalint.back().second) {
finalint.push_back(goodxint[i]);
}
else if (se>finalint.back().second) {
pair<int,int> last=finalint.back();
finalint.pop_back();
finalint.push_back({last.first,se});
}
}
}
for (int i=0; i<finalint.size(); i++) {
for (int j=finalint[i].first; j<=finalint[i].second; j++) {
answers[j] |= 1;
}
}
//cout << "ANSWERS2 ";
for (int i=0; i<n; i++) {
//cout <<answers[i] << " ";
}
//cout << endl;
string fans;
for (int i=0; i<n; i++) {
assert(answers[i]!=0);
if (answers[i]==1) {
fans.push_back('X');
}
else if (answers[i]==2) {
fans.push_back('_');
}
else if (answers[i]==3) {
fans.push_back('?');
}
}
return fans;
}
