#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>
#include "paint.h"
using namespace std;
const int N = 5 + 1e5;
const int inf = 7 + 1e9;
struct Event {
int pos, val, type;
bool operator <(const Event &O) const {
if (pos != O.pos)
return pos < O.pos;
if (val != O.val)
return val < O.val;
return type < O.type;
}
};
string t;
int n, m;
vector <int> a, sum, ma, vis;
vector <vector <int>> f;
vector <Event> g;
int get(int l, int r) {
return sum[r] - (l > 0 ? sum[l - 1] : 0);
}
int cal(int i, int j) {
if (i >= n)
return j >= m;
if (f[i][j] >= 0)
return f[i][j];
f[i][j] = 0;
if (j < m && i + a[j] <= n && get(i, i + a[j] - 1) == 0 && t[i + a[j]] != 'X' && cal(i + a[j] + 1, j + 1)) {
f[i][j] = 1;
ma[i] = max(ma[i], a[j]);
if (!vis[i + a[j]]) {
vis[i + a[j]] = 1;
g.push_back({i + a[j], 1, 0});
g.push_back({i + a[j] + 1, -1, 0});
}
}
if (t[i] != 'X' && cal(i + 1, j)) {
f[i][j] = 1;
if (!vis[i]) {
vis[i] = 1;
g.push_back({i, 1, 0});
g.push_back({i + 1, -1, 0});
}
}
return f[i][j];
}
string solve_puzzle(string s, vector<int> c) {
n = s.size(); m = c.size();
s += '_';
t = s;
a = c;
sum.assign(n, 0);
for (int i = 0; i < n; i ++) {
sum[i] = s[i] == '_';
if (i > 0)
sum[i] += sum[i - 1];
}
ma.assign(n, 0);
vis.assign(n + 1, 0);
f.assign(n + 2, vector <int> (m + 1, -1));
cal(0, 0);
for (int i = 0; i < n; i ++)
if (ma[i]) {
g.push_back({i, 1, 1});
g.push_back({i + ma[i], -1, 1});
}
string ans;
int pos = 0;
sort(g.begin(), g.end());
vector <int> cnt(2, 0);
for (int i = 0; i < n; i ++) {
while (pos < g.size() && g[pos].pos == i) {
cnt[g[pos].type] += g[pos].val;
pos ++;
}
if (cnt[0] == 0)
ans += 'X';
else if (cnt[1] == 0)
ans += '_';
else
ans += '?';
}
return ans;
}
