#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
pair<vector<ll>, vector<ll>> calc_l(ll n, ll k, vector<ll> &v, vector<ll> &c){
ll j = 0, cnt = 0, lim = -1;
vector<ll> ans(n);
vector<ll> left_lim(n);
for(ll i = 0; i < n; i++){
if(cnt == c[j]) {ans[i] = ans[i-1] + 1, lim = (!v[i] ? i : lim), left_lim[i] = lim, cnt = 0, j++; continue;}
if(v[i]) cnt++;
else cnt = 0, lim = i;
ans[i] = (i ? ans[i-1] : 0);
left_lim[i] = lim;
}
return {ans, left_lim};
}
pair<vector<ll>, vector<ll>> calc_r(ll n, ll k, vector<ll> &v, vector<ll> &c){
ll j = k-1, cnt = 0, lim = n;
vector<ll> ans(n);
vector<ll> right_lim(n);
for(ll i = n-1; i >= 0; i--){
if(cnt == c[j]) {ans[i] = ans[i+1] + 1, lim = (!v[i] ? i : lim), right_lim[i] = lim, cnt = 0, j--; continue;}
if(v[i]) cnt++;
else cnt = 0, lim = i;
ans[i] = (i < n-1 ? ans[i+1] : 0);
right_lim[i] = lim;
}
return {ans, right_lim};
}
string solve_puzzle(string s, vector<int> c) {
ll n = s.size(), k = c.size();
vector<ll> v(n);
for(ll i = 0; i < n; i++) {
if(s[i] == '.') v[i] = 2;
else if(s[i] == '_') v[i] = 0;
else v[i] = 1;
}
auto[left_cnt, left_lim] = calc_l(n, k, v, c);
auto[right_cnt, right_lim] = calc_r(n, k, v, c);
string ans = s;
for(ll i = 0; i < n; i++){
if(s[i] != '.') continue;
bool white = (left_cnt[i] + right_cnt[i] >= k);
ll x = (left_lim[i] >= 0 ? left_cnt[left_lim[i]] : 0), y = (right_lim[i] < n ? right_cnt[right_lim[i]] : 0);
bool black = 0;
if(left_lim[i] == -1) black = (left_cnt[i] + (i < n-1 ? right_cnt[i+1] : 0));
if(right_lim[i] == n && !black) black = (right_cnt[i] + (i ? left_cnt[i-1] : 0));
if(x + y + 1 >= k){
for(ll j = 0; j < k; j++) if(j <= x && y >= k - j - 1 && right_lim[i] - left_lim[i] - 1 >= c[j]) black = 1;
}
if(!white) ans[i] = 'X';
else if(!black) ans[i] = '_';
else ans[i] = '?';
}
return ans;
}
