#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];
int spB[MAX_N + 2], spW[MAX_N + 2];
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];
}
}
/*printf( "LR\n" );
for ( int i = 0; i <= n + 3; i++ ) {
printf( "%d ", i );
for ( int j = 0; j <= k + 1; j++ )
printf( "%d", sePoateLR[i][j] );
printf( "\n" );
}
printf( "RL\n" );
for ( int i = n + 3; i >= 0; i-- ) {
printf( "%d ", i );
for ( int j = k + 1; j >= 0; j-- )
printf( "%d", sePoateRL[i][j] );
printf( "\n" );
}*/
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]);
bool canBeB = false;
for ( int j = 1; j <= k; j++ ) {
for ( int l = i; l > i - c[j] && l >= 2; l-- ) {
int r = (i + (c[j] - (i - l)) - 1);
if ( r <= n + 2 && sumW( l, r ) == 0 && s[l - 1] != 'X' && s[r + 1] != 'X' )
canBeB |= (sePoateLR[l - 2][j - 1] & sePoateRL[r + 2][j + 1]);
}
}
if ( canBeB && canBeW )
ans += '?';
else if ( canBeB )
ans += 'X';
else if ( canBeW )
ans += "_";
else
ans += 'l';
}
return ans;
}
