//#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
bool pos[200005][105];
string ans, s;
int last[200005], d[200005];
vector<int> v;
bool swapx(int i, int j){
if(i + 1 < v[j]){
return 0;
}
if(i >= v[j]){
if(s[i - v[j]] == 'X'){
return 0;
}
}
if(i - last[i] + 1 < v[j]){
return 0;
}
if(i >= v[j]) return pos[i - v[j]][j];
return pos[i - v[j] + 1][j];
}
bool go[200005][105];
void check(int n, int k){
if(go[n][k]){
return;
}
go[n][k] = 1;
if(k == 0){
d[1] ++;
d[n + 1] --;
return;
}
if(s[n - 1] == '_'){
check(n - 1, k);
} else if(s[n - 1] == 'X'){
d[n + 1] -= 200000;
d[n - v[k - 1] + 1] += 200000;
d[n - v[k - 1]]++;
d[n - v[k - 1] + 1]--;
check(n - v[k - 1] - 1, k - 1);
} else {
if(pos[n - 1][k]){
d[n] ++;
d[n + 1]--;
check(n - 1, k);
}
if((n == v[k - 1] || pos[n - v[k - 1] - 1][k - 1]) && n - last[n - 1] >= v[k - 1]){
if(ans[n - v[k - 1] - 1] == 'X') return;
d[n - v[k - 1]]++;
d[n - v[k - 1] + 1]--;
d[n + 1] -= 200000;
d[n - v[k - 1] + 1] += 200000;
check(n - v[k - 1] - 1, k - 1);
}
}
}
string solve_puzzle(string s, vector<int> v) {
::v = v;
::s = s;
last[0] = -1;
int n = v.size(), sz = s.size(), i, j;
for(int i = 1; i < sz; i++){
if(s[i - 1] == '_'){
last[i] = i;
} else {
last[i] = last[i - 1];
}
}
ans = s;
pos[0][0] = 1;
for(i = 1; i <= sz; i++){
if(s[i - 1] == 'X'){
break;
}
pos[i][0] = 1;
}
for(i = 1; i <= sz; i++){
for(j = 1; j <= n; j++){
if(i < v[j - 1]){
continue;
}
if(s[i - 1] == 'X'){
pos[i][j] = swapx(i - 1, j - 1);
} else if(s[i - 1] =='_'){
pos[i][j] = pos[i - 1][j];
} else {
pos[i][j] = (pos[i - 1][j] == 0 ? swapx(i - 1, j - 1) : 1);
}
// cout<<i<<" "<<j<<" "<<pos[i][j]<<"\n";
}
}
check(sz, n);
for(int i = 0; i < sz; i++){
d[i + 1] += d[i];
if(ans[i] == '.'){
if(d[i + 1] >= 200000){
if(d[i + 1] % 200000 != 0){
ans[i] = '?';
} else {
ans[i] = 'X';
}
} else {
ans[i] = '_';
}
}
}
return ans;
}
