#include "paint.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000009
#define mod 1000000007
#define ppair(x); cerr << "(" << x.first << ", " << x.second << ")\n";
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
using namespace std;
typedef long long ll;
string s;
int pre[101];
string ans;
int varmi(int l, int r){
int ans = 0;
if (l == 0) ans = pre[r];
else ans = pre[r] - pre[l-1];
if (ans > 0) return 1;
else return 0;
}
int possible(int l, int r, vector<int>& c){
if (c.size() == 0) return 1;
if (r-l+1 < c.back()) return 0;
if (varmi(r-c.back()+1, r)) return possible(l, r-1, c);
r -= c.back();
r--;
c.pop_back();
return possible(l, r, c);
}
void merge(int i, char c){
if (ans[i] == '!') ans[i] = c;
else if (ans[i] == '_' && c == 'X') ans[i] = '?';
else if (ans[i] == 'X' && c == '_') ans[i] = '?';
else if (ans[i] == '_' && c == '?') ans[i] = '?';
else if (ans[i] == 'X' && c == '?') ans[i] = '?';
}
void solve(int l, int r, vector<int>& c){
//cout << "solve(" << l << ", " << r << ", "; prarrv(c);
if (c.size() == 0){
for (int i = l; i <= r; i++){
merge(i, '_');
}
} else {
vector<int> presum(c.size());
presum[0] = c[0];
string str(r-l+1, '?');
for (int i = 1; i < c.size(); i++) presum[i] = presum[i-1] + c[i];
if (presum[c.size()-1] > r-l+1) return;
for (int i = 0; i < c.size(); i++){
int sag = presum[i] + i;
int sol = presum[c.size()-1] - (i == 0 ? 0 : presum[i-1]) + c.size()-1-i;
sol = r-l+1-sol;
//cout << bas(sol) << bas(sag) << endl;
//if (sol < 0 || sag > str.size()) continue;
for (int k = sol; k < sag; k++) str[k] = 'X';
}
for (int i = 0; i < str.size(); i++) merge(i+l, str[i]);
}
}
vector<int> subv(int l, int r, vector<int>& arr){
vector<int> ans;
for (int i = l; i <= r; i++) ans.pb(arr[i]);
return ans;
}
string solve_puzzle(string S, vector<int> c) {
s = S;
int sum = 0;
for (int i = 0; i < s.size(); i++){
if (s[i] == '_') sum++;
pre[i] = sum;
}
ans = "";
for (int i = 0; i < s.size(); i++) ans += (s[i] == '_' ? '_' : '!');
vector<pair<int, int> > araliklar;
int last = -1;
for (int i = 0; i < s.size(); i++){
if (s[i] == '_'){
if (last != i-1) araliklar.pb(mp(last, i));
last = i;
}
}
//cout << ans << endl;
araliklar.pb(mp(last, s.size()));
//for (int i = 0; i < araliklar.size(); i++) {ppair(araliklar[i]);}
for (int l = -1; l < (int)c.size(); l++){
for (int r = l+1; r <= c.size(); r++){
for (int i = 0; i < araliklar.size(); i++){
vector<int> v1 = subv(0, l, c);
vector<int> v2 = subv(r, c.size()-1, c);
//cout << "0 - " << araliklar[i].first << ": "; prarrv(v1);
//cout << araliklar[i].second << " - " << s.size()-1 << ": "; prarrv(v2);
if (possible(0, araliklar[i].first, v1) &&
possible(araliklar[i].second, s.size()-1, v2)){
//cout << "possible" << endl;
vector<int> sv = subv(l+1, r-1, c);
solve(araliklar[i].first+1, araliklar[i].second-1, sv);
//cout << ans << endl;
}
}
}
}
return ans;
}
