#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
const int N = 2e5 + 5, K = 100 + 5, INF = 1e9 + 5;
int n, k, forcedwhite[N], forcedblack[N], posprefix[K][N], isgood[K][N], white[N], black[N], closest[K][N];
bool pos[K][N];
void update(int arr[N], int l, int r){
arr[l]++, arr[r + 1]--;
}
string solve_puzzle(string s, vector<int> c) {
n = s.size(), k = c.size();
s = " " + s, c.insert(c.begin(), 0);
int firstx = INF;
for(int i = 1; i <= n; i++){
forcedblack[i] = forcedblack[i - 1];
forcedwhite[i] = forcedwhite[i - 1];
if(s[i] == 'X'){
forcedblack[i] = i;
if(firstx == INF) firstx = i;
}
else if(s[i] == '_') forcedwhite[i] = i;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= k; j++){
if((i + 1 > n || s[i + 1] != 'X') && i - c[j] + 1 >= 1 && forcedwhite[i] < i - c[j] + 1){
if((j == 1 && i - c[j] < firstx) || ((forcedblack[i - c[j]] <= i - c[j] - 1 && posprefix[j - 1][i - c[j] - 1] - (forcedblack[i - c[j]] == 0 ? 0 : posprefix[j - 1][forcedblack[i - c[j]] - 1])))){
pos[j][i] = true;
}
}
}
for(int j = 1; j <= k; j++) posprefix[j][i] = posprefix[j][i - 1] + pos[j][i];
}
for(int i = 1; i <= n; i++){
if(i < forcedblack[n]) pos[k][i] = false;
else if(pos[k][i]) isgood[k][i]++, isgood[k][i - 1]--;
posprefix[k][i] = posprefix[k][i - 1] + pos[k][i];
}
for(int i = 1; i <= k; i++) closest[i][n + 1] = INF;
for(int i = n; i >= 0; i--){
for(int j = 1; j <= k; j++){
if(pos[j][i]) closest[j][i] = i;
else closest[j][i] = closest[j][i + 1];
}
}
for(int i = n; i >= 1; i--){
for(int j = k; j >= 1; j--){
isgood[j][i] += isgood[j][i + 1];
if(isgood[j][i] && pos[j][i]){
update(black, i - c[j] + 1, i);
if(j == k && i < n) update(white, i + 1, n);
if(j == 1 && i - c[j] >= 1) update(white, 1, i - c[1]);
if(j != 1){
if(forcedblack[i - c[j]] <= i - c[j] - 1){
isgood[j - 1][i - c[j] - 1]++;
if(forcedblack[i - c[j]] != 0) isgood[j - 1][forcedblack[i - c[j]] - 1]--;
}
if(closest[j - 1][forcedblack[i - c[j]]] + 1 <= i - c[j]) update(white, closest[j - 1][forcedblack[i - c[j]]] + 1, i - c[j]);
}
}
}
}
for(int i = 1; i <= n; i++) white[i] += white[i - 1];
for(int i = 1; i <= n; i++) black[i] += black[i - 1];
string ans;
for(int i = 1; i <= n; i++){
if(s[i] == '.'){
if(black[i] != 0 && white[i] == 0) ans += 'X';
else if(white[i] != 0 && black[i] == 0) ans += '_';
else ans += '?';
}
else ans += s[i];
}
return ans;
}
