#pragma GCC optimization "Ofast"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 3e5 + 9;
const ll mod = 1e9 + 7;
ll a[N],k,n;
ll dp1[N][203],dp2[N][203];
ll CanWhite[N],CanBlack[N],pre[N],suf[N];
string s;
bool Any(ll L,ll R){
return pre[R] - pre[L - 1];
}
ll f1(ll n,ll k){
if (k < 0) return 0;
if (n < 1) return (k == 0);
if (dp1[n][k] != -1) return dp1[n][k];
ll ans = 0,nxt = n - a[k] - 1;
if (s[n] == 'X' && n - a[k] + 1 > 0 && !Any(nxt + 2,n) && s[nxt + 1] != 'X') ans = f1(nxt,k - 1);
if (s[n] == '_') ans = f1(n - 1,k);
if (s[n] == '.'){
ans = f1(n - 1,k);
if (n - a[k] + 1 > 0 && !Any(nxt + 2,n) && s[nxt + 1] != 'X') ans |= f1(nxt,k - 1);
}
return dp1[n][k] = ans;
}
ll f2(ll pos,ll cur){
if (cur > k + 1) return 0;
if (pos > n) return (cur == k + 1);
if (dp2[pos][cur] != -1) return dp2[pos][cur];
ll ans = 0,nxt = pos + a[cur] + 1; //cout<<nxt; exit(0);
if (s[pos] == 'X' && pos + a[cur] - 1 <= n && !Any(pos,nxt - 2) && s[nxt - 1] != 'X') ans = f2(nxt,cur + 1);
if (s[pos] == '_') ans = f2(pos + 1,cur);
if (s[pos] == '.'){
ans = f2(pos + 1,cur);
if (pos + a[cur] - 1 <= n && !Any(pos,nxt - 2) && s[nxt - 1] != 'X') ans |= f2(nxt,cur + 1);
}
return dp2[pos][cur] = ans;
}
string solve_puzzle(string p,vector<ll> c){
n = p.size(); k = c.size(); s = " " + p;
for (ll i = 1;i <= k;i++) a[i] = c[i - 1];
for (ll i = 1;i <= n;i++){
pre[i] = pre[i - 1];
if (s[i] == '_') pre[i]++;
}
//cout<<pre[4]; exit(0);
memset(dp1,-1,sizeof(dp1)); memset(dp2,-1,sizeof(dp2));
string ans;
for (ll i = 1;i <= n;i++){
for (ll j = 0;j <= k;j++){
CanWhite[i] |= (f1(i - 1,j) & f2(i + 1,j + 1));
}
//cout<<f2(2,1); exit(0);
for (ll j = 1;j <= k;j++){
ll start = i - a[j] + 1; if (start < 1) continue;
if (s[start - 1] != 'X' && !Any(start,i) && s[i + 1] != 'X'){
//cout<<f(5,1); exit(0);
//cout<<f1(i,j)<<" "<<f2(i + 2,j + 1)<<"\n";
if (f1(start - 2,j - 1) & f2(i + 2,j + 1)){
CanBlack[start]++,CanBlack[i + 1]--;
//cout<<start<<" "<<i<<" "<<j<<"\n";
}
}
}
//exit(0);
}
//exit(0);
for (ll i = 1;i <= n;i++){
CanBlack[i] += CanBlack[i - 1]; //cout<<CanBlack[i]<<" ";
ll p = CanBlack[i],q = CanWhite[i];
if (s[i] == '_') p = 0,q = 1;
if (s[i] == 'X') p = 1,q = 0;
if (p && q) ans += '?';
else if (!p && q) ans += '_';
else ans += 'X';
}
//exit(0);
return ans;
}
