#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int MAXN = 200004;
const int MAXK = 104;
vi A;
vi C;
vi CSB, CSW;
int n,k;
bool DP[MAXK][MAXN] = {0};
int DPC[MAXK][MAXN] = {0};
int NEXTB[MAXN] = {0};
int wh(int lo, int hi){
if(lo > hi)return 0;
return CSW[hi+1]-CSW[lo];
}
int bl(int lo, int hi){
if(lo > hi)return 0;
return CSB[hi+1]-CSB[lo];
}
int CW[MAXN] = {0};
int CB[MAXN] = {0};
int ANS[MAXN] = {0};
string alf = "X_?";
int PREV[MAXK][MAXN] = {0};
void add_w(int i, int j){
if(i > j)return;
// cerr << "WHITE " << i << " " << j << "\n";
CW[i]++;
CW[j+1]--;
}
void add_b(int i, int j){
if(i > j)return;
// cerr << "BLACK " << i << " " << j << "\n";
CB[i]++;
CB[j+1]--;
}
int bla[2][MAXN] = {0};
void add_int(int i, int j, int b){
bla[b][i]++;
bla[b][j+1]--;
}
std::string solve_puzzle(string s, vector<int> c) {
n = sz(s);
k = sz(c);
C = c;
rep(c1,0,n){
if(s[c1] == 'X'){
// black
A.push_back(0);
}
if(s[c1] == '_'){
// white
A.push_back(1);
}
if(s[c1] == '.'){
A.push_back(2);
}
}
bool DEBUG = 0;
CSB.clear();
CSW.clear();
CSB.push_back(0);
CSW.push_back(0);
rep(c1,0,n){
CSB.push_back(CSB.back() + (A[c1] == 0));
CSW.push_back(CSW.back() + (A[c1] == 1));
}
rep(c1,0,n+1){
rep(c2,0,k+1){
DP[c2][c1] = 0;
}
}
int nex = n;
NEXTB[n] = n;
for(int c1 = n-1; c1 >= 0; c1--){
if(A[c1] == 0)nex = c1;
NEXTB[c1] = nex;
}
for(int i = n; i >= C[k-1]; i--){
if(i < n && A[i] == 0)break;
DP[k][i] = ((wh(i-C[k-1],i-1) == 0));
}
DPC[k][0] = 0;
rep(c1,0,n+1){
DPC[k][c1+1] = (DPC[k][c1] + DP[k][c1]);
}
for(int j = k-1; j >= 0; j--){
int c0 = 0;
if(j > 0){
c0 = C[j-1];
}
for(int i = c0+(j > 0); i < n; i++){
if(j == 0 || (A[i-1] != 0 && wh(i-1-c0,i-2) == 0)){
int lo = i + C[j] + (j < k-1);
int hi = NEXTB[i] + C[j] + (j < k-1);
hi = min(hi, n);
if(lo <= hi){
DP[j][i] = (DPC[j+1][hi+1] - DPC[j+1][lo] > 0);
}
}
}
DPC[j][0] = 0;
rep(c1,0,n+1){
DPC[j][c1+1] = (DPC[j][c1] + DP[j][c1]);
}
}
if(DEBUG){
rep(c1,0,k+1){
rep(c2,0,n+1){
cerr << DP[c1][c2] << " ";
}
cerr << "\n";
}
}
rep(j,0,k+1){
int prev = -1;
rep(i,0,n+1){
if(DP[j][i])prev = i;
PREV[j][i] = prev;
}
}
add_int(0,0,0);
rep(j,0,k+1){
int w = 0;
rep(i,0,n+1){
bla[(j+1)%2][i] = 0;
}
rep(i,0,n+1){
w += bla[j%2][i];
if(w > 0 && (DP[j][i])){
// cerr << j << " - " << i << "\n";
if(j == k){
add_w(i,n);
add_b(i-C[j-1],i-1);
}
else{
if(j > 0){
add_w(i-1,i-1);
add_b(i-1-C[j-1],i-2);
}
else{
add_w(0, i-1);
}
}
//if(j == k)continue;
int lo = i + C[j] + (j < k-1);
int hi = NEXTB[i] + C[j] + (j < k-1);
hi = min(hi, n);
// intervals2.push_back({lo,hi});
add_int(lo,hi,(j+1)%2);
int furthest = PREV[j+1][hi];
add_w(i, furthest - C[j] - (j < k-1) - 1);
}
}
}
int w = 0;
int b = 0;
rep(c1,0,n){
w += CW[c1];
b += CB[c1];
if(b > 0){
ANS[c1] ^= 1;
}
if(w > 0){
ANS[c1] ^= 2;
}
}
rep(c1,0,n){
ANS[c1]--;
}
string ans = "";
rep(c1,0,n){
// cerr << ANS[c1] << "\n";
ans += alf[ANS[c1]];
}
return ans;
}
