#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define pb push_back
#define se second
#define fr first
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
string S;
vector<int> C;
vector<pair<ll, ll>> rangs;
string cons(ll a, ll b, ll po)
{
ll i, tot = -1, dif, act, j, tam = rangs[po].se - rangs[po].fr + 1;
for (i = a; i <= b; i++)
{
tot++;
tot = tot + C[i];
}
dif = abs(tot - tam);
if (dif == 0)
{
string ans = "";
for (i = a; i <= b; i++)
{
if (i > a)
ans += "_";
string ag = "";
ag.resize(C[i], 'X');
ans += ag;
}
return ans;
}
string ret;
ret.resize(tam, 'X');
act = -1;
for (i = 0; i < min(dif, 1ll * tam - 1); i++)
ret[i] = '?';
for (i = a; i <= b; i++)
{
act++;
act = act + C[i];
if (act >= sz(ret))
break;
for (j = act; j <= min(act + dif, 1ll * tam - 1); j++)
ret[j] = '?';
}
return ret;
}
string un(string s, string x)
{
if (s[0] == '.')
return x;
for (ll i = 0; i < sz(s); i++)
if (s[i] != x[i])
s[i] = '?';
return s;
}
bool can(ll a, ll b, ll po)
{
ll i, tam = rangs[po].se - rangs[po].fr + 1, tot = 0, j = 0, act = 0;
if (a != -1)
{
for (i = a; i <= b; i++)
tot = tot + C[i];
tot = tot + (b - a);
if (tot > tam)
return 0;
}
for (i = 0; i < sz(S); i++)
{
if (j == a)
j = b + 1;
if(i==rangs[po].fr)
{
i=rangs[po].se;
continue;
}
if (j >= sz(C))
return 1;
if (S[i] == '.')
act++;
else
act = 0;
if (act == C[j])
{
act = 0;
j++;
i++;
}
}
if (j >= sz(C))
return 1;
return 0;
}
string calc(ll pos)
{
ll i, j, k;
string s=".";
if (can(-1, -1, pos))
{
string x;
x.resize(rangs[pos].se - rangs[pos].fr + 1, '_');
s = un(s, x);
}
for (i = 0; i < sz(C); i++)
{
for (j = i; j < sz(C); j++)
{
if (can(i, j, pos))
{
string x = cons(i, j, pos);
s = un(s, x);
}
}
}
return s;
}
std::string solve_puzzle(std::string s, std::vector<int> c)
{
S = s;
C = c;
ll i, in = 0, fin = 0, sig;
for (i = 0; i < sz(s); i++)
{
if (s[i] == '_')
{
if (in != i)
rangs.pb({in, fin - 1});
in = i + 1;
fin = in;
continue;
}
fin++;
}
if (in < sz(s))
rangs.pb({in, fin-1});
string ans = "";
sig=0;
for (i = 0; i < sz(rangs); i++)
{
while (sig < sz(s) && s[sig] == '_')
{
ans += "_";
sig++;
}
ans += calc(i);
sig = rangs[i].se + 1;
}
while (sig < sz(s) && s[sig] == '_')
{
ans += "_";
sig++;
}
return ans;
}
