#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 && j < csz; i++) {
if (s[i] == '_') {
curr = 0;
continue;
} else {
curr++;
}
// cout << curr << " " << i << endl;
if (curr == c[j]) {
start[j] = i - c[j] + 1;
j++;
curr = -1;
}
}
// cout << start[1] << " " << end[1] << endl;
for (int i = 0; i < csz; i++) {
if (start[i] == end[i] && start[i] + c[i] < n) {
s[start[i] + c[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;
vector<vector<int>> v2;
for (int i = 0; i < csz; i++) {
v.push_back({start[i], c[i]});
v2.push_back({end[i] + 1, c[i]});
}
sort(v.begin(), v.end());
sort(v2.begin(), v2.end());
set<int> ss;
map<int, int> mp;
j = 0;
int j2 = 0;
bool can = true;
// cout << start[1] << " " << end[1] << endl;
for (int i = 0; i < n ; i++) {
if (j < csz && v[j][0] == i) {
ss.insert(v[j][1]);
mp[v[j][1]]++;
j++;
}
if (j2 < csz && v2[j2][0] == i) {
mp[v2[j2][1]]--;
if (mp[v2[j2][1]] == 0) {
ss.erase(ss.lower_bound(v2[j2][1]));
}
j2++;
}
if (s[i] == '_' || s[i] == 'X') {
can = 1;
continue;
}
if ((i == 0 && s[i] == '.') || (i > 0 && s[i] == '.' && s[i - 1] == '_')) {
auto it = white.lower_bound(i);
int e = n;
if (it != white.end()) {
e = *it;
}
e = e - i;
// cout << e << endl;
auto itt = ss.upper_bound(e);
if ((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;
}
