#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#include "paint.h"
const int K = 110;
const int N = 200010;
bool pref[N][K][2], suf[N][K][2];
int w[N], canW[N], canB[N];
string solve_puzzle(string s, vector<int> c){
int n = sz(s);
s = '.' + s;
int k = sz(c);
vector<int>v;
v.push_back(0);
for(auto it : c)v.push_back(it);
for(int i = 1; i <= n; i++){
w[i] = w[i - 1] + (s[i] == '_');
}
pref[0][0][0] = pref[0][0][1] = 1;
suf[n + 1][k + 1][0] = suf[n + 1][k + 1][1] = 1;
//prefix
for(int j = 0; j <= k; j++){
for(int i = 1; i <= n; i++){
if(s[i] == '_' || s[i] == '.'){
pref[i][j][0] = pref[i - 1][j][1];
pref[i][j][1] = pref[i - 1][j][1];
}
if(j == 0 || i - v[j] < 0 || (w[i] - w[i - c[j]]) != 0) continue;
if(s[i] == 'X' || s[i] == '.'){
pref[i][j][1] = pref[i][j][1] || pref[i - v[j]][j - 1][1];
}
}
}
//sufix
for(int j = k + 1; j >= 1; j--){
for(int i = n; i >= 1; i--){
if(s[i] == '_' || s[i] == '.'){
suf[i][j][0] = suf[i + 1][j][1];
suf[i][j][1] = suf[i + 1][j][1];
}
if(j == k + 1 || i + v[j] - 1 > n || (w[i + v[j] - 1] - w[i - 1]) != 0) continue;
if(s[i] == 'X' || s[i] == '.'){
suf[i][j][1] = suf[i][j][1] || suf[i + v[j]][j + 1][1];
}
}
}
//which positions can be white
for(int i = 1; i <= n; i++){
for(int j = 0; j <= k; j++){
if(pref[i - 1][j][1] && suf[i + 1][j + 1][1])canW[i] = 1;
}
}
//which positions can be black #BlackPositionsMatter
for(int j = 1; j <= k; j++){
for(int r = 1; r <= n; r++){
int l = r - v[j] + 1;
if(l <= 0 || w[r] - w[l - 1] != 0)continue;
if(pref[l - 1][j - 1][0] && suf[r + 1][j + 1][0]){
canB[l]++;
canB[r + 1]--;
}
}
}
for(int i = 1; i <= n; i++){
canB[i] += canB[i - 1];
}
string ans = "";
for(int i = 1; i <= n; i++){
if(s[i] != '.'){
ans += s[i];
continue;
}
if(canW[i] && canB[i])ans += '?';else
if(canW[i])ans += '_';else ans += 'X';
}
return ans;
}
