#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "paint.h"
const int MAX_N = 200010, MAX_K = 105;
bool dp1[MAX_N][MAX_K], dp2[MAX_N][MAX_K];
int from1[MAX_N][MAX_K], from2[MAX_N][MAX_K];
char w[MAX_N];
int pf0[MAX_N], pf1[MAX_N], n;
int be0[MAX_N], be1[MAX_N];
int len[MAX_K], m;
int cnt1(int l, int r) { return pf1[r] - pf1[l-1]; }
int cnt0(int l, int r) { return pf0[r] - pf0[l-1]; }
void makedp1() {
for (int i = len[1];i <= n;++i)
dp1[i][1] = cnt0(i-len[1]+1, i) == 0 && cnt1(1, i-len[1]) == 0;
vector<int> f(m + 1);
for (int i = 1;i <= n;++i) {
for (int j = 2;j <= m;++j) {
if (len[j] > i || w[i-len[j]] == 'X' || cnt0(i-len[j]+1, i)) continue;
int &k = f[j];
while (k < i - len[j] &&
(!dp1[k][j-1] || cnt1(k+1, i-len[j]))) ++k;
if (k < i - len[j]) {
assert(dp1[k][j-1] && cnt1(k+1, i-len[j]) == 0);
dp1[i][j] = true;
from1[i][j] = k;
}
}
}
}
void makedp2() {
for (int i = 1;i <= n - len[m] + 1;++i) {
dp2[i][m] = cnt0(i, i+len[m]-1) == 0 && cnt1(i+len[m], n) == 0;
from2[i][m] = n + 1;
}
vector<int> f(m + 1, n);
for (int i = n;i >= 1;--i) {
for (int j = 1;j < m;++j) {
if (i + len[j] - 1 > n || w[i+len[j]] == 'X' || cnt0(i, i+len[j]-1)) continue;
int &k = f[j];
while (k > i + len[j] &&
(!dp2[k][j+1] || cnt1(i+len[j], k-1))) --k;
if (k > i + len[j]) {
assert(dp2[k][j+1] && cnt1(i+len[j], k-1) == 0);
dp2[i][j] = true;
from2[i][j] = k;
}
}
}
}
void collect() {
for (int i = 1;i <= n;++i) {
for (int j = 1;j <= m;++j) {
if (dp1[i][j] && dp2[i - len[j] + 1][j]) {
int l = i - len[j] + 1, r = i;
++be0[ from1[i][j] + 1 ];
--be0[ l ];
++be1[ l ];
--be1[ r+1 ];
++be0[ r+1 ];
--be0[ from2[i - len[j] + 1][j] ];
}
}
}
for (int i = 1;i <= n;++i) {
be1[i] += be1[i-1];
be0[i] += be0[i-1];
}
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
static int cnt;
assert(++cnt == 1);
n = s.size();
for (int i = 1;i <= n;++i) {
pf0[i] = pf0[i-1] + (s[i-1] == '_');
pf1[i] = pf1[i-1] + (s[i-1] == 'X');
w[i] = s[i-1];
}
m = c.size();
for (int i = 1;i <= m;++i)
len[i] = c[i-1];
makedp1();
makedp2();
collect();
string res(n, '?');
for (int i = 1;i <= n;++i) {
assert(be0[i] || be1[i]);
if (be0[i] && be1[i]) continue;
if (be0[i])
res[i-1] = '_';
if (be1[i])
res[i-1] = 'X';
}
for (int i = 0;i < n;++i) {
if (s[i] != '.' && res[i] != '?') assert(res[i] == s[i]);
}
return res;
}
