#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <cstdlib>
#include <set>
#include <iomanip>
#include <limits>
#include <map>
#include <assert.h>
#include <algorithm>
#include <list>
#include <iterator>
#include <fstream>
#include <random>
#include <unordered_map>
#include <array>
//#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i < b; i++)
#define rrep(i,a) for (int i = (a) - 1; i >= 0; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef pair<bool, bool> pbb;
// fast
#include "paint.h" // !
#include <cstdlib>
//
vector<vector<int>> dp; // dp
vector<pbb> alts;
//vector<bool> white_alts, black_alts;
int N, K;
string S;
vector<int> C;
vector<int> white_inds;
vector<int> black_start;
// ?
bool go(int nat, int kat)
{
//if (kat >= K) return true;
if (nat >= N && kat >= K) return true;
if (nat >= N) return false;
if (dp[nat][kat] != -1) return bool(dp[nat][kat]); // ??
if (S[nat] == '_')
{
dp[nat][kat] = go(nat + 1, kat);
}
else if (S[nat] == 'X')
{
if (kat >= K)
{
dp[nat][kat] = false;
}
else
{
// when next white, nw_ind - nat >= C[kat] -> yay
int wi;
if (white_inds.size() == 0) wi = N;
else if (nat > white_inds[white_inds.size() - 1]) wi = N;
else
{
int wii = lower_bound(all(white_inds), nat) - white_inds.begin();
wi = white_inds[wii];
}
if (wi - nat >= C[kat] && S[nat + C[kat]] != 'X')
{
dp[nat][kat] = go(nat + C[kat] + 1, kat + 1); // +1 !!
if (dp[nat][kat]) {
alts[nat + C[kat]].second = true;
black_start[nat] = max(black_start[nat], C[kat]);
}
}
else
{
dp[nat][kat] = false;
}
}
}
else if (S[nat] == '.') //
{
if (kat >= K)
{
bool b = false, w;
w = go(nat + 1, kat);
if (w)
{
alts[nat].second = true;
}
dp[nat][kat] = w;
}
else
{
bool b, w;
// black ?
int wi;
if (white_inds.size() == 0) wi = N;
else if (nat > white_inds[white_inds.size() - 1]) wi = N;
else
{
int wii = lower_bound(all(white_inds), nat) - white_inds.begin();
wi = white_inds[wii];
}
if (wi - nat >= C[kat] && S[nat + C[kat]] != 'X')
{
b = go(nat + C[kat] + 1, kat + 1); // +1
if (b) {
alts[nat + C[kat]].second = true;
black_start[nat] = max(black_start[nat], C[kat]);
}
}
else b = false;
w = go(nat + 1, kat);
//assert(b || w);
if (b || w)
{
if (b) alts[nat].first = true;
if (w) alts[nat].second = true;
}
dp[nat][kat] = (b || w);
}
}
return bool(dp[nat][kat]);
}
std::string solve_puzzle(std::string s, std::vector<int> c)
{
N = s.size();
K = c.size();
S = s;
C = c;
dp.assign(N, vector<int>(K + 1, -1));
alts.assign(N, make_pair(false, false));
black_start.assign(N, -1);
rep(i,0,N) {
if (S[i] == '_') white_inds.pb(i);
}
go(0,0); //
int reach = -1; // inc
rep(i,0,N)
{
if (black_start[i] != -1) reach = max(reach, i + black_start[i] - 1);
if (i <= reach) alts[i].first = true;
}
string ret = "";
rep(i,0,N) {
if (S[i] == '_') ret += '_';
else if (S[i] == 'X') ret += 'X';
else if (alts[i].first && alts[i].second) ret += '?';
else if (alts[i].first) ret += 'X';
else if (alts[i].second) ret += '_';
else {
ret += 'X';
}
}
return ret;
}
