#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int N, K;
char S[maxn];
int C[maxn], psum1[maxn], psum2[maxn], chk[maxn][2];
int sum[111][maxn];
int calc(int l, int r, int *psum) {
if(l > r) return 0;
return psum[r] - (l? psum[l - 1] : 0);
}
int cc1[maxn][111];
int dp1(int x, int k) {
if(x == 0) return k == 0;
int &ret = cc1[x][k];
if(ret != -1) return ret;
if(S[x] == 'X') return ret = 0;
ret = 0;
ret |= dp1(x - 1, k);
if(k && x - C[k] >= 1 && calc(x - C[k], x - 1, psum2) == 0) {
ret |= dp1(x - C[k] - 1, k - 1);
}
return ret;
}
int cc2[maxn][111];
int dp2(int x, int k) {
if(x == N + 1) return k == K + 1;
int &ret = cc2[x][k];
if(ret != -1) return ret;
if(S[x] == 'X') return ret = 0;
ret = 0;
ret |= dp2(x + 1, k);
if(k <= K && x + C[k] <= N && calc(x + 1, x + C[k], psum2) == 0) {
ret |= dp2(x + C[k] + 1, k + 1);
}
return ret;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
N = s.size();
K = c.size();
for(int i = 1; i <= N; i++) {
S[i] = s[i - 1];
}
for(int i = 1; i <= K; i++) {
C[i] = c[i - 1];
}
for(int i = 1; i <= N; i++) {
psum1[i] = S[i] == 'X';
psum2[i] = S[i] == '_';
psum1[i] += psum1[i - 1];
psum2[i] += psum2[i - 1];
}
memset(cc1, -1, sizeof(cc1));
memset(cc2, -1, sizeof(cc2));
for(int i = 1; i <= N; i++) {
if(S[i] == 'X') chk[i][1] = 1;
if(S[i] == '_') chk[i][0] = 1;
}
for(int i = 1; i <= N; i++) if(S[i] == '.') {
for(int j = 0; j <= K; j++) {
if(dp1(i, j) & dp2(i, j + 1)) {
chk[i][0] = 1;
break;
}
}
}
for(int i = 1; i <= K; i++) {
for(int j = 0; j <= N - C[i]; j++) {
sum[i][j] = dp1(j, i - 1) & dp2(j + C[i] + 1, i + 1) & calc(j + 1, j + C[i], psum2) == 0;
}
for(int j = 1; j <= N + 1; j++) {
sum[i][j] += sum[i][j - 1];
}
}
for(int i = 1; i <= N; i++) if(S[i] == '.') {
for(int j = 1; j <= K; j++) {
if(calc(max(0, i - C[j]), i - 1, sum[j])) {
chk[i][1] = 1;
break;
}
}
}
string ret;
for(int i = 1; i <= N; i++) {
if(chk[i][1] == chk[i][0]) ret.push_back('?');
else if(chk[i][1]) ret.push_back('X');
else ret.push_back('_');
}
return ret;
}
