#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXK = 110;
const int MAXN = 200010;
int n, k;
int canWhite[MAXN];
int canBlack[MAXN];
bool prefix[MAXN][MAXK][2];
bool suffix[MAXN][MAXK][2];
string solve_puzzle(string s, vector<int> c)
{
n = (int)s.size(); k = (int)c.size();
c.insert( c.begin() , -1 );
s.insert( s.begin() , 'o' );
prefix[0][0][0] = prefix[0][0][1] = true;
suffix[n + 1][k + 1][0] = suffix[n + 1][k + 1][1] = true;
for(int j = 0 ; j <= k ; j++)
{
for(int i = 1 ; i <= n ; i++)
{
if( s[i] == '_' || s[i] == '.' )
{
prefix[i][j][0] = prefix[i - 1][j][1];
prefix[i][j][1] = prefix[i - 1][j][1];
}
if( s[i] == 'X' || s[i] == '.' )
{
if( j == 0 ) continue;
if( i < c[j] || s[i - c[j]] == 'X' ) continue;
prefix[i][j][1] = prefix[i][j][1] || prefix[i - c[j]][j - 1][0];
}
}
}
for(int j = k + 1 ; j > 0 ; j--)
{
for(int i = n ; i > 0 ; i--)
{
if( s[i] == '_' || s[i] == '.' )
{
suffix[i][j][0] = suffix[i + 1][j][1];
suffix[i][j][1] = suffix[i + 1][j][1];
}
if( s[i] == 'X' || s[i] == '.' )
{
if( j == k + 1 ) continue;
if( i + c[j] - 1 > n || s[i + c[j]] == 'X' ) continue;
suffix[i][j][1] = suffix[i][j][1] || suffix[i + c[j]][j + 1][0];
}
}
}
for(int i = 1 ; i <= n ; i++)
{
int& w = canWhite[i];
for(int j = 0 ; j <= k ; j++)
w = w || ( prefix[i - 1][j][1] && suffix[i + 1][j + 1][1] );
}
for(int j = 1 ; j <= k ; j++)
{
int sum = 0;
for(int R = 1 ; R <= n ; R++)
{
int L = R - c[j] + 1;
if( s[R] == '_' ) sum++;
if( L > 0 && s[L] == '_' ) sum--;
if( sum != 0 || L <= 0 ) continue;
if( prefix[L - 1][j - 1][0] && suffix[R + 1][j + 1][0] )
{
canBlack[L]++;
canBlack[R + 1]--;
}
}
}
for(int i = 1 ; i <= n ; i++)
canBlack[i] += canBlack[i - 1];
string ans;
for(int i = 1 ; i <= n ; i++)
{
if( s[i] != '.' )
{
ans.push_back( s[i] );
continue;
}
if( canWhite[i] && canBlack[i] ) ans.push_back( '?' );
if( canWhite[i] && !canBlack[i] ) ans.push_back( '_' );
if( !canWhite[i] && canBlack[i] ) ans.push_back( 'X' );
}
return ans;
}
