#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
string s_;
bool canBeWhite(int idx){
if(s_[idx - 1] == '_' || s_[idx - 1] == '.'){
return true;
}
else{
return false;
}
}
bool cannotBeBlack(int idx){
if(s_[idx - 1] == '_'){
return true;
}
else{
return false;
}
}
string solve_puzzle(string s, vector<int> c){
int n = (int)s.size();
int k = (int)c.size();
s_ = s;
vector<vector<bool> > dp(1 + n, vector<bool>(1 + k, false));
vector<int> pref(1 + n, 0);
for(int i = 1; i <= n; i++){
if(cannotBeBlack(i)){
pref[i] = pref[i - 1] + 1;
}
else{
pref[i] = pref[i - 1];
}
}
vector<int> pref2(1 + n, 0);
for(int i = 1; i <= n; i++){
if(!canBeWhite(i)){
pref2[i] = pref2[i - 1] + 1;
}
else{
pref2[i] = pref2[i - 1];
}
}
for(int i = 0; i <= n; i++){
if(pref2[i] == 0){
dp[i][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 && pref[i] == 0){
dp[i][j] = true;
}
}
if(i > c[j - 1] && dp[i - c[j - 1] - 1][j - 1]){
if(pref[i] == pref[i - c[j - 1]] && canBeWhite(i - c[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 && pref[i] == 0){
dp[i][j] = true;
}
}
if(i > c[j - 1] && dp[i - c[j - 1] - 1][j - 1]){
if(pref[i] == pref[i - c[j - 1]] && canBeWhite(i - c[j - 1])){
dp[i][j] = true;
}
}
if(canBeWhite(i) && 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));
visited[n][k] = true;
vector<int> maxVal(1 + n, 0);
int thing = 0;
while(!q.empty()){
pair<int, int> x = q.front();
q.pop();
if(x.second == 0){
if(pref2[x.first] == 0){
thing = max(thing, x.first);
}
continue;
}
if(x.first == c[x.second - 1]){
if(x.second == 1 && pref[x.first] == 0){
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]){
if(pref[x.first] == pref[x.first - c[x.second - 1]] && canBeWhite(x.first - c[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));
visited[x.first - c[x.second - 1] - 1][x.second - 1] = true;
}
}
}
if(x.first >= 1 && dp[x.first - 1][x.second]){
if(canBeWhite(x.first)){
white[x.first] = true;
if(!visited[x.first - 1][x.second]){
q.push(make_pair(x.first - 1, x.second));
visited[x.first - 1][x.second] = true;
}
}
}
}
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";
// }
