#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
string solve_puzzle(string s, vector<int> c){
int n = (int)s.size();
int k = (int)c.size();
vector<vector<bool> > dp(1 + n, vector<bool>(1 + k, false));
dp[0][0] = true;
for(int j = 1; j <= n; j++){
dp[j][0] = true;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= k; j++){
if(s[i - 1] == 'X'){
if(i == c[j - 1]){
if(j == 1){
dp[i][j] = true;
}
}
if(i > c[j - 1] && dp[i - c[j - 1] - 1][j - 1]){
dp[i][j] = true;
}
}
else if(s[i - 1] == '_'){
if(dp[i - 1][j]){
dp[i][j] = true;
}
}
else{
if(i == c[j - 1]){
if(j == 1){
dp[i][j] = true;
}
}
else if(i > c[j - 1] && dp[i - c[j - 1] - 1][j - 1]){
dp[i][j] = true;
}
if(dp[i - 1][j]){
dp[i][j] = true;
}
}
}
}
vector<vector<bool> > visited(1 + n, vector<bool>(1 + k, false));
vector<bool> black(1 + n, false);
vector<bool> white(1 + n, false);
queue<pair<int, int> > q;
q.push(make_pair(n, k));
vector<int> maxVal(1 + n, 0);
int thing = 0;
while(!q.empty()){
pair<int, int> x = q.front();
q.pop();
visited[x.first][x.second] = true;
if(x.second == 0){
thing = max(thing, x.first);
continue;
}
if(x.first == c[x.second - 1]){
if(x.second == 1){
maxVal[1] = max(maxVal[1], x.first);
}
}
else if(x.first > c[x.second - 1] && dp[x.first - c[x.second - 1] - 1][x.second - 1]){
maxVal[x.first - c[x.second - 1] + 1] = max(maxVal[x.first - c[x.second - 1] + 1], x.first);
white[x.first - c[x.second - 1]] = true;
if(!visited[x.first - c[x.second - 1] - 1][x.second - 1]){
q.push(make_pair(x.first - c[x.second - 1] - 1, x.second - 1));
}
}
if(x.first >= 1 && dp[x.first - 1][x.second]){
white[x.first] = true;
if(!visited[x.first - 1][x.second]){
q.push(make_pair(x.first - 1, x.second));
}
}
}
set<int> maxVals;
for(int i = 1; i <= n; i++){
if(maxVal[i] != 0){
maxVals.insert(maxVal[i]);
}
if(!maxVals.empty()){
black[i] = true;
}
while(!maxVals.empty()){
auto it = maxVals.begin();
if((*it) != i){
break;
}
else{
maxVals.erase(it);
}
}
}
for(int j = 1; j <= thing; j++){
white[j] = true;
}
string res = "";
for(int i = 1; i <= n; i++){
if(black[i] && white[i]){
res += "?";
}
else if(black[i]){
res += "X";
}
else{
res += "_";
}
}
return res;
}
// int main(){
// string s;
// cin >> s;
// int k;
// cin >> k;
// vector<int> c(k);
// for(int i = 0; i < k; i++){
// cin >> c[i];
// }
// cout << solve_puzzle(s, c) << "\n";
// }
