#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], qtd[N], forb[N];
char v[N];
vector<int> pos[K], pos2[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);
}
}
}
void count()
{
for(int en = 1; en <= n; en ++)
{
if(v[en] != 'X') continue;
int st = en, cnt = 0, id;
while(v[en] == 'X') en ++;
en --;
for(int i = 1; i <= k; i++)
{
bool can = false;
for(auto p: pos[i])
{
if(p <= st && en < p + sz[i])
{
can = true;
id = i;
}
}
if(can) cnt ++;
}
if(cnt == 1)
{
forb[id] = 1;
for(auto p: pos[id])
{
if(p <= st && en < p + sz[id]) pos2[id].push_back(p);
}
}
}
}
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();
count();
for(int i = 1; i <= k; i++)
{
memset(cnt, 0, sizeof cnt);
int tam = 0;
if(!forb[i])
{
for(auto p: pos[i])
for(int j = p; j < p + sz[i]; j++) global[j] ++, cnt[j] ++;
tam = pos[i].size();
}
else
{
for(auto p: pos2[i])
for(int j = p; j < p + sz[i]; j++) global[j] ++, cnt[j] ++;
tam = pos2[i].size();
}
for(int j = 1; j <= n; j++) if(cnt[j] == tam) 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;
}
