#include "paint.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 2e5 + 5, K = 105;
bool dpl[N][K][2];
bool dpr[N][K][2];
int l[N], r[N];
string solve_puzzle(string s, vi c) {
int n = SZ(s), k = SZ(c);
dpl[0][0][0] = 1;
for(int i = 1; i <= n; i++) {
if(s[i - 1] == '_') l[i] = 0;
else l[i] = l[i - 1] + 1;
for(int j = 0; j <= k; j++) {
// 0
if(s[i - 1] != 'X')
dpl[i][j][0] |= dpl[i - 1][j][0] | dpl[i - 1][j][1];
// 1
if(s[i - 1] != '_' && j && c[j - 1] <= l[i])
dpl[i][j][1] |= dpl[i - c[j - 1]][j - 1][0];
}
}
dpr[n + 1][0][0] = 1;
for(int i = n; i >= 1; i--) {
if(s[i - 1] == '_') r[i] = 0;
else r[i] = r[i + 1] + 1;
for(int j = 0; j <= k; j++) {
// 0
if(s[i - 1] != 'X')
dpr[i][j][0] |= dpr[i + 1][j][0] | dpr[i + 1][j][1];
// 1
if(s[i - 1] != '_' && j && c[k - j] <= r[i])
dpr[i][j][1] |= dpr[i + c[k - j]][j - 1][0];
}
}
string ans(n, '@');
for(int i = 1; i <= n; i++)
for(int j = 0; j <= k; j++)
if(dpl[i][j][0] && dpr[i][k - j][0])
ans[i - 1] = '_';
vi p(n + 1);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= k; j++) {
if(dpl[i][j][1] && dpr[i + 1][k - j][0]) {
int lb = i - c[j - 1] + 1, rb = i;
p[lb - 1]++;
p[rb]--;
}
}
}
for(int i = 0; i < n; i++) {
if(i) p[i] += p[i - 1];
if(p[i]) {
if(ans[i] == '_') ans[i] = '?';
else ans[i] = 'X';
}
}
return ans;
}
