#include "paint.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 200010;
const int K = 110;
int pos[K];
bool isx[N];
int next_[N];
vector<int> len;
int n, k;
pair<bool, int> place(int l, int x, int len)
{
Loop (i,l,n-len+1) {
if (next_[i] < i+len || isx[i+len]) {
if (isx[i])
return {false, i};
else
continue;
}
if (x < i+len)
return {true, i};
}
return {false, -1};
}
int rem(int l)
{
Loop (i,l,n)
if (isx[i])
return i;
return -1;
}
string make_ans()
{
string s(n, '_');
Loop (i,0,k)
Loop (j,pos[i],pos[i]+len[i])
s[j] = 'X';
return s;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
n = s.size();
k = c.size();
len = c;
next_[n] = N;
LoopR (i,0,n) {
next_[i] = s[i] == '_'? i: next_[i+1];
isx[i] = s[i] == 'x' || s[i] == 'X';
}
int p = 0;
int px = -1;
for (;;) {
if (p == k) {
px = rem(pos[p]);
if (px == -1)
return make_ans();
else
--p;
}
bool suc; int val;
tie(suc, val) = place(pos[p], px, c[p]);
if (suc) {
pos[p] = val;
pos[p+1] = max(pos[p+1], val+c[p]+1);
++p;
} else {
assert(px != -1);
px = val;
--p;
}
}
}
