#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
string s;
const int N = 5005;
const int K = 105;
vector <int> c(K), minNeedLen(K, 0);
vector <set <char> > chars(N);
string ans = "";
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';
for (int i = 1; i <= k; i++) c[i] = c1[i-1];
for (int i = 0; i < n+2; i++) ans += '?';
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;
}
