#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, MAXK=107;
int pref[LIM][MAXK], suf[LIM][MAXK], lewo[LIM], prawo[LIM], sum[LIM];
string solve_puzzle(string s, vector<int>c) {
int n=s.size(), k=c.size();
pref[0][0]=1;
rep(i, n) {
if(s[i]!='X') {
rep(j, k+1) pref[i+1][j]=pref[i][j];
}
if(s[i]!='_') {
lewo[i+1]=lewo[i]+1;
rep(j, k) {
if(lewo[i+1]>=c[j]) {
if(i-c[j]+1==0) {
if(j==0) pref[i+1][j+1]=1;
} else if(s[i-c[j]]!='X' && pref[i-c[j]][j]) {
pref[i+1][j+1]=1;
}
}
}
}
}
suf[n+1][k+1]=1;
for(int i=n-1; i>=0; --i) {
if(s[i]!='X') {
rep(j, k+1) suf[i+1][j+1]=suf[i+2][j+1];
}
if(s[i]!='_') {
prawo[i+1]=prawo[i+2]+1;
rep(j, k) {
if(prawo[i+1]>=c[j]) {
if(i+1+c[j]==n+1) {
if(j==k-1) suf[i+1][j+1]=1;
} else if(s[i+c[j]]!='X' && suf[i+c[j]+2][j+2]) {
suf[i+1][j+1]=1;
}
}
}
}
}
rep(i, n) if(s[i]=='.') {
bool ok=false;
rep(j, k+1) if(pref[i][j] && suf[i+2][j+1]) ok=true;
if(!ok) s[i]='X';
}
rep(j, k) {
for(int i=c[j]-1; i<n; ++i) {
if(lewo[i+1]>=c[j]) {
bool ok=true;
if(i+1-c[j]==0 && j>0) ok=false;
if(i+1-c[j]>0 && (pref[i-c[j]][j]==0 || s[i-c[j]]=='X')) {
ok=false;
}
if(i+1==n && j<k-1) ok=false;
if(i+1<n && (suf[i+3][j+2]==0 || s[i+1]=='X')) ok=false;
if(ok) {
++sum[i-c[j]+1];
--sum[i+1];
}
}
}
}
int akt=0;
rep(i, n) {
akt+=sum[i];
if(s[i]=='.') {
if(akt==0) s[i]='_';
else s[i]='?';
}
}
return s;
}
