#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
std::string solve_puzzle(std::string s, std::vector<int> c) {
int n = s.size();
int csz = c.size();
vector<int> end(csz);
vector<int> start(csz);
int curr = 0;
int j = csz - 1;
set<int> white;
for (int i = 0; i < n ; i++) {
if (s[i] == '_') {
white.insert(i);
}
}
for (int i = n - 1; i >= 0 && j >= 0; i--) {
if (s[i] == '_') {
curr = 0;
} else {
curr++;
}
if (curr == c[j]) {
end[j] = i;
j--;
curr = -1;
}
}
curr = 0;
j = 0;
for (int i = 0; i < n - 1 && j < csz; i++) {
if (s[i] == '_') {
curr = 0;
continue;
} else {
curr++;
}
if (curr == c[j]) {
start[j] = i - c[j] + 1;
j++;
curr = -1;
}
}
for (int i = 0; i < csz; i++) {
if (start[i] + c[i] - 1 > end[i]) {
for (int j = end[i]; j <= start[i] + c[i] - 1; j++) {
s[j] = 'X';
}
}
}
vector<vector<int>> v;
for (int i = 0; i < csz; i++) {
v.push_back({start[i], c[i]});
}
sort(v.begin(), v.end());
set<int> ss;
j = 0;
bool can = true;
for (int i = 0; i < n ; i++) {
if (s[i] == '_' || s[i] == 'X') {
can = 1;
continue;
}
if (j < csz && v[j][0] == i) {
ss.insert(v[j][1]);
j++;
}
if ((i == 0 && s[i] == '.') || (i > 0 && s[i] == '.' && s[i - 1] == '_')) {
auto it = white.lower_bound(i);
int e = n - 1;
if (it != white.end()) {
e = *it;
}
e = e - i;
auto itt = ss.upper_bound(e);
if ((itt == ss.end() && ss.size() == 0) || (itt == ss.begin())) {
can = false;
}
}
if (!can) {
s[i] = '_';
}
}
for (int i = 0 ; i < n ; i++) {
if (s[i] == '.') {
s[i] = '?';
}
}
return s;
}
