#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 3;
const int maxk = 101;
bitset<maxk> pref[maxn];
bitset<maxk> suf[maxn];
int prefSum[maxn];
int prefSumBlack[maxn];
int isWhiteGood[maxn];
string ans;
int n;
int k;
void addWhite(int l, int r){
isWhiteGood[l]++;
isWhiteGood[r + 1]--;
}
int getSum(int l, int r){
int res = prefSum[r];
if(l)res-=prefSum[l - 1];
return res;
}
int getSumBlack(int l, int r){
int res = prefSumBlack[r];
if(l)res-=prefSumBlack[l - 1];
return res;
}
bool canSuf(int sufNum, int need){
if(sufNum == n){
if(need == k)return 1;
else return 0;
}
if(need == k){
if(sufNum >= n)return 1;
int sufSum = getSumBlack(sufNum, n - 1);
if(sufSum)return 0;
else return 1;
}
if(sufNum >= n)return 0;
return suf[sufNum][need];
}
bool canPref(int prefNum, int need){
if(prefNum == -1){
if(need == 0)return 1;
else return 0;
}
if(need == 0){
if(prefNum <= -1)return 1;
int prefSum = getSumBlack(0, prefNum);
if(prefSum)return 0;
else return 1;
}
if(prefNum < 0)return 0;
return pref[prefNum][need - 1];
}
void solveBlack(string& s, string& ans){
for(int i = 0; i < s.size();i++){
if(s[i] != '.')continue;
bool can = 0;
for(int prefCnt = 0; prefCnt<= k;prefCnt++){
int sufCnt = prefCnt;
if(canPref(i - 1, prefCnt) && canSuf(i + 1, sufCnt)){
can = 1;
}
}
if(!can){
ans[i] = 'X';
}
}
}
bool putBlock(int l, int r, int j, string& s){
if(l){
if(s[l - 1] == 'X')return 0;
}
if(r != s.size() - 1){
if(s[r + 1] == 'X')return 0;
}
//cout << "MDA " << l << ' ' << r << ' ' << j << ' ' << canPref(l - 2, j) << ' ' << canSuf(r + 2, j + 1) << endl;
return ((canPref(l - 2, j) && canSuf(r + 2, j + 1)));
}
void solveWhite(string& s, vector<int>& c, string& ans){
for(int j = 0; j < c.size();j++){
for(int l = 0 ; l < s.size();l++){
int r = l + c[j] - 1;
if(r >= s.size())continue;
if(getSum(l, r))continue;
if(putBlock(l, r, j, s)){
addWhite(l, r);
//cout << "OPA " << l << ' ' << r << endl;
}
}
}
int nowSum = 0;
for(int i = 0; i < n;i++){
nowSum+=isWhiteGood[i];
if(s[i] != '.')continue;
//cout << i << ' ' << nowSum << endl;
if(nowSum == 0){
ans[i] = '_';
}
}
}
void calc_suf(vector<int>& c, string& s){
for(int i = s.size() - 1; i >= 0;i--){
for(int j = c.size() - 1; j >= 0;j--){
if(s[i] != 'X' && i != s.size() - 1)suf[i][j] = suf[i + 1][j];
int r = i + c[j] - 1;
if(r >= s.size())continue;
int sumOnSegm = getSum(i, r);
//cout << "SUF " << i << ' ' << j << ' ' << sumOnSegm << endl;
if(sumOnSegm)continue;
//cout << i << ' ' << j << endl;
if(j == c.size() - 1){
if(r == s.size() - 1){
suf[i][j] = 1;
}else{
if(getSumBlack(r + 1, s.size() - 1)!=0)continue;
else suf[i][j] = 1;
}
}else{
if(s[r + 1] == 'X')continue;
if(r + 2 < s.size()){
if(suf[r + 2][j + 1]){
suf[i][j] = 1;
}
}
}
}
}
}
void calc_pref(vector<int>& c, string& s){
for(int i = 0; i < s.size();i++){
for(int j = 0; j < c.size();j++){
if(s[i] != 'X' && i)pref[i][j] = pref[i - 1][j];
int l = i - c[j] + 1;
if(l < 0)continue;
int sumOnSegm = getSum(l, i);
if(sumOnSegm)continue;
if(j == 0){
if(l == 0){
pref[i][j] = 1;
}else{
if(prefSumBlack[l - 1] != 0)continue;
else pref[i][j] = 1;
}
}else{
if(s[l - 1] == 'X')continue;
if(l - 2 >= 0){
if(pref[l - 2][j - 1]){
pref[i][j] = 1;
}
}
}
}
}
}
string solve_puzzle(string s, vector<int> c) {
n = s.size();
k = c.size();
for(int i = 0; i < s.size();i++){
if(s[i] == '_'){
prefSum[i]++;
}
if(s[i] == 'X'){
prefSumBlack[i]++;
}
if(s[i] != '.'){
ans+= s[i];
}else{
ans+='?';
}
if(i){
prefSum[i] += prefSum[i - 1];
prefSumBlack[i] += prefSumBlack[i - 1];
}
}
calc_pref(c, s);
calc_suf(c, s);
solveBlack(s, ans);
solveWhite(s, c, ans);
// for(int i = 0; i < n;i++){
// cout << i << endl;
// for(int j = 0; j <= k;j++){
// cout << suf[i][j] << ' ';
// }
// cout << endl;
// }
return ans;
}
/*
..._..X._...
1
3
*/
