#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll n, k;
int dp1[200005][105][2], dp2[200005][105][2];
int prefX[200005], pref_[200005], exl[200005], exr[200005], pref[200005], cnt[200005];
string res = "";
ll add(ll a, ll b)
{
return (a + b) % mod;
}
ll mult(ll a, ll b)
{
return (a * b) % mod;
}
ll sub(ll a, ll b)
{
return (a - b + 10*mod) % mod;
}
ll getX(ll l, ll r)
{
r = min(r, n - 1);
if (l > 0) return sub(prefX[r], prefX[l - 1]);
return prefX[r];
}
ll get_(ll l, ll r)
{
r = min(r, n - 1);
if (l > 0) return sub(pref_[r], pref_[l - 1]);
return pref_[r];
}
string solve_puzzle(string s, vector<int> c)
{
n = s.length();
k = c.size();
for (ll i = 0; i < n; i++)
{
if (i)
{
prefX[i] = prefX[i - 1];
pref_[i] = pref_[i - 1];
}
prefX[i] += (s[i] == 'X');
pref_[i] += (s[i] == '_');
}
for (ll i = 0; i < n; i++)
{
if (s[i] == '.' || s[i] == 'X')
{
ll cnt_ = get_(i, i + c[0] - 1);
ll cntX = (!i ? 0 : getX(0, i - 1));
ll flag = 1;
if (1 == c.size() && i + c[0] < n && getX(i + c[0], n - 1)) flag = 0;
if (!(!flag || cntX || cnt_ || i + c[0] - 1 >= n))
{
if (i) dp1[i][0][0] = dp1[i - 1][0][1];
else dp1[i][0][0] = 1;
}
}
if (s[i] == '.' || s[i] == '_')
{
ll cntX = (!i ? 0 : getX(0, i - 1));
if (cntX) continue;
if (i) dp1[i][0][1] = dp1[i - 1][0][1];
else dp1[i][0][1] = 1;
}
}
for (ll i = 1; i < n; i++)
{
for (ll j = 1; j < k; j++)
{
if (s[i] == '.' || s[i] == 'X')
{
ll cnt_ = get_(i, i + c[j] - 1);
ll flag = 1;
if (j == k - 1 && i + c[j] < n && getX(i + c[j], n - 1)) flag = 0;
if (!(!flag || cnt_ || i + c[j] - 1 >= n))
{
dp1[i][j][0] = dp1[i - 1][j][1];
}
}
if (s[i] == '.' || s[i] == '_')
{
dp1[i][j][1] = dp1[i - 1][j][1];
if (i - c[j - 1] < 0) continue;
dp1[i][j][1] = add(dp1[i][j][1], dp1[i - c[j - 1]][j - 1][0]);
}
}
}
//-----
for (ll i = n - 1; i >= 0; i--)
{
if (s[i] == '.' || s[i] == 'X')
{
ll cnt_ = get_(i, i + c[k - 1] - 1);
ll cntX = (i + c[k - 1] >= n ? 0 : getX(i + c[k - 1], n - 1));
ll flag = 1;
if (1 == c.size() && i && getX(0, i - 1)) flag = 0;
if (!(!flag || cntX || cnt_ || i + c[k - 1] - 1 >= n))
{
if (i + c[k - 1] < n) dp2[i][k - 1][0] = dp2[i + c[k - 1]][k - 1][1];
else dp2[i][k - 1][0] = 1;
}
}
if (s[i] == '.' || s[i] == '_')
{
ll cntX = (i == n - 1 ? 0 : getX(i + 1, n - 1));
if (cntX) continue;
if (i != n - 1) dp2[i][k - 1][1] = dp2[i + 1][k - 1][1];
else dp2[i][k - 1][1] = 1;
}
}
for (ll i = n - 2; i >= 0; i--)
{
for (ll j = k - 2; j >= 0; j--)
{
if (s[i] == '.' || s[i] == 'X')
{
ll cnt_ = get_(i, i + c[j] - 1);
ll flag = 1;
if (!j && i && getX(0, i - 1)) flag = 0;
if (!(!flag || cnt_ || i + c[j] - 1 >= n))
{
if (i + c[j] < n) dp2[i][j][0] = dp2[i + c[j]][j][1];
}
}
if (s[i] == '.' || s[i] == '_')
{
dp2[i][j][1] = dp2[i + 1][j][1];
dp2[i][j][1] = add(dp2[i][j][1], dp2[i + 1][j + 1][0]);
}
}
}
for (ll i = 1; i < n; i++)
{
exl[i] = exl[i - 1];
if (i - c[k - 1] >= 0) exl[i] = add(exl[i], dp1[i - c[k - 1]][k - 1][0]);
}
for (ll i = n - 2; i >= 0; i--)
{
exr[i] = add(exr[i + 1], dp2[i + 1][0][0]);
}
// for (ll j = 0; j < k; j++)
// {
// for (ll i = 0; i < n; i++)
// {
// cout << dp1[i][j][1] << ' ';
// }
// cout << '\n';
// }
// for (ll i = 0; i < n; i++) cout << exl[i] << ' ';
// cout << "\n\n";
// for (ll i = 0; i < n; i++) cout << exr[i] << ' ';
// cout << '\n';
// for (ll j = 0; j < k; j++)
// {
// for (ll i = 0; i < n; i++)
// {
// cout << dp2[i][j][1] << ' ';
// }
// cout << '\n';
// }
// cout << '\n';
ll all = 0;
for (ll i = 0; i < n; i++)
{
all = add(all, dp1[i][k - 1][0]);
cnt[i] = add(cnt[i], mult(exl[i], dp2[i][k - 1][1]));
for (ll j = 0; j < k; j++)
{
ll x = mult(dp1[i][j][0], dp2[i][j][0]);
pref[i] = add(pref[i], x);
if (i + c[j] < n) pref[i + c[j]] = sub(pref[i + c[j]], x);
if (!j) x = mult(exr[i], dp1[i][j][1]);
else x = mult(dp1[i][j][1], dp2[i][j - 1][1]);
cnt[i] = add(cnt[i], x);
}
}
// cout << all << endl;
for (ll i = 1; i < n; i++) pref[i] = add(pref[i], pref[i - 1]);
for (ll i = 0; i < n; i++)
{
// cout << cnt[i] << ' ';
if (pref[i] == all) res.push_back('X');
else if (cnt[i] == all) res.push_back('_');
else res.push_back('?');
}
// cout << '\n';
return res;
}
