#include "paint.h"
#include <cstdlib>
#include<bits/stdc++.h>
#ifdef LOCAL
#include "debugger.cpp"
#else
#define debug(...)
#endif
using namespace std;
#define all(a) (a).begin(), (a).end()
string solve_puzzle(string s, vector<int> c) {
int n = s.size();
int k = c.size();
s = "$" + s + "$";
reverse(all(c)); c.push_back(0); reverse(all(c)); c.push_back(0);
vector lef(k + 2, vector(n + 2, false)), rig(k + 2, vector(n + 2, false));
lef[0][0] = 1;
for(int i = 1; i <= n; i ++){
if(s[i] == 'X') break;
lef[0][i] = 1;
}
vector<int> w(n + 2), b(n + 2);
for(int i = 1; i <= n; i ++) w[i] = w[i - 1] + (s[i] == '_'), b[i] = b[i - 1] + (s[i] == 'X');
for(int i = 1; i <= k; i ++){
vector<int> near(n + 2, -1);
if(i == 1) near[0] = 0;
for(int j = 1; j <= n; j ++) near[j] = (lef[i - 1][j] ? j : near[j - 1]);
//debug(near);
for(int j = c[i]; j <= n; j ++){
if(j == c[i]){
if(i == 1) lef[i][j] = 1;
}else{
if(w[j] - w[j - c[i]] == 0 && near[j - c[i] - 1] != -1 && b[j - c[i]] - b[near[j - c[i] - 1]] == 0){
// debug(i, j, c[i]);
lef[i][j] = 1;
}
}
}
}
//debug(lef);
rig[k + 1][n + 1] = 1;
for(int i = n; i >= 1; i --){
if(s[i] == 'X') break;
rig[k + 1][i + 1] = 1;
}
for(int i = k; i >= 1; i --){
vector<int>near(n + 2, -1);
if(i == k) near[n + 1] = n + 1;
for(int j = n; j >= 1; j --) near[j] = (rig[i + 1][j] ? j : near[j + 1]);
for(int j = n - c[i] + 1; j >= 1; j --){
if(j + c[i] - 1 == n){
if(i == k) rig[i][j] = 1;
}else{
if(w[j + c[i] - 1] - w[j - 1] == 0 && near[j + c[i] + 1] != -1 && b[near[j + c[i] + 1] - 1] - b[j + c[i]] == 0){
rig[i][j] = 1;
}
}
}
}
vector<int> x(n + 2), _(n + 2);
for(int i = 1; i <= k; i ++){
for(int j = 1; j + c[i] - 1 <= n; j ++){
if(lef[i][j + c[i] - 1] && rig[i][j]){
x[j] ++;
x[j + c[i]] --;
}
}
}
for(int j = 1; j <= n; j ++){
x[j] += x[j - 1];
}
debug(x);
debug(rig);
for(int i = 0; i <= k; i ++){
vector<int> near(n + 2, -1);
if(rig[i + 1][n + 1]) near[n + 1] = n + 1;
for(int j = n; j >= 1; j --){
near[j] = (rig[i + 1][j] ? j : near[j + 1]);
}
vector<int> lnear(n + 2, -1);
if(i == 0) lnear[0] = 0;
for(int j = 1; j <= n; j ++){
lnear[j] = lef[i][j] ? j : lnear[j - 1];
}
for(int j = 1; j <= n; j ++){
if(lnear[j - 1] != -1 && near[j + 1] != -1 && b[near[j + 1] - 1] - b[lnear[j - 1]] == 0){
debug(i, j, near[j + 1]);
_[lnear[j - 1] + 1] ++;
_[near[j + 1]] --;
}
}
}
for(int i = 1; i <= n; i ++) _[i] += _[i - 1];
string ans = "";
for(int i = 1; i <= n; i ++) if(_[i] && x[i]) ans.push_back('?'); else if(_[i]) ans.push_back('_'); else ans.push_back('X');
return ans;
}
