#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int N, K, t[200009][3], v1[200009], v2[200009];
bool dpl[200009][109][2], dpr[200009][109][2];
int ranged(int l, int r, int x) {
return t[r + 1][x] - t[l][x];
}
string solve_puzzle(string s, vector<int> c) {
N = s.size(); K = c.size();
for (int i = 0; i < N; i++) {
if (s[i] == '_') t[i + 1][0]++;
if (s[i] == 'X') t[i + 1][1]++;
if (s[i] == '?') t[i + 1][2]++;
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 3; j++) t[i][j] += t[i - 1][j];
}
dpl[0][0][0] = true;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= K; j++) {
if (dpl[i - 1][j][0] == true && s[i - 1] != 'X') dpl[i][j][0] = true;
if (dpl[i - 1][j][1] == true && s[i - 1] != 'X') dpl[i][j][0] = true;
if (j >= 0 && i >= c[j - 1] && dpl[i - c[j - 1]][j - 1][0] == true && ranged(i - c[j - 1], i - 1, 0) == 0) dpl[i][j][1] = true;
}
}
dpr[N][K][0] = true;
for (int i = N - 1; i >= 0; i--) {
for (int j = 0; j <= K; j++) {
if (dpr[i + 1][j][0] == true && s[i] != 'X') dpr[i][j][0] = true;
if (dpr[i + 1][j][1] == true && s[i] != 'X') dpr[i][j][0] = true;
if (j < K && i + c[j] <= N && dpr[i + c[j]][j + 1][0] == true && ranged(i, i + c[j] - 1, 0) == 0) dpr[i][j][1] = true;
}
}
for (int i = 0; i < N; i++) {
bool p1 = false;
for (int j = 0; j <= K; j++) {
if (s[i] == 'X') continue;
if ((dpl[i][j][0] == false && dpl[i][j][1] == false) || dpl[i + 1][j][0] == false) continue;
if ((dpr[i + 1][j][0] == false && dpr[i + 1][j][1] == false) || dpr[i][j][0] == false) continue;
p1 = true; break;
}
for (int j = 0; j < K; j++) {
if (s[i] == '_') continue;
if (i + 1 < c[j] || dpl[i - c[j] + 1][j][0] == false || dpl[i + 1][j + 1][1] == false) continue;
if (i + 1 < c[j] || dpr[i - c[j] + 1][j][1] == false || dpr[i + 1][j + 1][0] == false) continue;
v2[i - c[j] + 1] += 1;
v2[i + 1] -= 1;
}
if (p1 == true) v1[i] = 1;
}
for (int i = 1; i <= N + 1; i++) v2[i] += v2[i - 1];
string str = "";
for (int i = 0; i < N; i++) {
if (v1[i] >= 1 && v2[i] >= 1) str += '?';
if (v1[i] >= 1 && v2[i] == 0) str += '_';
if (v1[i] == 0 && v2[i] >= 1) str += 'X';
if (v1[i] == 0 && v2[i] == 0) str += 'A';
}
return str;
}
