#include "paint.h"
#include <vector>
#include <string>
#include <functional>
#include <limits>
#include <algorithm>
#include <cassert>
using namespace std;
struct segtree{
vector<int> cache;
function<int(int, int)> conquer;
int neutral;
segtree(int n, function<int(int, int)> conquera, int neutrala){
cache = vector<int> (n*4);
conquer = conquera;
neutral = neutrala;
}
int build(int l, int r, int i, vector<int>& v){
if(l+1==r) return cache[i] = v[l];
int m = l + (r-l)/2;
return cache[i] = conquer(build(l, m, i*2+1, v), build(m, r, i*2+2, v));
}
int query(int l, int r, int i, int ql, int qr){
if(ql <= l && r <= qr) return cache[i];
if(qr <= l || r <= ql) return neutral;
int m = l + (r-l)/2;
return conquer(query(l, m, i*2+1, ql, qr), query(m, r, i*2+2, ql, qr));
}
};
string solve_puzzle(string s, vector<int> c) {
int k = c.size();
int n = s.size();
auto add = [&](int a, int b) ->int {return a + b;};
auto minf = [&](int a, int b) ->int {return min(a, b);};
segtree sum (k, add, 0);
sum.build(0, k, 0, c);
segtree mint (k, minf, numeric_limits<int>::max());
mint.build(0, k, 0, c);
vector<int> back_cram = {k};
vector<int> occ = {n};
int tsize = 0;
int at = k-1;
for(int back = n-1; back >= 0; back--){
if(s[back] == '_'){
occ.push_back(back);
while(at >= 0 && tsize >= c[at]){
tsize -= c[at] + 1;
at--;
}
tsize = 0;
back_cram.push_back(at+1);
}
else tsize++;
}
occ.push_back(-1);
reverse(back_cram.begin(), back_cram.end());
reverse(occ.begin(), occ.end());
int maxdone = 0;
int bi = 0;
for(int solver = 0; solver < n; solver++){
if(s[solver] != '.'){
int tsize = occ[bi+1]-occ[bi]-1;
while(maxdone < k && tsize >= c[maxdone]){
tsize -= c[maxdone];
tsize -= 1;
maxdone++;
}
bi++;
continue;
}
bool w = false, b = false;
if(maxdone >= back_cram[bi]){
w = true;
if(occ[bi+1]-occ[bi] - 1 >= mint.query(0, k, 0, back_cram[bi]-1, maxdone+1)) b = true;
}
else{
int l = maxdone;
int r = back_cram[bi] + 1;
while(l+1<r){
int m = l + (r-l)/2;
int prened = sum.query(0, k, 0, maxdone, m) + (m-maxdone-1);
int preav = solver-occ[bi]-1;
if(prened > preav) r = m;
else l = m;
}
int prened = max(0,sum.query(0, k, 0, maxdone, l) + (l-maxdone-1));
int qans = sum.query(0, k, 0, l, back_cram[bi]);
int postned = max(0,sum.query(0, k, 0, l, back_cram[bi]) + (back_cram[bi]-l-1));
int preav = solver-occ[bi]-1;
int postav = occ[bi+1]-solver-1;
if(prened <= preav && postned <= postav){
w = true;
}
if(prened + postned + 1 < occ[bi+1]-occ[bi]-1 || occ[bi]+prened + 1 < solver || prened == 0 || postned == 0) b = true;
}
if(w && b) s[solver] = '?';
else if(w) s[solver] = '_';
else if(b) s[solver] = 'X';
else assert(false);
}
return s;
}
/*
#include "paint.h"
#include <vector>
#include <string>
#include <cstdio>
#include <cassert>
const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];
int main() {
assert(1 == scanf("%s", buf));
std::string s = buf;
int c_len;
assert(1 == scanf("%d", &c_len));
std::vector<int> c(c_len);
for (int i = 0; i < c_len; i++) {
assert(1 == scanf("%d", &c[i]));
}
std::string ans = solve_puzzle(s, c);
printf("%s\n", ans.data());
return 0;
}
*/
