#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
int n, k;
string s;
vector < int > c;
vector < int > cnt_, cntX;
vector < int > inc_, incX;
vector < vector < int > > memo;
bool has_(int l, int r)
{
r = min(r, n);
return cnt_[r] > cnt_[l];
}
bool hasX(int l, int r)
{
r = min(r, n);
return cntX[r] > cntX[l];
}
void set_(int l, int r)
{
inc_[l]++;
inc_[r]--;
}
void setX(int l, int r)
{
incX[l]++;
incX[r]--;
}
bool verifica(int i, int j)
{
if (j == k) if (!hasX(i, n))
{
set_(i, n);
return 1;
}
else return 0;
if (i >= n) return 0;
if (i + c[j] >= n) return 0;
if (memo[i][j] != -1) return memo[i][j];
bool ok = false;
if (!has_(i, i+c[j]) && s[i+c[j]] != 'X')
{
if (verifica(i+c[j]+1, j+1))
{
setX(i, i+c[j]);
set_(i+c[j], i+c[j]+1);
ok = true;
}
}
if (s[i] != 'X')
{
if (verifica(i+1, j))
{
set_(i, i+1);
ok = true;
}
}
//cerr << i << " " << j << " " << ok << "\n";
return memo[i][j] = ok;
}
std::string solve_puzzle(std::string ss, std::vector<int> cc)
{
s = ss;
s += "_";
c = cc;
n = s.size();
k = c.size();
memo.resize(n, vector < int > (k, -1));
cnt_.resize(n+1,0);
cntX.resize(n+1,0);
inc_.resize(n+1, 0);
incX.resize(n+1, 0);
for (int i = 1; i <= n; i++)
{
cnt_[i] = cnt_[i-1] + (s[i-1] == '_');
cntX[i] = cntX[i-1] + (s[i-1] == 'X');
}
string ans = "";
for (int i = 0; i < n; i++)
{
verifica(i, 0);
if (s[i] == 'X') break;
}
int cX=0, c_=0;
for (int i = 0; i < n-1; i++)
{
cX += incX[i];
c_ += inc_[i];
assert(cX || c_);
assert(cX >= 0);
assert(c_ >= 0);
if (!cX) ans += "_";
else if (!c_) ans += "X";
else ans += "?";
}
return ans;
}
