#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
int fr[110], to[110];
bool dp[200100][110];
int rEnd[110];
bool possBlack (int x, int y, string s) {
if (y < x || x < 0 || y >= (int)s.size())
return false;
FOR(i, x, y)
if (s[i] == '_')
return false;
return true;
}
bool possWhite (int x, int y, string s) {
if (y < x || x < 0 || y >= (int)s.size())
return false;
FOR(i, x, y)
if (s[i] == 'X')
return false;
return true;
}
bool possWhite (int x, string s) {
return possWhite(x, x, s);
}
bool isDp (int toId, int jId) {
if (jId < 0) return true;
if (toId < 0) return false;
FOR(i, 0, toId)
if (dp[i][jId])
return true;
return false;
}
bool endsAft (int i, int j, int k, int n){
if (j >= k) return true;
if (rEnd[j] >= i) return true;
else return false;
}
bool canWh[200100];
std::string solve_puzzle(std::string s, std::vector<int> c) {
string ret = s;
int n = (int)s.size();
int k = (int)c.size();
FOR(i, 0, k-1) fr[i] = 0, to[i] = n;
int cur = n;
for (int j = k-1; j >= 0; j--) {
cur -= c[j];
while (true) {
bool ok = true;
if (j < k-1 && !possWhite(cur+c[j], s)) ok = false;
if (j > 0 && !possWhite(cur-1, s)) ok = false;
if (!possBlack(cur, cur+c[j]-1, s)) ok = false;
if(ok) break;
else cur--;
}
rEnd[j] = cur;
cur--;
//cout <<" j = " << j << " rend = " << rEnd[j] << endl;
}
FOR(i, 0, n-1) FOR(j, 0, k-1) {
dp[i][j] = (j > 0 || i-c[j] < 0 || possWhite(0, i-c[j], s)) && (j < k-1 || i+1 > n-1 || possWhite(i+1, n-1, s)) &&
possBlack(i-c[j]+1, i, s) && (j == 0 || possWhite(i-c[j], i-c[j], s)) && isDp(i - c[j] - 1, j-1) && endsAft (i+2, j+1, k, n);
if (dp[i][j]) {
fr[j] = i - c[j] + 1;
if (to[j] == n) to[j] = i;
}
//cout << " i= " << i << " j =" << j << " dp[i][j] = " << dp[i][j] << endl;
}
// FOR(i, 0, k-1) cout << " i = " << i << " fr = " << fr[i] << " to = " << to[i] << endl;
FOR(i, 0, k-1) FOR(j, fr[i], to[i]) ret[j] = 'X';
FOR(i, 0, n-1) canWh[i] = true;
FOR(i, 0, n-1) FOR(j, 0, k-1) {
if (dp[i][j]) {
FOR(x, i - c[j]+1, i)
canWh[x] = false;
}
}
FOR(i, 0, n-1) if (canWh[i]) ret[i] = '_';
FOR(i, 0, n-1) if (ret[i] == '.') ret[i] = '?';
return ret;
}
