#include "paint.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
#include <cstdlib>
using namespace std;
ll dp[200005][105][2];
ll DP[200005][105][2];
ll mod[] = {998244353, 1000000007};
std::string solve_puzzle(std::string s, std::vector<int> c) {
int n = s.size(), k = c.size();
char ch[n + 2], a[k + 1], pref[n + 1];
ch[0] = ch[n + 1] = '.';
for(int i = 1; i<= n; i++){
ch[i] = s[i - 1];
}
for(int i = 1; i <= k; i++) a[i] = c[i - 1];
pref[0] = 0;
for(int i = 1; i <= n; i++){
pref[i] = pref[i - 1];
if(ch[i] == '_') pref[i]++;
}
dp[0][0][0] = dp[0][0][1] = 1;
DP[n + 1][k + 1][0] = DP[n + 1][k + 1][1] = 1;
for(int x = 0; x < 2; x++){
for(int i = 1; i <= n; i++){
for(int j = 0; j <= k; j++){
if(ch[i] != 'X') dp[i][j][x] += dp[i - 1][j][x];
if(j == 0) continue;
if(i < a[j]) continue;
int v = pref[i] - pref[i - a[j]];
if(v == 0 && ch[i - a[j]] != 'X'){
dp[i][j][x] += dp[max(0, i - a[j] - 1)][j - 1][x];
}
dp[i][j][x] %= mod[x];
}
}
}
for(int x = 0; x < 2; x++){
for(int i = n; i >= 1; i--){
for(int j = 1; j <= k + 1; j++){
if(ch[i] != 'X') DP[i][j][x] += DP[i + 1][j][x];
if(j == k + 1) continue;
if(i + a[j] - 1 > n) continue;
int v = pref[i + a[j] - 1] - pref[i - 1];
if(v == 0 && ch[i + a[j]] != 'X'){
DP[i][j][x] += DP[min(n + 1, i + a[j] + 1)][j + 1][x];
}
DP[i][j][x] %= mod[x];
}
}
}
ll sum[n + 2][2];
for(int i = 0; i <= n + 1; i++) sum[i][0] = sum[i][1] = 0;
for(int x = 0; x < 2; x++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= k; j++){
if(i < a[j]) continue;
if(ch[i - a[j]] != 'X' && ch[i + 1] != 'X'){
if(pref[i] - pref[i - a[j]]) continue;
ll val = dp[max(i - a[j] - 1, 0)][j - 1][x] * DP[min(i + 2, n + 1)][j + 1][x];
val %= mod[x];
int l = i - a[j] + 1, r = i + 1;
sum[l][x] += val;
sum[l][x] %= mod[x];
sum[r][x] -= val;
sum[r][x] += mod[x];
sum[r][x] %= mod[x];
}
}
}}
/*for(int i = 1; i <= n; i++){
for(int j = 0; j <= k; j++){
cout << dp[i][j] << ' ';
}
cout << "\n";
}*/
string ans = "";
ll cursum = sum[0][0];
ll cursum1 = sum[0][1];
for(int i = 1; i <= n; i++){
cursum += sum[i][0];
cursum1 += sum[i][1];
cursum %= mod[0]; cursum += mod[0]; cursum %= mod[0];
cursum1 %= mod[1]; cursum1 += mod[1]; cursum1 %= mod[1];
if(cursum == 0 && cursum1 == 0) {ans += '_'; continue;}
if((cursum == dp[n][k][0]) && (cursum1 == dp[n][k][1])){ans += 'X'; continue;}
ans += '?';
}
return ans;
}
