#include <bits/stdc++.h>
#include "paint.h"
#define pb push_back
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 + 1; 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' and dp[i - 1][j]) dp[i][j] = 1;
if(j > 0){
int len = c[j - 1];
int L = i - len + 1;
if(L >= 1 and pref[i] - pref[L - 1] == 0){
if(L == 1){
if(j == 1) dp[i][j] = 1;
} else if(s[L - 1] != 'X'){
dp[i][j] |= dp[L - 2][j - 1];
}
}
}
}
}
}
string solve_puzzle(string s, vector<int> c1) {
n = s.size();
k = c1.size();
c = c1;
string s1 = " " + s;
pref[0] = 0;
for(int i = 1; i <= n; i++) pref[i] = pref[i - 1] + (s1[i] == '_' ? 1 : 0);
makedp(s1);
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= k; j++) dp1[i][j] = dp[i][j];
}
reverse(s.begin(), s.end());
s1 = " " + s;
reverse(c.begin(), c.end());
pref[0] = 0;
for(int i = 1; i <= n; i++) pref[i] = pref[i - 1] + (s1[i] == '_' ? 1 : 0);
makedp(s1);
for(int i = 0; i <= n + 1; i++){
for(int j = 0; j <= k; j++) dp2[i][j] = dp[n - i + 1][j];
}
reverse(c.begin(), c.end());
reverse(s.begin(), s.end());
s = " " + s;
for(int i = 1; i <= n; i++){
if(s[i] == 'X') continue;
for(int j = 0; j <= k; j++){
if(dp1[i - 1][j] and dp2[i + 1][k - j]) wh[i] = 1;
}
}
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;
}
string ans = "";
for(int i = 1; i <= n; i++){
if(bl[i] and wh[i]) ans += '?';
else if(bl[i]) ans += 'X';
else 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);
// }
