#include <bits/stdc++.h>
using namespace std;
const int maxn = 200003;
const int maxk = 103;
string s;
vector <int> c;
int pr[maxn];
pair <bool, bool> dp[maxn][maxk];
bool f(int pos, int k)
{
if (pos == 0)
{
if (k == -1)
return true;
return false;
}
if (k < -1)
return false;
if (dp[pos][k+1].second)
return dp[pos][k+1].first;
dp[pos][k+1] = {false, true};
if (k != -1)
if (pos-c[k]-1 >= 0)
if (s[pos-c[k]-1] != 'X')
if (pr[pos-1] - pr[pos-c[k]-1] == 0)
if (f(pos-c[k]-1, k-1))
dp[pos][k+1].first = true;
if (s[pos-1] != 'X')
if (f(pos-1, k))
dp[pos][k+1].first = true;
return dp[pos][k+1].first;
}
bool used[maxn][maxk];
bool can_white[maxn], can_black[maxn];
vector <pair <int, int> > shit;
void dfs(int pos, int k)
{
if (pos == 0)
return;
if (used[pos][k+1])
return;
used[pos][k+1] = true;
can_white[pos] = true;
if (s[pos-1] != 'X')
if (f(pos-1, k))
dfs(pos-1, k);
if (k != -1)
if (pos-c[k]-1 >= 0)
if (s[pos-c[k]-1] != 'X')
if (pr[pos-1] - pr[pos-c[k]-1] == 0)
if (f(pos-c[k]-1, k-1))
{
shit.push_back({pos-c[k], pos-1});
dfs(pos-c[k]-1, k-1);
}
}
string solve_puzzle(string _s, vector <int> _c)
{
s += "_";
s += _s;
s += "_";
c = _c;
if (s[0] == '_')
pr[0]++;
for (int i = 1; i < (int)s.size(); i++)
{
pr[i] = pr[i-1];
if (s[i] == '_')
pr[i]++;
}
f((int)s.size()-1, (int)c.size()-1);
dfs((int)s.size()-1, (int)c.size()-1);
sort (shit.begin(), shit.end());
int max_r = -1;
for (auto i: shit)
{
if (i.second <= max_r)
continue;
if (i.first > max_r)
{
for (int j = i.first; j <= i.second; j++)
can_black[j] = true;
max_r = i.second;
}
else
{
for (int j = max_r + 1; j <= i.second; j++)
can_black[j] = true;
max_r = i.second;
}
}
string ans;
for (int i = 0; i < (int)s.size()-2; i++)
{
if (can_black[i+1] && can_white[i+1])
ans += "?";
else
if (can_black[i+1])
ans += "X";
else
ans += "_";
}
return ans;
}
/*
string s1;
int k1;
vector <int> v1;
int main()
{
cin >> s1 >> k1;
v1.resize(k1);
for (int i = 0; i < k1; i++)
cin >> v1[i];
cout << solve_puzzle(s1, v1) << endl;
}
*/
