#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
typedef long long ll;
string solveSub(string s, vector<int> c, ll n1, ll n, ll k1, ll k) {
ll minLen = k-k1-1;
for (int i = k1; i < k; i++) minLen += c[i];
if (minLen > n-n1) return "-";
if (minLen <= 0) {
for (int i = n1; i < n; i++) {
s[i] = '_';
}
return s;
}
ll play = n-n1 - minLen;
ll pos = 0;
for (int i = k1; i < k; i++) {
for (int j = pos+play; j < pos+c[i]; j++) {
s[j] = 'X';
}
pos += c[i]+1;
}
for (int i = n1; i < n; i++) {
if (s[i] == '.') s[i] = minLen == n-n1 ? '_' : '?';
}
return s;
}
string solve_puzzle(string s, vector<int> c) {
ll n = s.size(), k = c.size();
vector<ll> spaces;
for (int i = 0; i < n; i++) {
if (s[i] == '_') spaces.push_back(i);
}
spaces.push_back(n);
ll m = spaces.size();
vector<vector<bool>> poss(m, vector<bool>(k+1));
vector<vector<string>> dp(m, vector<string>(k+1));
for (int i = 0; i < m; i++) {
poss[i][0] = true;
dp[i][0] = s;
for (int j = 0; j < spaces[i]; j++) {
dp[i][0][j] = '_';
}
}
for (int j = 1; j <= k && poss[0][j-1]; j++) {
dp[0][j] = solveSub(s, c, 0, spaces[0], 0, j);
poss[0][j] = dp[0][j][0] != '-';
}
for (int i = 1; i < m; i++) {
for (int j = 1; j <= k && poss[i][j-1]; j++) {
for (int p = 0; p <= j; p++) {
if (!poss[i-1][p]) continue;
string sol = solveSub(s, c, spaces[i-1]+1, spaces[i], p, j);
bool valid = sol[0] != '-';
if (valid) {
if (!poss[i][j]) {
dp[i][j] = dp[i-1][p];
for (int i1 = spaces[i-1]+1; i1 < spaces[i]; i1++) {
dp[i][j][i1] = sol[i1];
}
poss[i][j] = true;
}
else {
for (int i1 = 0; i1 < spaces[i-1]; i1++) {
if (dp[i-1][p][i1] == '?' || dp[i-1][p][i1] != dp[i][j][i1]) dp[i][j][i1] = '?';
}
for (int i1 = spaces[i-1]+1; i1 < spaces[i]; i1++) {
if (sol[i1] == '?' || sol[i1] != dp[i][j][i1]) dp[i][j][i1] = '?';
}
}
}
}
}
}
return dp[m-1][k];
}
