#include "paint.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <ll,ll> pi;
typedef vector <int> vec;
const ll INF = 1e18;
char s[200005];
int a[200005],pwh[200005],pbl[200005],canbl[105][200005],canbr[105][200005];
int n,k,canX[200005];
bool can_[200005];
string solve_puzzle(string S,vec c) {
n = S.length(), k = c.size();
for(int i = 0;i < n;i++) {
s[i+1] = S[i];
pwh[i+1] = pwh[i]+(s[i+1] == '_');
pbl[i+1] = pbl[i]+(s[i+1] == 'X');
}
canbl[0][0] = 1;
for(int i = 0;i < k;i++) a[i+1] = c[i];
for(int i = 0;i <= k;i++) {
if(i == 1) {
for(int j = 0;j <= n+1;j++) canbl[i][j] = 0;
for(int j = a[i];j <= n;j++) if(pbl[j-a[i]] == 0&&pwh[j] == pwh[j-a[i]]) canbl[i][j] = 1;
}
for(int j = 0;j <= n;j++) {
//cout << canbl[i][j] << ' ';
if(canbl[i][j]&&s[j+1] != 'X') {
canbl[i][j+1] = 1;
if(i == k||i == 0) continue;
if(j+a[i+1]+(i>0) <= n&&pwh[j+a[i+1]+(i>0)] == pwh[j+(i>0)]) canbl[i+1][j+a[i+1]+(i>0)] = 1;
}
}
//cout << '\n';
}
//cout << '\n';
canbr[k+1][n+1] = 1;
for(int i = k+1;i >= 1;i--) {
if(i == k) {
for(int j = 0;j <= n+1;j++) canbr[i][j] = 0;
for(int j = n-a[i]+1;j >= 1;j--) if(pbl[j+a[i]-1] == pbl[n]&&pwh[j-1] == pwh[j+a[i]-1]) canbr[i][j] = 1;
}
for(int j = n+1;j >= 1;j--) {
//cout << canbr[i][j] << ' ';
if(canbr[i][j]&&s[j-1] != 'X') {
canbr[i][j-1] = 1;
if(i == 1||i == k+1) continue;
if(j-a[i-1]-(i<k+1) >= 1&&pwh[j-a[i-1]-(i<k+1)-1] == pwh[j-1-(i<k+1)]) canbr[i-1][j-a[i-1]-(i<k+1)] = 1;
}
}
//cout << '\n';
}
for(int i = 1;i <= n;i++) {
for(int j = 0;j <= k;j++) {
if(canbl[j][i-1]&&canbr[j+1][i+1]&&s[i] != 'X') can_[i] = 1;
}
//cout << i << ' ' << can_[i] << '\n';
}
for(int i = 1;i <= k;i++) {
for(int j = a[i];j <= n;j++) {
bool bl,br;
if(j-a[i] <= 0) bl = (i == 1);
else bl = (canbl[i-1][j-a[i]-1]&&s[j-a[i]] != 'X');
if(j == n) br = (i == k);
else br = (canbr[i+1][j+2]&&s[j+1] != 'X');
if(bl&&br&&pwh[j] == pwh[j-a[i]]) canX[j-a[i]+1]++, canX[j+1]--;
}
}
for(int i = 1;i <= n;i++) canX[i] += canX[i-1];//, cout<< canX[i] << ' ';
// cout << '\n';
string ans;
for(int i = 1;i <= n;i++) {
if(s[i] != '.') ans += s[i];
else if(canX[i]&&can_[i]) ans += '?';
else if(canX[i]) ans += 'X';
else if(can_[i]) ans += '_';
else while(1);// cout << i << ' ' << "WTF\n";
}
return ans;
}
