#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n, k;
bool pref[N][105], suff[N][105];
bool prefor[N][105], suffor[N][105];
int sum[N];
bool xx[N];
string solve_puzzle(string s, vector<int> c) {
n = s.length();
k = c.size();
s += '_';
//calc prefix
for(int i=0;i<=n;i++)sum[i] = ((i==0)? 0 : sum[i-1])+(int)(s[i]=='_');
for(int j=0;j<k;j++){
for(int i=0;i<n;i++){
if(s[i] == '_' || i-c[j]+1 < 0)continue;
if(sum[i] == ((i-c[j] < 0)? 0:sum[i-c[j]]) &&
(j==0 || (i-c[j]-1>=0&&pref[i-c[j]-1][j-1] == true)))pref[i][j] = true;
}
}
// calc suffix
for(int i=n;i>=0;i--)sum[i] = ((i==n)?0 : sum[i+1]+(int)(s[i]=='_'));
for(int j=k-1;j>=0;j--){
for(int i=n-1;i>=0;i--){
if(s[i] == '_' || i+c[j]-1>=n)continue;
if(sum[i] == ((i+c[j] > n)? 0:sum[i+c[j]]) &&
(j==k-1 || (i+c[j]+1<=n&&suff[i+c[j]+1][j+1] == true)))suff[i][j] = true;
}
}
for(int j=0;j<k;j++){
for(int i=0;i<=n;i++){
prefor[i][j] = pref[i][j];
if(i>0)prefor[i][j] |= prefor[i-1][j];
}
}
for(int j=0;j<k;j++){
for(int i=n;i>=0;i--){
suffor[i][j] = suff[i][j];
if(i<n)suffor[i][j] |= suffor[i+1][j];
}
}
for(int i=0;i<=n;i++)sum[i] = ((i==0)? 0 : sum[i-1])+(int)(s[i]=='_');
for(int j=0;j<k;j++){
vector<int> pr(N,0);
for(int i=0;i<n;i++){
if(k!=j&&(i+c[j] > n || ((i==0)?0:sum[i-1]) != sum[i+c[j]-1]))continue;
if((int)((j==0)?1:((i-2<0)?0:prefor[i-2][j-1])) + ((j+1>=k)?1:((i+c[j]+1>n)?1:suffor[i+c[j]+1][j+1])) > 1
&& ((i==0)?1:s[i-1]!='X') && s[min(n, i+c[j])] != 'X'){pr[i]++, pr[min(n, i+c[j])]--;}
}for(int i=0;i<n;i++){
pr[i] = (i==0)?pr[i]:pr[i]+pr[i-1];
if(pr[i])xx[i] = true;
}
}
string ans(n, '?');
for(int i=0;i<n;i++){
if(s[i] != '.'){
ans[i] = s[i];
continue;
}
bool X = xx[i];
bool _ = false;
for(int j=0;j<=k;j++){
if((int)((j==0)?1:((i==0)?0:prefor[i-1][j-1])) + ((j==k)?1:suffor[i+1][j]) > 1){
_ = true;
}
}
if(X && !_)ans[i] = 'X';
if(_ && !X)ans[i] = '_';
}
return ans;
}
/*
..._._.._.
1 3
*/
