#include "paint.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define pld pair<ld, ld>
#define NEK 2000000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001
using namespace std;
string solve_puzzle(string s, vec<int> c) {
int n = s.size();
vec<set<int>> v(n+5);
v[0].insert(0);
vec<pii> b;
s.push_back('_');
vec<int> w;
int k = c.size();
vec<vec<bool>> dp(n + 1, vec<bool>(k+1, 0));
dp[n][c.size()] = 1;
vec<int> ps(n + 1, 0);
ps[0] = 0;
For(i, n) {
if (s[i] == '_') ps[i+1]++;
ps[i+1] += ps[i];
}
rfor(i, n - 1) {
For(j, k+1) {
//ostanem bielym
if(s[i] != 'X') dp[i][j] = dp[i + 1][j];
//ostanem ciernym
if (j == k) continue;
if (i + c[j] > n) continue;
int poc_b = ps[i + c[j]] - ps[i];
if (poc_b != 0) continue;
if (s[i + c[j]] == 'X') continue;
if (i + c[j] == n) {
dp[i][j] = dp[i][j] | dp[n][j + 1];
continue;
}
if(s[i] != '_') dp[i][j] = dp[i][j] || dp[i + c[j] + 1][j + 1];
}
}
For(i, n) {
for (auto j : v[i]) {
//idem cez vsetky moznosti toho co vybavili predomnou
//skus sa dat ako biely
if (s[i] != 'X') {
if (dp[i + 1][j]) {
w.push_back(i);
v[i + 1].insert(j);
}
}
//skus sa dat ako cierny
if (s[i] != '_' && j != k) {
int chod = i + c[j] + 1;
if (chod == n + 1) chod = n;
if (i + c[j] <= n && (ps[i + c[j]] - ps[i]) == 0 && s[i + c[j]] != 'X' && dp[chod][j + 1]) {
b.push_back({ i, i + c[j] - 1 });
w.push_back(i + c[j]);
v[i + c[j] + 1].insert(j + 1);
}
}
}
}
sort(all(b));
vec<bool> mb(n, 0), mw(n + 100, 0);
int som = 0;
int kon = -1;
For(i, n){
while (som < b.size() && b[som].ff <= i) {
kon = max(kon, b[som].ss);
som++;
}
if (i <= kon) mb[i] = 1;
}
For(i, w.size()) {
mw[w[i]] = 1;
}
string odp;
For(i, n) {
if (!mw[i]) {
odp.push_back('X');
continue;
}
if (!mb[i]) {
odp.push_back('_');
continue;
}
odp.push_back('?');
}
return odp;
}
/*
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s;
cin >> s;
int k; cin >> k;
vec<int> c(k);
For(i, k) cin >> c[i];
cout << solve_puzzle(s, c) << '\n';
return 0;
}*/
