#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<int> prefX, pref_;
int getX(int l, int r)
{
r = min(r, n - 1);
if (l > 0) return prefX[r] - prefX[l - 1];
return prefX[r];
}
int get_(int l, int r)
{
r = min(r, n - 1);
if (l > 0) return pref_[r] - pref_[l - 1];
return pref_[r];
}
string solve_puzzle(string s, vector<int> c)
{
n = s.length();
k = c.size();
vector<vector<array<int, 2>>> dp1(n + 1, vector<array<int, 2>> (k + 1, {0, 0}));
vector<vector<array<int, 2>>> dp2 = dp1;
prefX.assign(n + 1, 0);
pref_.assign(n + 1, 0);
for (int 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 (int i = 0; i < n; i++)
{
if (s[i] == '.' || s[i] == 'X')
{
int cnt_ = get_(i, i + c[0] - 1);
int cntX = (!i ? 0 : getX(0, i - 1));
int 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] == '_')
{
int 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 (int i = 1; i < n; i++)
{
for (int j = 1; j < k; j++)
{
if (s[i] == '.' || s[i] == 'X')
{
int cnt_ = get_(i, i + c[j] - 1);
int 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] += dp1[i - c[j - 1]][j - 1][0];
}
}
}
//-----
for (int i = n - 1; i >= 0; i--)
{
if (s[i] == '.' || s[i] == 'X')
{
int cnt_ = get_(i, i + c[k - 1] - 1);
int cntX = (i + c[k - 1] >= n ? 0 : getX(i + c[k - 1], n - 1));
int 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] == '_')
{
int 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 (int i = n - 2; i >= 0; i--)
{
for (int j = k - 2; j >= 0; j--)
{
if (s[i] == '.' || s[i] == 'X')
{
int cnt_ = get_(i, i + c[j] - 1);
int 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] += dp2[i + 1][j + 1][0];
}
}
}
vector<int> exl(n + 1, 0), exr(n + 1, 0);
for (int i = 1; i < n; i++)
{
exl[i] = exl[i - 1];
if (i - c[k - 1] >= 0) exl[i] += dp1[i - c[k - 1]][k - 1][0];
}
for (int i = n - 2; i >= 0; i--)
{
exr[i] = exr[i + 1] + dp2[i + 1][0][0];
}
// for (int j = 0; j < k; j++)
// {
// for (int i = 0; i < n; i++)
// {
// cout << dp1[i][j][1] << ' ';
// }
// cout << '\n';
// }
// for (int i = 0; i < n; i++) cout << exl[i] << ' ';
// cout << "\n\n";
// for (int i = 0; i < n; i++) cout << exr[i] << ' ';
// cout << '\n';
// for (int j = 0; j < k; j++)
// {
// for (int i = 0; i < n; i++)
// {
// cout << dp2[i][j][1] << ' ';
// }
// cout << '\n';
// }
// cout << '\n';
int all = 0;
vector<int> pref(n + 1, 0), cnt(n + 1, 0);
for (int i = 0; i < n; i++)
{
all += dp1[i][k - 1][0];
cnt[i] += exl[i] * dp2[i][k - 1][1];
for (int j = 0; j < k; j++)
{
int x = dp1[i][j][0] * dp2[i][j][0];
pref[i] += x;
if (i + c[j] < n) pref[i + c[j]] -= x;
if (!j) x = exr[i] * dp1[i][j][1];
else x = dp1[i][j][1] * dp2[i][j - 1][1];
cnt[i] += x;
}
}
// cout << all << endl;
for (int i = 1; i < n; i++) pref[i] += pref[i - 1];
string res = "";
for (int 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;
}
