#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5;
const int MAX_K = 100;
bool sePoateLR[MAX_N + 4][MAX_K + 1], sePoateRL[MAX_N + 4][MAX_K + 1], canBeB[MAX_N + 4];
int spB[MAX_N + 4], spW[MAX_N + 4], black[MAX_N + 4];
int sumW( int l, int r ) {
return spW[r] - (l == 0 ? 0 : spW[l - 1] );
}
int sumB( int l, int r ) {
return spB[r] - (l == 0 ? 0 : spB[l - 1] );
}
string solve_puzzle( string s, vector<int> c ) {
int n = s.size(), k = c.size();
s = "_" + s + "_";
s = "." + s + ".";
reverse( c.begin(), c.end() );
c.push_back( 0 );
reverse( c.begin(), c.end() );
c.push_back( 0 );
for ( int i = 1; i <= n + 3; i++ ) {
spB[i] = spB[i - 1] + (s[i] == 'X');
spW[i] = spW[i - 1] + (s[i] == '_');
}
for ( int i = 0; i <= n + 3; i++ ) {
sePoateLR[i][0] = (sumB( 1, i ) == 0);
for ( int j = 1; j <= k + 1; j++ ) {
if ( i - c[j] < 0 ) {
sePoateLR[i][j] = false;
continue;
}
if ( sumW( i - c[j] + 1, i ) == 0 && s[i - c[j]] != 'X' )
sePoateLR[i][j] = sePoateLR[i - c[j] - 1][j - 1];
else
sePoateLR[i][j] = false;
}
if ( s[i] != 'X' && i >= 1 ) {
for ( int j = 0; j <= k + 1; j++ )
sePoateLR[i][j] |= sePoateLR[i - 1][j];
}
}
for ( int i = n + 3; i >= 0; i-- ) {
sePoateRL[i][k + 1] = (sumB( i, n + 3 ) == 0);
for ( int j = k; j >= 0; j-- ) {
if ( i + c[j] > n + 3 ) {
sePoateRL[i][j] = false;
continue;
}
if ( sumW( i, i + c[j] - 1 ) == 0 && s[i + c[j]] != 'X' ) {
if ( i + c[j] == n + 1 )
sePoateRL[i][j] = (j == k);
else
sePoateRL[i][j] = sePoateRL[i + c[j] + 1][j + 1];
} else
sePoateRL[i][j] = false;
}
if ( s[i] != 'X' && i <= n + 2 ) {
for ( int j = 0; j <= k + 1; j++ )
sePoateRL[i][j] |= sePoateRL[i + 1][j];
}
}
for ( int j = 1; j <= k; j++ ) {
for ( int l = 2; l + c[j] - 1 <= n + 1; l++ ) {
int r = l + c[j] - 1;
if ( sumW( l, r ) == 0 && s[l - 1] != 'X' && s[r + 1] != 'X' && sePoateLR[l - 2][j - 1] && sePoateRL[r + 2][j + 1] ) {
black[l]++;
black[r + 1]--;
}
}
}
int sum = 0;
for ( int i = 2; i <= n + 1; i++ ) {
sum += black[i];
canBeB[i] = (sum > 0);
}
string ans = "";
for ( int i = 2; i <= n + 1; i++ ) {
if ( s[i] != '.' ) {
ans += s[i];
continue;
}
bool canBeW = false;
for ( int j = 0; j <= k; j++ )
canBeW |= (sePoateLR[i - 1][j] & sePoateRL[i + 1][j + 1]);
if ( canBeB[i] && canBeW )
ans += '?';
else if ( canBeB[i] )
ans += 'X';
else if ( canBeW )
ans += "_";
else
ans += 'l';
}
return ans;
}
