#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
#include <bitset>
#include "paint.h"
using namespace std;
#define ll long long
//cin.tie(0);ios_base::sync_with_stdio(0);
const int MAXN = 2 * 1e5 + 5, MAXK = 105;
bool dp[MAXN][MAXK];
int preW[MAXN];
int preB[MAXN];
string s;
vector<int> c;
bool canX[MAXN], canY[MAXN];
bool vis[MAXN][MAXK];
void backtrack(int i, int j) {
if (vis[i][j]) {
return;
}
vis[i][j] = true;
if (s[i] != 'X' && dp[i - 1][j]) {
//dp[i][j] = dp[i - 1][j];
backtrack(i - 1, j);
canY[i] = true;
}
if (i - c[j] - 1 >= 0) {
if (preW[i] == preW[i - c[j]] && s[i - c[j]] != 'X' && dp[i - c[j] - 1][j - 1]) {
//dp[i][j] |= dp[i - c[j] - 1][j - 1];
backtrack(i - c[j] - 1, j - 1);
for (int k = i - c[j] + 1; k <= i; k++) {
canX[k] = true;
}
canY[i - c[j]] = true;
}
}
if (i - c[j] == 0 && j == 1) {
if (preW[i] == preW[i - c[j]] && s[i - c[j]] != 'X') {
//dp[i][j] = true;
for (int k = i - c[j] + 1; k <= i; k++) {
canX[k] = true;
}
canY[i - c[j]] = true;
}
}
}
string solve_puzzle(string S, vector<int> C) {
s = S;
c = C;
int n = s.size();
s = '*' + s;
int m = c.size();
c.insert(c.begin(), 0);
for (int i = 1; i <= n; i++) {
preW[i] = preW[i - 1];
preB[i] = preB[i - 1];
if (s[i] == '_') {
preW[i]++;
}
if (s[i] == 'X') {
preB[i]++;
}
}
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if(s[i] != 'X')
dp[i][j] = dp[i - 1][j];
if (i - c[j] - 1 >= 0) {
if(preW[i] == preW[i - c[j]] && s[i - c[j]] != 'X')
dp[i][j] |= dp[i - c[j] - 1][j - 1];
}
if (i - c[j] == 0 && j == 1) {
if (preW[i] == preW[i - c[j]] && s[i - c[j]] != 'X')
dp[i][j] = true;
}
}
}
/*for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << dp[i][j] << " ";
}
cout << endl;
}*/
if (dp[n][m]) {
backtrack(n, m);
}
string ans = "";
for (int i = 1; i <= n; i++) {
if (canX[i] && canY[i]) {
ans += '?';
}
else if (canX[i]) {
ans += 'X';
}
else {
ans += '_';
}
}
return ans;
}
