#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j ,k) for(int i = j; i < (int)k; i++)
typedef vector<int> vi;
const int N = 2e5 + 10;
bitset<110> dp[N] , pd[N];
string solve_puzzle(string s, vi c) {
int n = s.size();
int k = c.size();
rep(i , 0 , n) {
dp[i].reset();
pd[i].reset();
}
{
int last = -1;
bool haveX = false;
rep(i , 0 , n) {
if (s[i] == 'X') haveX = true;
dp[i][0] = !haveX;
if (s[i] == '_') last = i;
rep(j , 1 , k + 1) {
if (i && s[i] != 'X') dp[i][j] = dp[i - 1][j];
int p = i - c[j - 1];
if (last <= p) {
if (p == -1)
dp[i][j] = dp[i][j] || (j == 1);
else if (p == 0)
dp[i][j] = dp[i][j] || (j == 1 && s[p] != 'X');
else
dp[i][j] = dp[i][j] || (s[p] != 'X' && dp[p - 1][j - 1]);
}
}
}
}
{
int last = n;
bool haveX = false;
for (int i = n - 1; ~i; i--) {
if (s[i] == 'X') haveX = true;
pd[i][k + 1] = !haveX;
if (s[i] == '_') last = i;
rep(j , 1 , k + 1) {
int p = i + c[j - 1];
if (i + 1 < n && s[i] != 'X') pd[i][j] = pd[i + 1][j];
if (p <= last) {
if (p == n)
pd[i][j] = pd[i][j] || (j == k);
else if (p == n - 1)
pd[i][j] = pd[i][j] || (j == k && s[p] != 'X');
else
pd[i][j] = pd[i][j] || (s[p] != 'X' && pd[p + 1][j + 1]);
}
}
}
}
vi cnt(n + 1);
rep(j , 1 , k + 1) {
int last = -1;
rep(i , 0 , n) {
if (s[i] == '_') last = i;
int p = i - c[j - 1];
if (last <= p) {
bool flag = true;
if (flag && p == -1) {
if (j > 1)
flag = false;
}
else if (flag) {
if (s[p] == 'X')
flag = false;
if (p == 0) {
if (j > 1) flag = false;
}
else if (!dp[p - 1][j - 1]) flag = false;
}
p = i + 1;
if (p == n) {
if (j < k) flag = false;
}
else if (flag) {
if (s[p] == 'X') flag = false;
if (p == n - 1) {
if (j < k) flag = false;
}
else if (!pd[p + 1][j + 1]) flag = false;
}
if (flag) {
cnt[i - c[j - 1] + 1]++;
cnt[i + 1]--;
}
}
}
}
string res;
int local = 0;
rep(i , 0 , n) {
local += cnt[i];
bool A = local > 0;
bool B = false;
rep(j , 0 , k + 1) {
bool C = true;
if (i == 0 && j) C = false;
if (i == n - 1 && j < k) C = false;
if (i && !dp[i - 1][j]) C= false;
if (i + 1 < n && !pd[i + 1][j + 1]) C = false;
B |= C;
}
if (s[i] == 'X') B = false;
if (A && !B) res.push_back('X');
else if (!A && B) res.push_back('_');
else res.push_back('?');
//cout << A << ' ' << B << endl;
//assert(A || B);
}
return res;
}
