#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<bool> black(1 + n, false);
vector<bool> white(1 + n, false);
queue<pair<int, int> > q;
q.push(make_pair(n, k));
while(!q.empty()){
pair<int, int> x = q.front();
q.pop();
if(x.second == 0){
for(int j = 1; j <= x.first; j++){
white[j] = true;
}
continue;
}
if(x.first == c[x.second - 1]){
if(x.second == 1){
for(int j = x.first; j > 0; j--){
black[j] = true;
}
}
}
else if(x.first > c[x.second - 1] && dp[x.first - c[x.second - 1] - 1][x.second - 1]){
for(int j = x.first; j > x.first - c[x.second - 1]; j--){
black[j] = true;
}
white[x.first - c[x.second - 1]] = true;
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;
q.push(make_pair(x.first - 1, x.second));
}
}
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";
// }
