#include "paint.h"
#include <cstdlib>
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;
const int N = 2e5+5;
const int K = 105;
int n, k;
string s;
V<int> c;
bool canwh[N], canbl[N];
int prfwh[N], prfbl[N];
int cntwh(int l,int r){
return (r>0 ? prfwh[r]:0) - (l>0 ? prfwh[l-1]:0);
}
int cntbl(int l,int r){
return (r>0 ? prfbl[r]:0) - (l>0 ? prfbl[l-1]:0);
}
// dp[i][j] = last black if fill position 1..i with blocks 1..c
// t = 0 : prefix
// t = 1 : suffix
bool dp[N][K];
bool can(int i,int j){
if(i<=0) return j<=0;
return dp[i][j];
// dp[i][j]+1 ... i must white
// return !cntbl(dp[i][j]+1, i);
}
bool cn[2][N][K];
bool cnf(int t,int i,int j){
if(t==0){
if(i<=0) return j<=0;
return cn[t][i][j];
}
else{
if(i>n) return j>k;
return cn[t][i][j];
}
}
struct Fenw{
int fw[N];
Fenw(){
rep(i,0,N) fw[i] = 0;
}
void upd(int l,int r){
for(; l<N; l+=l&-l) fw[l]++;
for(r++; r<N; r+=r&-r) fw[r]--;
}
int qry(int i){
int ret = 0;
for(; i>0; i-=i&-i) ret += fw[i];
return ret;
}
} fenw;
string solve_puzzle(string _s,V<int> _c){
// s.swap(_s); c.swap(_c);
n = _s.size(); k = _c.size();
s = " " + _s + " ";
c = {0};
for(int x : _c) c.push_back(x);
c.push_back(0);
// t=0 prefix, t=1 suffix
rep(t,0,2){
// dbg(t);
// cout << s << nl;
// cout << "c[] "; for(int x : c) cout << x << " ";
// cout << nl;
// build prefix sum
rep(i,1,n+2) prfbl[i] = prfwh[i] = 0;
rep(i,1,n+1){
if(s[i]=='X') prfbl[i] = 1;
if(s[i]=='_') prfwh[i] = 1;
}
prfbl[n+1] = prfwh[n+1] = 1;
rep(i,1,n+2){
prfbl[i] += prfbl[i-1];
prfwh[i] += prfwh[i-1];
}
rep(i,0,N) rep(j,0,K) dp[i][j] = 0;
rep(i,0,n+1){
if(s[i]=='X') break;
dp[i][0] = 1;
}
// dp[0][0] = 1;
// dp transition
rep(i,1,n+1) rep(j,1,k+1){
dp[i][j] = 0;
// empty here
if(s[i]!='X' && can(i-1,j)){
dp[i][j] = 1;
}
// fill here
if(s[i]!='_' && i>=c[j] && s[i-c[j]]!='X'
&& !cntwh(i-c[j]+1,i) && can(i-c[j]-1,j-1)){
dp[i][j] = 1;
}
}
rep(i,0,n+1) rep(j,0,k+1) if(can(i,j)){
int ii = t ? n+1-i : i;
int jj = t ? k+1-j : j;
cn[t][ii][jj] = 1;
// cout << ii _ jj << nl;
}
// reverse suffix into prefix
reverse(all(s));
reverse(all(c));
}
// build prefix sum
rep(i,1,n+2) prfbl[i] = prfwh[i] = 0;
rep(i,1,n+1){
if(s[i]=='X') prfbl[i] = 1;
if(s[i]=='_') prfwh[i] = 1;
}
prfbl[n+1] = prfwh[n+1] = 1;
rep(i,1,n+2){
prfbl[i] += prfbl[i-1];
prfwh[i] += prfwh[i-1];
}
// check if can white
rep(i,1,n+1) if(s[i]=='.'){
// put j blocks to left
rep(j,0,k+1){
canwh[i] |= cnf(0,i-1,j) && cnf(1,i+1,j+1);
}
}
// check if can black
// cout << "BLACK SEGS" << nl;
rep(j,1,k+1) for(int l=1,r=c[j]; r<=n; l++,r++){
// if(l==1 && r==3){
// dbg(l-2); dbg(j-1);
// dbg(cnf(0,l-2,j-1));
// dbg(s[l-1]);
// dbg(!cntwh(l,r));
// dbg(s[r+1]);
// dbg(cnf(1,r+2,j+1));
// }
if(cnf(0,l-2,j-1) && s[l-1]!='X'
&& !cntwh(l,r)
&& s[r+1]!='X' && cnf(1,r+2,j+1)
){
// cout << l _ r << nl;
fenw.upd(l,r);
// rep(i,l,r+1) canbl[i] = 1;
}
}
string ans = string(n+1,'T');
rep(i,1,n+1){
if(s[i]!='.'){
ans[i] = s[i];
continue;
}
if(canwh[i] && fenw.qry(i)) ans[i] = '?';
// if(canwh[i] && canbl[i]) ans[i] = '?';
else if(canwh[i]) ans[i] = '_';
// else if(canbl[i]) ans[i] = 'X';
else if(fenw.qry(i)) ans[i] = 'X';
// else assert(0);
}
return ans.substr(1);
}
