#include "paint.h"
#include <cstdlib>
#include <iostream>
using namespace std;
int n, k;
vector<int> l;
vector<int> r;
vector<int> last;
vector<int> nexxt;
string solve_puzzle(string s, vector<int> c) {
n = s.size();
k = c.size();
l = vector<int>(k);
r = vector<int>(k);
last = vector<int>(n);
nexxt = vector<int>(n);
if (s[0] != '_') {
last[0] = -1;
}
if (s[n-1] != '_') {
nexxt[n-1] = n;
} else {
nexxt[n-1] = n-1;
}
for (int i = 1; i < n; i++) {
if (s[i] == '_') {
last[i] = i;
} else {
last[i] = last[i-1];
}
}
for (int i = n-2; i >= 0; i--) {
if (s[i] == '_') {
nexxt[i] = i;
} else {
nexxt[i] = nexxt[i+1];
}
}
int lindex = 0;
int rindex = n-1;
for (int i = 0; i < k; i++) {
while (true) {
int fail = -1;
for (int j = lindex; j < lindex+c[i]; j++) {
if (s[j] == '_') {
fail = j;
}
}
if (fail == -1) {
l[i] = lindex;
lindex = lindex+c[i]+1;
break;
} else {
lindex = fail+1;
}
}
while (true) {
int fail = -1;
for (int j = rindex; j > rindex-c[k-1-i]; j--) {
if (s[j] == '_') {
fail = j;
}
}
if (fail == -1) {
r[k-1-i] = rindex;
rindex = rindex-c[k-1-i]-1;
break;
} else {
rindex = fail-1;
}
}
}
/*
for (int i = 0; i < k; i++) {
cout << l[i] << " " << r[i] << endl;
}*/
string res = "";
for (int i = 0; i < n; i++) {
bool cover = false;
bool free = false;
for (int j = 0; j < k; j++) {
int left = max(l[j],last[i]+1);
int right = min(r[j],nexxt[i]-1);
/*
if (i == 3) {
cout << "- " << left << " " << right << endl;
}*/
if (right-left+1 >= c[j]) {
if (left <= i && i <= right) {
cover = true;
}
}
}
for (int j = 0; j < k-1; j++) {
if (l[j]+c[j] <= i && i <= r[j+1]-c[j+1]) {
free = true;
}
}
if (l[k-1]+c[k-1] <= i || i <= r[0]-c[0]) {
free = true;
}
if (free && cover) {
res += '?';
} else if (free) {
res += '_';
} else {
res += 'X';
}
}
return res;
}
