#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];
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];
}
}
string ans(n, '?');
for(int i=0;i<=n;i++)sum[i] = ((i==0)? 0 : sum[i-1])+(int)(s[i]=='_');
for(int i=0;i<n;i++){
if(s[i] != '.'){
ans[i] = s[i];
continue;
}
bool X = false;
bool _ = false;
for(int j=0;j<=k;j++){
if(((((int)((j==0)?1:prefor[i][j-1]) + ((j==k)?1:((i+2>n)?0:suffor[i+2][j])) > 1))
|| (int)((j==0)?1:((i-2<0)?0:prefor[i-2][j-1])) + ((j==k)?1:(suffor[i][j])) > 1)){
X = true;
}
if((int)((j==0)?1:((i==0)?0:prefor[i-1][j-1])) + ((j==k)?1:suffor[i+1][j]) > 1){
_ = true;
}
}
if(X && _)cout << i << '\n';
if(X && !_)ans[i] = 'X';
if(_ && !X)ans[i] = '_';
}
return ans;
}
