#include <bits/stdc++.h>
#include "paint.h"
#define pb push_back
#define fs first
#define sc second
using namespace std;
const int N = 2e5 + 5, K = 105;
bool dp[N][K], dp1[N][K], dp2[N][K];
int k, pref[N], n;
vector<int> c;
int wh[N], bl[N], diff[N];
void makedp(string s){
for(int i = 0; i <= n; i++){
for(int j = 0; j <= k; j++){
dp[i][j] = 0;
}
}
dp[0][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= k; j++){
if(s[i] != 'X') dp[i][j] |= dp[i - 1][j];
if(j > 0){
int len = c[j - 1];
int L = i - len + 1;
if(L >= 1){
if(pref[i] - pref[L - 1] == 0){
if(L == 1 or s[L - 1] != 'X'){
dp[i][j] |= dp[L - 1][j - 1];
}
}
}
}
}
}
}
string solve_puzzle(string s, vector<int> c1) {
n = s.size();
k = c1.size();
c.clear();
for(int i = 0; i < k; i++) c.pb(c1[i]);
string s1 = " " + s;
pref[0] = 0;
for(int i = 1; i <= n; i++){
pref[i] = pref[i - 1] + (s1[i] == '_' ? 1 : 0);
}
makedp(s1);
reverse(s.begin(), s.end());
s1 = "%" + s;
for(int i = 0; i <= n; i++){
for(int j = 0; j <= k; j++) dp1[i][j] = dp[i][j], dp[i][j] = 0;
}
pref[0] = 0;
for(int i = 1; i <= n; i++){
pref[i] = pref[i - 1] + (s1[i] == '_' ? 1 : 0);
}
reverse(c.begin(), c.end());
makedp(s1);
for(int i = 1; i <= n; i++){
for(int j = 0; j <= k; j++){
dp2[i][j] = dp[n - i + 1][k - j];
}
}
reverse(c.begin(), c.end());
reverse(s.begin(), s.end());
s = '%' + s;
pref[0] = 0;
for(int i = 1; i <= n; i++){
pref[i] = pref[i - 1] + (s[i] == '_' ? 1 : 0);
}
dp2[n + 1][0] = 1;
for(int i = 1; i <= n; i++){
if(s[i] != '.'){
wh[i] = bl[i] = 2;
continue;
}
for(int j = 0; j <= k; j++){
if(dp1[i - 1][j] == 1 and dp2[i + 1][k - j] == 1) wh[i] = 1;
}
}
// cout << dp1[0][0] << endl;
// cout << dp2[2][k] << endl;
int diff[N];
for(int i = 0; i <= n + 1; i++) diff[i] = 0;
for(int t = 0; t < k; t++){
int len = c[t];
for(int l = 1; l + len - 1 <= n; l++){
int r = l + len - 1;
if(pref[r] - pref[l - 1] != 0) continue;
if(l > 1 and s[l - 1] == 'X') continue;
if(r < n and s[r + 1] == 'X') continue;
if(dp1[l - 1][t] == 1 and dp2[r + 1][t + 1] == 1){
diff[l]++;
diff[r + 1]--;
}
}
}
int cur = 0;
for(int i = 1; i <= n; i++){
cur += diff[i];
if(cur) bl[i] = 1;
}
for(int i = 1; i < s.size(); i++){
if(s[i] != '.') bl[i] = 2;
}
// for(int i = 1; i <= n; i++){
// cout << bl[i] << " " << wh[i] << endl;
// }
string ans = "";
for(int i = 1; i < s.size(); i++){
if(bl[i] == 2 and wh[i] == 2) ans += s[i];
if(bl[i] == 1 and wh[i] == 0) ans += 'X';
if(bl[i] == 0 and wh[i] == 1) ans += '_';
if(bl[i] == 1 and wh[i] == 1) ans += '?';
}
return ans;
}
// signed main(){
// string s;
// cin >> s;
// int k;
// cin >> k;
// cout << s.size() << endl;
// vector<int> a(k);
// for(int i = 0; i < k; i++) cin >> a[i];
// cout << solve_puzzle(s, a);
// }
