#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
const int K = 105;
vector <int> c(K), minNeedLen(K, 0);
vector <set <char> > chars(N);
string s;
int n, k;
void solve(int idx, string&cur) {
int pos = cur.size();
if (pos > n+1) return;
// cout << cur << '\n';
if (pos == n+1) {
if (idx <= k) return;
// cout << cur << '\n';
for (int i = 1; i <= n; i++) {
chars[i].insert((cur[i] == 'X' ? 'X' : '_'));
}
return;
}
if (pos + minNeedLen[idx] - 1 > n || pos > n) {
return;
}
if (idx == k+1 && pos < n+1) {
int tmp = n+1 - pos;
for (int i = 0; i < tmp; i++) {
if (s[pos + i] == 'X') return;
}
for (int i = 0; i < tmp; i++) cur.push_back('_');
solve(idx, cur);
for (int i = 0; i < tmp; i++) cur.pop_back();
return;
}
if (s[pos] != 'X') {
cur.push_back('_');
solve(idx, cur);
cur.pop_back();
}
for (int i = pos; i < pos + c[idx]; i++) {
if (s[i] == '_') {
// cout << pos << ' ' << idx << ' ' << cur << '\n';
return;
}
}
int tmp = c[idx];
for (int i = 0; i < tmp; i++) {
cur.push_back('X');
}
if (idx != k)
cur.push_back('_');
solve(idx+1, cur);
if (idx != k)
cur.pop_back();
for (int i = 0; i < tmp; i++) {
cur.pop_back();
}
}
string solve_puzzle(string s1, vector<int> c1) {
n = s1.size(), k = c1.size();
s = 'A' + s1 + 'A';
vector <int> c(k+5, 0);
for (int i = 1; i <= k; i++) c[i] = c1[i-1];
string ans = "";
for (int i = 0; i < n+2; i++) {
ans += '?';
}
for (int i = 1; i <= n; i++) {
if (s[i-1] != '.') ans[i] = s[i-1];
}
vector <int> pre(k+5, 1), suf(k + 5, n);
vector <int> white(1, 0), black;
if (!black.empty()) {
for (int i = k; i >= 1; i--)
minNeedLen[i] = c[i] + (i < k ? minNeedLen[i+1]+1 : 0);
string cur = "A";
solve(1, cur);
for (int i = 1; i <= n; i++) {
if (chars[i].size() != 1) ans[i] = '?';
else ans[i] = *chars[i].begin();
}
ans = ans.substr(1, n);
return ans;
}
for (int i = 0; i < n; i++) {
if (s[i] == '_') white.push_back(i+1);
if (s[i] == 'X') black.push_back(i+1);
}
white.push_back(n+1);
for (int i = 1; i < white.size(); i++) {
int len = white[i] - white[i-1] - 1;
if (len < c[1]) {
continue;
}
pre[1] = white[i-1]+1;
break;
}
for (int i = white.size()-1; i > 0; i--) {
int len = white[i] - white[i-1] - 1;
if (len < c[k]) continue;
suf[k] = white[i]-1;
break;
}
bool changed = 1;
while(changed) {
changed = 0;
for (int i = 2; i <= k; i++) {
int st = pre[i-1]+c[i-1]+1, end = st + c[i]-1;
int tmp = st;
while(1) {
auto it = lower_bound(white.begin(), white.end(), st);
if (*it <= end) {
st = *it+1;
end = st + c[i]-1;
} else break;
}
pre[i] = max(pre[i], st);
}
for (int i = k-1; i >= 1; i--) {
int end = suf[i+1] - c[i+1] - 1, st = end - c[i] + 1;
int tmp = end;
while(1) {
auto it = lower_bound(white.begin(), white.end(), st);
if (*it <= end) {
end = *it-1;
st = end - c[i] + 1;
} else break;
}
suf[i] = min(suf[i], end);
}
for (int i = 0; i < black.size(); i++) {
int pos = black[i], cnt = 0, A, B, len, I;
for (int j = 1; j <= k; j++) {
int a = pre[j], b = suf[j];
if (a > pos) break;
if (a <= pos && pos <= b) {
cnt++;
A = a, B = b, len = c[j], I = j;
}
}
if (cnt == 1) {
int a1 = max(1, pos - len + 1), b1 = min(n, pos + len - 1);
if (a1 > A || b1 < B) {
changed = 1;
A = max(A, a1);
B = min(B, b1);
pre[I] = A, suf[I] = B;
}
}
}
}
for (int i = 0; i < pre[1]; i++) ans[i] = '_';
for (int i = suf[k]+1; i <= n; i++) ans[i] = '_';
for (int i = 1; i <= k; i++) {
// cout << i << ": " << pre[i] << ' ' << suf[i] << '\n';
int len = suf[i] - pre[i] + 1;
if (len >= c[i] * 2) continue;
if (len == c[i])
for (int j = pre[i]; j <= suf[i]; j++) ans[j] = 'X';
int len1 = c[i] * 2 - len;
for (int j = 0; j < len1; j++) {
ans[j + c[i] - len1 + pre[i]] = 'X';
}
}
for (int i = 2; i <= k; i++) {
int a = pre[i-1], b = suf[i-1];
int a1 = pre[i], b1 = suf[i];
for (int j = b+1; j < a1; j++) ans[j] = '_';
}
for (int i = 1; i < white.size() && white.size() != 2; i++) {
int st = white[i-1]+1, end = white[i]-1;
bool x = 0;
for (int j = 1; j <= k; j++) {
int a = pre[j], b = suf[j], len1 = c[j];
int a1 = max(st, pre[j]), b1 = min(b, end), len = b1 - a1 + 1;
if (len >= len1) {
x = 1;
break;
}
}
if (!x) {
for (int j = st; j <= end; j++) ans[j] = '_';
}
}
for (int i = 1; i <= n; i++) {
if (ans[i] != '_') continue;
if (i < n && ans[i+1] == 'X') {
set <int> vals;
int pos = i+1;
for (int j = 1; j <= k; j++) {
int a = pre[j], b = suf[j];
if (a <= pos && pos <= b) {
vals.insert(c[j]);
}
}
int mini = *vals.begin();
for (int j = 0; j < mini; j++) {
ans[pos+j] = 'X';
}
if (vals.size() == 1) {
ans[pos+mini] = '_';
}
}
}
ans = ans.substr(1, n);
return ans;
}
