// Starcraft 2 enjoyer //
#include <bits/stdc++.h>
#include "paint.h"
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
#define LSOne(X) ((X) & -(X))
const int N = 2e5 + 5;
const int M = 5e5 + 5;
const int K = 1e2 + 5;
const int LG = 20;
const int INF = 1e9 + 5;
const int B = 1000;
const int MOD = 1e9 + 7;
int n, k, pref1[N], pref2[N], gud1[N], gud2[N];
vector<int> a;
bool dp1[N][K], dp2[N][K];
string s;
string solve_puzzle(string s, vector<int> v)
{
n = s.size();
k = v.size();
vector<int> a;
a.push_back(0);
for (int i : v)
a.push_back(i);
// cout << s << " " << n << " " << k << "\n";
// for (int x = 1; x <= k; x++)
// {
// cout << a[x] << " ";
// }
// cout << "\n";
s = '0' + s;
for (int x = 1; x <= n; x++)
{
pref1[x] = pref1[x - 1];
pref2[x] = pref2[x - 1];
if (s[x] == '_')
{
pref1[x]++;
}
if (s[x] == 'X')
{
pref2[x]++;
}
}
dp1[0][0] = 1;
for (int x = 0; x < n; x++)
{
for (int y = 0; y <= k; y++)
{
if (!dp1[x][y])
continue;
if (!(pref2[x + 1] - pref2[x]))
{
dp1[x + 1][y] = 1;
}
if (y < k && x + a[y + 1] + 1 <= n)
{
if (!(pref1[x + a[y + 1]] - pref1[x]) && !(pref2[x + a[y + 1] + 1] - pref2[x + a[y + 1]]))
{
dp1[x + a[y + 1] + 1][y + 1] = 1;
}
}
}
}
dp2[n + 1][k + 1] = 1;
for (int x = n + 1; x >= 2; x--)
{
for (int y = 1; y <= k + 1; y++)
{
if (!dp2[x][y])
continue;
if (!(pref2[x - 1] - pref2[x - 2]))
{
dp2[x - 1][y] = 1;
}
if (y > 1 && x - 1 - a[y - 1] >= 1)
{
if (!(pref1[x - 1] - pref1[x - 1 - a[y - 1]]) && !(pref2[x - 1 - a[y - 1]] - pref2[x - 2 - a[y - 1]]))
{
dp2[x - 1 - a[y - 1]][y - 1] = 1;
}
}
}
}
for (int x = n + 1; x >= 1; x--)
{
for (int y = 1; y <= k + 1; y++)
{
if (!dp2[x][y])
continue;
if (dp1[x][y - 1])
{
gud1[x]++;
gud1[x + 1]--;
}
if (y >= 2 && x - a[y - 1] >= 1 && dp1[x - a[y - 1] - 1][y - 2] && !(pref1[x - 1] - pref1[x - a[y - 1] - 1]))
{
gud2[x - a[y - 1]]++;
gud2[x]--;
}
}
}
for (int x = 1; x <= n; x++)
{
gud1[x] += gud1[x - 1];
gud2[x] += gud2[x - 1];
}
string ans = "";
for (int x = 1; x <= n; x++)
{
if (gud1[x] && gud2[x])
ans += '?';
else if (gud1[x])
ans += '_';
else
ans += 'X';
}
return ans;
}
