#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define nl '\n'
int frsB = -1;
int dp[2005][105][3];
int Black[2005];
bool White[2005];
int c1[105];
bool used[2005][105][2];
void find ( string ss ) {
int ll = ss.size();
for ( int i = 0; i < ll; i++ ) {
if ( ss[i] == 'X' && frsB == -1 ) {
frsB = i;
}
}
if ( frsB == -1 ) {
frsB = 1000000000;
}
}
void go ( int clr, int num, int pos ) {
if( used[pos][num][clr] != 0 ) return;
used[pos][num][clr] = 1;
if( num == 0 && clr == 1 ) return;
if( pos < 0 ) return;
if ( clr == 0 ) {
White[pos] = 1;
if ( dp[pos - 1][num][0] == 1 ) go( 0, num, pos - 1);
if ( dp[pos - 1][num][1] == 1 ) go( 1, num, pos - 1);
return;
}
if ( clr == 1 ) {
Black[pos - c1[num - 1] + 1]++;
Black[pos + 1]--;
go ( 0, num - 1, pos - c1[num - 1] );
return;
}
}
string solve_puzzle( string s, vector<int> c) {
int n = s.size();
int k = c.size();
for ( int i = 0; i < k; i++ ) {
c1[i] = c[i];
}
find ( s );
int cntW = 0;
for ( int i = 0; i < c[0]; i++ ) {
if ( s[i] == '_' ) {
cntW++;
}
}
for ( int i = 0; i < c[0] - 1; i++ ) {
dp[i][1][1] = 0;
}
for ( int i = 0; i <= min( frsB, n - c[0] ); i++ ){
if ( cntW == 0 ) {
dp[c[0] + i - 1][1][1] = 1;
}
else {
dp[c[0] + i - 1][1][1] = 0;
}
if ( s[c[0] + i] == '_' ) {
cntW--;
}
if ( s[i] == '_' ) {
cntW--;
}
}
for ( int i = min( frsB, n - c[0] ) + c[0]; i < n; i++ ) {
dp[i][1][1] = 0;
}
for ( int i = 0; i < c[0]; i++ ) {
dp[i][1][0] = 0;
}
if ( dp[c[0] - 1][1][1] == 1 && s[c[0]] != 'X' ) {
dp[c[0]][1][0] = 1;
}
for ( int i = c[0] + 1; i < n; i++ ){
if ( s[i] == 'X' ) {
dp[i][1][0] = 0;
}
else {
if ( dp[i - 1][1][0] || dp[i - 1][1][1] ) {
dp[i][1][0] = 1;
}
else {
dp[i][1][0] = 0;
}
}
}
for ( int i = 2; i <= k; i++ ) {
cntW = 0;
for ( int j = 0; j < c[i - 1]; j++ ) {
if ( s[j] == '_' ) {
cntW++;
}
}
for ( int j = 0; j < c[i - 1]; j++ ) {
dp[j][i][1] = 0;
}
for ( int j = c[i - 1]; j < n; j++ ) {
if ( s[j] == '_' ) {
cntW++;
}
if ( s[j - c[i - 1]] == '_' ) {
cntW--;
}
dp[j][i][1] = 0;
if ( cntW == 0 && dp[j - c[i - 1]][i - 1][0] ) {
dp[j][i][1] = 1;
}
}
dp[0][i][0] = 0;
for ( int j = 1; j < n; j++ ) {
dp[j][i][0] = 0;
if ( s[j] != 'X' && (dp[j - 1][i][1] || dp[j - 1][i][0]) ) {
dp[j][i][0] = 1;
}
}
}
memset( Black, 0, sizeof Black);
memset( White, 0, sizeof White);
memset( used, 0, sizeof used );
if( dp[n - 1][k][1] == 1 ) go( 1, k, n - 1);
if( dp[n - 1][k][0] == 1 ) go( 0, k, n - 1);
int cnt = 0;
for ( int i = 0; i < n; i++ ) {
cnt += Black[i];
if ( cnt > 0 ) Black[i] = 1;
else Black[i] = 0;
}
for ( int i = 0; i < n; i++ ) {
if ( Black[i] == 1 && White[i] == 1 ){
s[i] = '?';
}
if ( Black[i] == 1 && White[i] == 0 ){
s[i] = 'X';
}
if ( Black[i] == 0 && White[i] == 1 ){
s[i] = '_';
}
}
return s;
}
