#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int) 2e5 + 5;
const int MAXK = 100;
static bool dpl[MAXN + 1][MAXK + 1], dpr[MAXN + 1][MAXK + 1];
int toL[MAXN + 1];
inline void solve(string &str, vector <int> &c, int n, int k, bool dp[MAXN + 1][MAXK + 1]) {
int i, j;
for(i = 1; i <= n; i++) {
toL[i] = i;
if(str[i] != 'X') {
toL[i] = toL[i - 1];
}
}
vector <int> W(n + 1), sp(n + 1);
dp[0][0] = 1;
for(i = 1; i <= n; i++) {
dp[i][0] = (dp[i - 1][0] && str[i] != 'X');
W[i] = W[i - 1] + (str[i] == '_');
}
for(j = 1; j <= k; j++) {
sp[0] = 0;
for(i = 1; i <= n; i++) {
if(i >= c[j] && str[i - c[j]] != 'X' && W[i] - W[i - c[j]] == 0) {
if(j == 1) {
if(toL[i - c[j]] == 0)
dp[i][j] = 1;
}
else if(i > c[j]) {
dp[i][j] = (sp[i - c[j] - 1] - sp[max(0, toL[i - c[j]] - 1)] > 0);
}
}
sp[i] = sp[i - 1] + dp[i][j - 1];
}
}
}
string solve_puzzle(string s, vector<int> c) {
int n = s.size(), k = c.size();
int i, j;
string str = " " + s;
c.resize(k + 1), str.resize(n + 2);
for(i = k; i >= 1; i--) {
c[i] = c[i - 1];
}
solve(str, c, n, k, dpl);
for(i = 1; i < n - i + 1; i++) {
swap(str[i], str[n - i + 1]);
}
for(i = 1; i < k - i + 1; i++) {
swap(c[i], c[k - i + 1]);
}
solve(str, c, n, k, dpr);
for(i = 1; i < n - i + 1; i++) {
swap(str[i], str[n - i + 1]);
for(j = 0; j <= k; j++) {
swap(dpr[i][j], dpr[n - i + 1][j]);
}
}
for(i = 1; i < k - i + 1; i++) {
swap(c[i], c[k - i + 1]);
}
vector <int> B(n + 2), W(n + 2);
for(j = 1; j <= k; j++) {
int mx = n + 1, last = n + 1;
for(i = n; i >= 1; i--) {
/*if(i == 78 && j == 5) {
cerr << mx << "\n";
}*/
if(dpl[i][j] && str[i + 1] != 'X' && ((j == k && last == n + 1) || (j < k && mx > i + 1 && mx != n + 1 && mx <= last))) {
B[i - c[j] + 1]++;
B[i + 1]--;
W[i + 1]++;
W[mx]--;
}
if(str[i] == 'X') last = i;
if(dpr[i][k - j] && (mx > last || mx == n + 1) && j != k) {
mx = i;
}
}
}
for(i = 1; i <= n; i++) {
if(dpr[i][k]) {
W[1]++, W[i]--;
}
if(str[i] == 'X') break;
}
string ans; ans.resize(n);
for(i = 1; i <= n; i++) {
B[i] += B[i - 1], W[i] += W[i - 1];
if(B[i] && W[i]) {
ans[i - 1] = '?';
}
else if(B[i]) {
ans[i - 1] = 'X';
}
else if(W[i]) {
ans[i - 1] = '_';
}
else {
assert(0);
}
}
return ans;
}
