#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 2e5 + 5;
const int K = 100 + 5;
int n, k;
string s;
vector<int> c;
string ans;
int event[N];
int preW[N], preB[N];
int dpL[N][K], dpR[N][K];
int fL(int x, int i) {
if(x <= 0) {
return !i;
}
if(!i) {
return preB[x] == 0;
}
if(x < c[i]) {
return 0;
}
int &r = dpL[x][i];
if(r != -1) {
return r;
}
r = 0;
if(s[x] != 'X') {
r |= fL(x - 1, i);
}
if(preW[x] - preW[x - c[i]] == 0 and (x - c[i] == 0 or s[x - c[i]] != 'X')) {
r |= fL(x - c[i] - 1, i - 1);
}
return r;
}
int fR(int x, int i) {
if(x > n) {
return i == k + 1;
}
if(i > k) {
return preB[n] - preB[x - 1] == 0;
}
if(x + c[i] - 1 > n) {
return 0;
}
// if(x == 8 and i == 2) {
// printf("c[%d] = %d n = %d\n", i, c[i], n);
// puts("ASD");
// }
int &r = dpR[x][i];
if(r != -1) {
return r;
}
r = 0;
if(s[x] != 'X') {
r |= fR(x + 1, i);
}
if(preW[x + c[i] - 1] - preW[x - 1] == 0 and (x + c[i] == n + 1 or s[x + c[i]] != 'X')) {
r |= fR(x + c[i] + 1, i + 1);
}
return r;
}
void solve() {
memset(dpL, -1, sizeof dpL);
memset(dpR, -1, sizeof dpR);
n = s.size();
k = c.size();
s = "#" + s;
c.insert(c.begin(), 0);
for(int i = 1; i <= n; i++) {
preB[i] = preB[i - 1] + (s[i] == 'X');
preW[i] = preW[i - 1] + (s[i] == '_');
}
ans = string(n + 1, '?');
// for(int i = 1; i <= n; i++) {
// for(int j = 1; j <= k; j++) {
// printf("fL(%d, %d) = %d fR(%d, %d) = %d\n", i, j, fL(i, j), i, j, fR(i, j));
// }
// }
for(int i = 1; i <= n; i++) {
if(s[i] != '.') {
ans[i] = s[i];
continue;
}
bool flag = false;
for(int j = 0; j <= k; j++) {
if(fL(i - 1, j) and fR(i + 1, j + 1)) {
// printf("i = %d j = %d\n", i, j);
flag = true;
break;
}
}
if(!flag) {
// printf("assign x to %d\n", i);
ans[i] = 'X';
}
}
// puts(ans.substr(1).c_str());
for(int j = 1; j <= k; j++) {
for(int i = 1; i + c[j] - 1 <= n; i++) {
if(preW[i + c[j] - 1] - preW[i - 1] == 0 and (i + c[j] == n + 1 or s[i + c[j]] != 'X') and (i == 1 or s[i - 1] != 'X')) {
if(fL(i - 2, j - 1) and fR(i + c[j] + 1, j + 1)) {
// printf("with %d [%d, %d] could be done\n", j, i, i + c[j] - 1);
event[i]++;
event[i + c[j]]--;
}
}
}
}
for(int i = 1; i <= n; i++) {
event[i] += event[i - 1];
// printf("event[%d] = %d\n", i, event[i]);
if(ans[i] == '?') {
if(event[i] > 0) {
ans[i] = '?';
} else {
ans[i] = '_';
}
}
}
}
string solve_puzzle(string S, vector<int> C) {
s = S;
c = C;
solve();
ans = ans.substr(1);
return ans;
}
