#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
using DP = vector<vector<int>>;
template<typename T> T rev(T v) {
reverse(v.begin(), v.end());
return v;
}
DP compute_dp(string s, vector<int> c) {
int n = s.size(), k = c.size();
DP dp(n, vector<int>(k, 0));
for (int j = 0 ; j < k ; ++ j) {
int last_ = -1;
for (int i = 0 ; i < n ; ++ i) {
if (s[i] == '_') last_ = i;
if (last_ < i - c[j] + 1 && s[i - c[j]] != 'X') {
dp[i][j] |= (!j && i - c[j] + 1 >= 0 ? 1 : (j && i - c[j] - 1 >= 0 ? dp[i - c[j] - 1][j - 1] : 0));
}
if (s[i] != 'X' && i > 0) {
dp[i][j] |= dp[i - 1][j];
}
}
}
return dp;
}
string solve_puzzle(string s, vector<int> c) {
auto dpref = compute_dp(s, c);
auto dsuff = rev(compute_dp(rev(s), rev(c)));
int n = s.size(), k = c.size();
vector<int>emp(n, 1);
vector<int>ems(n, 1);
for (int i = 0 ; i < n ; ++ i) {
if (s[i] == 'X') emp[i] = 0;
if (i > 0) emp[i] &= emp[i - 1];
}
for (int i = n - 1 ; i >= 0 ; -- i) {
if (s[i] == 'X') ems[i] = 0;
if (i + 1 < n) ems[i] &= ems[i + 1];
}
DP can(n, vector<int>(k));
for (int y = 0 ; y < k ; ++ y) {
int last_ = n;
for (int x = n - 1 ; x >= 0 ; -- x) {
if (s[x] == '_') last_ = x;
if (x + c[y] - 1 >= last_) {
can[x][y] = 0;
continue;
}
if (k == 1) {
can[x][y] = ((!x || emp[x - 1]) && (x + c[y] >= n || ems[x + c[y]]));
continue;
}
if (y == 0) can[x][y] = x + c[y] - 1 < n && (!x || emp[x-1]) && (x+c[y]>=n||s[x+c[y]]!='X')&&(x+c[y]+1>=n||dsuff[x + c[y] + 1][k - 2 - y]);
else if (y == k - 1) can[x][y] = (x+c[y]>=n||ems[x+c[y]]) && (!x || s[x-1]!='X')&&(x<=1||dpref[x - 2][y - 1]);
else can[x][y] = x + c[y] - 1 < n && (!x || s[x-1]!='X')&&(x<=1||dpref[x - 2][y - 1]) && (x+c[y]>=n||s[x+c[y]]!='X')&&(x+c[y]+1>=n||dsuff[x + c[y] + 1][k - 2 - y]);
}
}
vector<int>canx(n), can_(n);
for (int x = 0 ; x < n ; ++ x) {
if (s[x] != '.') continue;
for (int y = -1 ; y < k ; ++ y) {
if (y == -1) can_[x] |= (x + 1 < n && k - 1 >= 0 && (!x||emp[x-1]) && dsuff[x + 1][k - 1]);
else if (y == k - 1) can_[x] |= (x > 0 && (x+1>=n||ems[x+1]) && dpref[x - 1][y]);
else can_[x] |= (x > 0 && x + 1 < n && dpref[x - 1][y] && dsuff[x + 1][k - y - 2]);
}
}
for (int y = 0 ; y < k ; ++ y) {
int sum = 0;
for (int x = 0 ; x < n ; ++ x) {
if (x - c[y] >= 0) sum -= can[x - c[y]][y];
sum += can[x][y];
canx[x] |= (sum > 0 ? 1 : 0);
}
}
string ans = s;
for (int i = 0 ; i < n ; ++ i) {
if (s[i] == '.') {
ans[i] = (canx[i] && can_[i]) ? '?' : (canx[i] ? 'X' : '_');
}
}
return ans;
}
