#include "paint.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 2e5;
const int MAX_K = 105;
int cnt[MAX_N];
//bool dpl[MAX_N][MAX_K];
//bool dpr[MAX_N][MAX_K];
std::string solve_puzzle(std::string s, std::vector<int> c) {
int n = s.size();
int k = c.size();
// for (int i = 0; i < n; i++) {
// int sum = -1;
// for (int j = 0; j < k; j++) {
// sum += c[j] + 1;
// if (i && dpl[i - 1][j]) {
// dpl[i][j] = true;
// continue;
// }
// if (sum > i + 1) break;
// }
// }
vi bad;
for (int i = 0; i < n; i++) {
if (s[i] == '_') bad.push_back(i);
}
bad.push_back(n);
int sum = 0;
for (int d : c) sum += d;
int count = 0;
for (int j = 0; j <= n; j++, count++) {
int ind = j;
int x = 0;
for (int l = 0; l < k && ind < n; l++) {
int d = c[l];
while (ind < n) {
int y = *lower_bound(all(bad), ind);
if (y - ind >= d) break;
ind = y + 1;
}
for (int i = ind; i < min(ind + d, n); i++) {
x++, cnt[i]++;
}
ind += d + 1;
}
if (x != sum - k + 1) {
for (int l = 0; l < k && ind < n; l++) {
int d = c[l];
while (ind < n) {
int y = *lower_bound(all(bad), ind);
if (y >= d) break;
ind = y + 1;
}
for (int i = ind; i < min(ind + d, n); i++) {
cnt[i]--;
}
ind += d + 1;
}
break;
}
// ind = n - 1;
// for (int l = k - 1; l >= j; l--) {
// int d = c[l];
// for (int i = ind; i > ind - d; i--) cnt[i]++;
// ind -= d + 1;
// }
}
string ans(n, '?');
for (int i = 0; i < n; i++) {
if (cnt[i] == count) ans[i] = 'X';
else if (!cnt[i]) ans[i] = '_';
}
return ans;
}
