#include <bits/stdc++.h>
#include "paint.h"
#define K 120
#define N 200050
using namespace std;
int ini[K], fim[K], n, k, sz[K], cnt[N], global[N];
string ans;
int sum[N];
char v[N];
vector<int> pos[K];
void get_position()
{
for(int i = 1; i <= k; i++)
{
int st = ini[i - 1] + sz[i - 1] + 1;
while(true)
{
int en = st + sz[i] - 1;
if(sum[en] - sum[st - 1] > 0) st ++;
else break;
}
ini[i] = st;
}
fim[k + 1] = n + 2;
for(int i = k; i >= 1; i--)
{
int st = fim[i + 1] - sz[i] - 1;
while(true)
{
int en = st + sz[i] - 1;
if(sum[en] - sum[st - 1] > 0) st --;
else break;
}
fim[i] = st;
}
for(int i = 1; i <= k; i++)
{
for(int st = ini[i]; st <= fim[i]; st++)
{
int en = st + sz[i] - 1;
if(!(sum[en] - sum[st - 1])) pos[i].push_back(st);
}
}
}
string solve_puzzle(string s, vector<int> c)
{
n = s.size();
string ans = s;
k = c.size();
for(int i = 0; i < n ; i++)
{
v[i + 1] = s[i];
if(s[i] == '_') sum[i + 1] ++;
}
for(int i = 1; i <= n; i++) sum[i] += sum[i - 1];
for(int i = 1; i <= k; i++) sz[i] = c[i - 1];
get_position();
for(int i = 1; i <= k; i++)
{
memset(cnt, 0, sizeof cnt);
for(auto p: pos[i])
for(int j = p; j < p + sz[i]; j++) global[j] ++, cnt[j] ++;
for(int j = 1; j <= n; j++) if(cnt[j] == fim[i] - ini[i] + 1) ans[j - 1] = 'X';
}
for(int i = 1; i <= n; i++)
{
if(!global[i] && ans[i - 1] != 'X') ans[i - 1] = '_';
else if(ans[i - 1] == '.') ans[i - 1] = '?';
}
return ans;
}
