#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
const int MAXN = 2e5 + 7;
const int MAXK = 107;
int Sum[MAXN];
int pref[MAXN][MAXK];
int suf[MAXN][MAXK];
int pre[MAXN];
int nxt[MAXN];
int n, m;
string s;
vi c;
string solve_puzzle(string xd, vi lol){
s = xd;
c = lol;
n = sz(s);
m = sz(c);
int x = -1;
for(int i = 0; i < n; i++){
if(s[i] != '_'){
pre[i] = x;
}else{
pre[i] = i;
x = i;
}
}
x = n;
for(int i = n - 1; i >= 0; i--){
if(s[i] != '_'){
nxt[i] = x;
}else{
nxt[i] = i;
x = i;
}
}
pref[0][0] = 1;
for(int i = 0; i < n - 1; i++){
if(s[i] != 'X'){
for(int j = 0; j <= m; j++){
pref[i + 1][j] = pref[i][j];
}
}
if(s[i] != '_'){
for(int j = 0; j < m; j++){
if(pre[i] < i - c[j] + 1 && i - c[j] + 1 >= 0){
if(i - c[j] + 1 == 0){
if(j == 0){
pref[i + 1][j + 1] = 1;
}
continue;
}
if(s[i - c[j]] != 'X' && pref[i - c[j]][j]){
pref[i + 1][j + 1] = 1;
}
}
}
}
}
suf[n - 1][m] = 1;
suf[n][m] = 1;
for(int i = n - 1; i > 0; i--){
if(s[i] != 'X'){
for(int j = 0; j <= m; j++){
suf[i - 1][j] = suf[i][j];
}
}
if(s[i] != '_'){
for(int j = 1; j <= m; j++){
if(nxt[i] > i + c[j - 1] - 1 && i + c[j - 1] - 1 < n){
if(i + c[j - 1] - 1 == n - 1){
if(j == m){
suf[i - 1][j - 1] = 1;
}
continue;
}
if(s[i + c[j - 1]] != 'X' && suf[i + c[j - 1]][j]){
suf[i - 1][j - 1] = 1;
}
}
}
}
}
/*for(int i = 0; i < n; i++){
for(int j = 0; j <= m; j++){
cout << pref[i][j] << ' ';
}
cout << '\n';
}*/
for(int i = 0; i < n; i++){
//sprawdź czy istnieją takie rozwiązania w których masz _
if(s[i] != '.'){
continue;
}
bool f = 0;
for(int j = 0; j <= m; j++){
if(pref[i][j] && suf[i][j]){
f = 1;
}
}
if(!f){
s[i] = 'X';
}
}
//cout << s << '\n';
for(int j = 0; j < m; j++){
for(int i = 0; i + c[j] - 1 < n; i++){
if(nxt[i] > i + c[j] - 1){
bool ok = 1;
if(i == 0){
if(j != 0){
ok = 0;
}
}else{
if(!pref[i - 1][j]){
ok = 0;
}
if(s[i - 1] == 'X'){
ok = 0;
}
}
if(i + c[j] < n){
if(!suf[i + c[j]][j + 1]){
ok = 0;
}
if(s[i + c[j]] == 'X'){
ok = 0;
}
}else{
if(j != m - 1){
ok = 0;
}
}
if(ok){
Sum[i]++;
Sum[i + c[j]]--;
}
}
}
}
string res = "";
int sum = 0;
for(int i = 0; i < n; i++){
sum += Sum[i];
if(s[i] != '.'){
res += s[i];
continue;
}
if(sum > 0){
res += "?";
}else{
res += "_";
}
}
return res;
}
/*int main(){
cout << solve_puzzle("........", {3, 4}) << '\n';
return 0;
}*/
