#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_?";
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);
}
}
for(int I = 0; I < n; I++){
if(A[I] != 2){
ANS[I] = A[I];
continue;
}
for(int ai = 0; ai < 2; ai++){
bool DEBUG = (ai == -1 && I == 4);
A[I] = ai;
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);
if(DEBUG && i == 6){
cerr << j << " - " << wh(i-1-c0,i-2) << " what\n";
}
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";
}
}
if(DP[0][0]){
ANS[I] ^= (ai+1);
}
}
ANS[I]--;
A[I] = 2;
}
/*
vector<pii> intervals;
intervals.push_back({0,0});
rep(j,0,k){
sort(all(intervals));
vector<pii> intervals2;
int r = 0;
trav(p, intervals){
rep(i, max(r, p.first), p.second+1){
if(DP[j][i]){
}
r = max(r, p.second+1);
}
}
}
*/
string ans = "";
rep(c1,0,n){
//cerr << ANS[c1] << "\n";
ans += alf[ANS[c1]];
}
return ans;
}
