#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
typedef long long ll;
string solve(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 = n1;
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 solveSub(string s, vector<int> c, ll n1, ll n, ll k1, ll k) {
string orig = s;
ll minLen = max(0ll, k-k1-1);
for (int i = k1; i < k; i++) minLen += c[i];
if (minLen > n-n1) return "-";
vector<ll> blacks;
for (int i = n1; i < n; i++) {
if (s[i] == 'X') blacks.push_back(i);
}
blacks.push_back(n);
ll m = blacks.size();
if (minLen <= 0 && m > 1)
return "-";
else if (minLen <= 0) {
for (int i = n1; i < n; i++) {
s[i] = '_';
}
return s;
}
if (m == 1)
return solve(s, c, n1, n, k1, k);
ll play = n-n1 - minLen;
vector<ll> cOff(k-k1);
for (int i = 1; i < k-k1; i++) {
cOff[i] = cOff[i-1] + c[i+k1-1] + 1;
}
unordered_set<ll> idk;
bool has = false;
ll pos = n1;
ll curC = k-k1-1;
ll mid = (m-1)/2;
while (pos <= n1+play) {
while (curC >= 0 && cOff[curC] + pos > blacks[mid]) curC--;
if (curC < 0) break;
if (cOff[curC] + pos + c[curC+k1] <= blacks[mid]) { pos++; continue; }
ll low = cOff[curC] + pos;
ll high = low + c[curC+k1];
ll kL = curC;
ll kH = k-k1 - curC - 1;
ll hash = low | (high << 7) | (kL << 14) | (kH << 21);
idk.insert(hash);
has = true;
pos++;
}
if (!has)
return "-";
/*vector<vector<bool>> poss(m, vector<bool>(k-k1+1));
vector<vector<string>> dp(m, vector<string>(k-k1+1));
for (int i = 0; i < m; i++) {
poss[i][0] = true;
dp[i][0] = s;
for (int j = n1; j < blacks[i]; j++) {
dp[i][0][j] = '_';
}
}
for (int j = k1+1; j <= k && poss[0][j-1]; j++) {
dp[0][j] = solve(s, c, n1, blacks[0], k1, j);
poss[0][j] = dp[0][j][0] != '-';
}*/
string dummy = "";
bool f = false;
for (int i = 0; i < n; i++) dummy += s[i];
for (auto &e : idk) {
ll low = e & 127;
ll high = (e >> 7) & 127;
bool lo = low > n1, hi = high < n;
if (lo) low--;
if (hi) high++;
ll kL = (e >> 14) & 127;
ll kH = (e >> 21) & 127;
string sol = solveSub(dummy, c, n1, low, k1, k1+kL);
if (sol[0] == '-') continue;
sol = solveSub(sol, c, high, n, k-kH, k);
if (sol[0] == '-') continue;
if (lo) {
if (sol[low] == 'X') continue;
sol[low] = '_';
}
if (hi) {
if (sol[high-1] == 'X') continue;
sol[high-1] = '_';
}
for (int i1 = low+lo; i1 < high-hi; i1++) {
sol[i1] = 'X';
}
for (int i1 = n1; i1 < high; i1++) {
if (s[i1] == '.') s[i1] = sol[i1];
else if (sol[i1] == '?' || sol[i1] != s[i1]) s[i1] = '?';
}
for (int i1 = high; i1 < n; i1++) {
if (s[i1] == '.') s[i1] = sol[i1];
else if (sol[i1] == '?' || sol[i1] != s[i1]) s[i1] = '?';
}
f = true;
}
for (int i = n1; i < n; i++) {
if (orig[i] == s[i]) continue;
if (orig[i] == 'X')
s[i] = 'X';
if (orig[i] == '_')
s[i] = '_';
}
return f ? 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++) {
dp[i][0] = solveSub(s, c, 0, spaces[i], 0, 0);
poss[i][0] = dp[i][0][0] != '-';
}
for (int j = 1; j <= k; 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; 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];
}
