#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
ll dp[200200][110];
ll pref[200200][110];
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);
for(ll i = 0; i < n; i++){
for(ll j = 0; j < k; j++){
dp[i][j] = (i+1 >= c[j] && (left_lim[i] < i - c[j] + 1) && s[i - c[j]] != 'X' && (j == 0 || pref[i - c[j] - 1][j]));
// cout << dp[i][j] << " ";
pref[i+1][j+1] = pref[i][j+1] + dp[i][j];
}
// cout << "\n";
}
string ans = s;
for(ll i = 0; i < n; i++){
if(s[i] != '.') continue;
bool white = (left_cnt[i] + right_cnt[i] >= k);
bool black = 0;
for(ll j = 0; j < k; j++) if(pref[i + c[j]][j+1] - pref[i][j+1]) black = 1;
if(!white) ans[i] = 'X';
else if(!black) ans[i] = '_';
else ans[i] = '?';
}
return ans;
}
