#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
bool dpf[101][200002], dpb[101][200002];
string s; int n; int ps_b[200002], ps_w[200002];
inline bool empty(int l, int r) { if(l < 1 || l > n || r < 1 || r > n) return false; return ps_b[r] == ps_b[l - 1]; }
inline bool fill(int l, int r) { if(l < 1 || l > n || r < 1 || r > n) return false; return ps_w[r] == ps_w[l - 1]; }
int aps_b[200002];
std::string solve_puzzle(std::string s, std::vector<int> c) {
s = "_" + s + "$"; n = s.size() - 2;
for(int i = 1; i <= n; i++) ps_b[i] = ps_b[i - 1] + (s[i] == 'X');
for(int i = 1; i <= n; i++) ps_w[i] = ps_w[i - 1] + (s[i] == '_');
int k = c.size(); vector<int> a; a.push_back(0);
for(int i = 0; i < k; i++) { a.push_back(c[i]); };
dpf[0][0] = dpb[k + 1][n + 1] = true;
for(int i = 0; i <= k; i++){
for(int j = 1; j <= n; j++){
dpf[i][j] |= dpf[i][j - 1] && empty(j, j);
if(i == 1){
if(j >= a[i])
dpf[i][j] |= dpf[i - 1][j - a[i]] && fill(j - a[i] + 1, j);
}else if(i > 1){
if(j >= a[i] + 1)
dpf[i][j] |= dpf[i - 1][j - a[i] - 1] && empty(j - a[i], j - a[i]) && fill(j - a[i] + 1, j);
}
}
}
for(int i = k + 1; i >= 1; i--){
for(int j = n; j >= 1; j--){
dpb[i][j] |= dpb[i][j + 1] && empty(j, j);
if(i == k){
if(j <= n - a[i] + 1)
dpb[i][j] |= dpb[i + 1][j + a[i]] && fill(j, j + a[i] - 1);
}else if(i < k){
if(j <= n - a[i])
dpb[i][j] |= dpb[i + 1][j + a[i] + 1] && empty(j + a[i], j + a[i]) && fill(j, j + a[i] - 1);
}
}
}
string ans(n, ' ');
for(int i = 1; i <= k; i++){
for(int j = 1; j <= n; j++){
bool ok = true;
ok &= fill(j, j + a[i] - 1);
int f = j - (i != 1), b = j + a[i] - 1 + (i != k);
if(i != 1) ok &= empty(j - 1, j - 1);
if(i != k) ok &= empty(j + a[i], j + a[i]);
if(!ok) continue;
if(dpf[i - 1][f - 1] && dpb[i + 1][b + 1]){
aps_b[j]++, aps_b[j + a[i]]--;
}
}
}
for(int i = 1; i <= n; i++){
aps_b[i] += aps_b[i - 1];
}
for(int i = 1; i <= n; i++){
if(s[i] != '.'){
ans[i - 1] = s[i];
continue;
}
bool can_b = aps_b[i], can_w = false;
for(int j = 0; j <= k; j++){
if(dpf[j][i - 1] && dpb[j + 1][i + 1]){
can_w = true;
}
}
ans[i - 1] = (can_b ? (can_w ? '?' : 'X') : (can_w ? '_' : '$'));
}
return ans;
}
