#include "paint.h"
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
const int maxn=2e5+5, maxk=105;
bool dp[maxn][maxk][2];
bool dp2[maxn][maxk][2];
int n, k;
int sw[maxn];
bool bijela[maxn], crna[maxn];
string solve_puzzle(string s, vector < int > c) {
n=s.size();
k=c.size();
dp[0][0][0]=1;
int zadnji=0;
for(int i=1; i<=n; i++){
for(int j=0; j<=k; j++){
if(s[i-1]=='_'){
zadnji=i;
if(j){
dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j-1][1];
}
else{
dp[i][j][0]=dp[i-1][j][0];
}
}
else if(s[i-1]=='X'){
if(j<k && i-zadnji>=c[j]){
dp[i][j][1]=dp[i-c[j]][j][0];
}
}
else{
if(j){
dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j-1][1];
}
else{
dp[i][j][0]=dp[i-1][j][0];
}
if(j<k && i-zadnji>=c[j]){
dp[i][j][1]=dp[i-c[j]][j][0];
}
}
}
}
zadnji=n;
dp2[n][k][0]=1;
for(int i=n-1; i>=0; i--){
for(int j=0; j<=k; j++){
if(s[i]=='_'){
zadnji=i;
if(j<k){
dp2[i][j][0]=dp2[i+1][j][0]+dp2[i+1][j+1][1];
}
else{
dp2[i][j][0]=dp2[i+1][j][0];
}
}
else if(s[i]=='X'){
if(j && zadnji-i>=c[j-1]){
dp2[i][j][1]=dp2[i+c[j-1]][j][0];
}
}
else{
if(j<k){
dp2[i][j][0]=dp2[i+1][j][0]+dp2[i+1][j+1][1];
}
else{
dp2[i][j][0]=dp2[i+1][j][0];
}
if(j && zadnji-i>=c[j-1]){
dp2[i][j][1]=dp2[i+c[j-1]][j][0];
}
}
}
}
for(int i=1; i<=n; i++){
for(int j=0; j<=k; j++){
/* if(i==2 && j==1){
cout << dp[i][j][0] << ' ' << dp2[i-1][j][0] << endl;
}*/
if(dp[i][j][0] && dp2[i-1][j][0]){
bijela[i-1]=1;
}
if(dp[i][j][1] && dp2[i][j+1][0]){
// cout << "usao " << i << ' ' << j << endl;
// cout << "usao " << i << ' ' << j << endl;
sw[i]--;
sw[i-c[j]]++;
}
}
}
int uk=0;
for(int i=0; i<n; i++){
uk+=sw[i];
crna[i]=uk;
}
string sol;
for(int i=0; i<n; i++){
if(bijela[i] && crna[i]){
sol.push_back('?');
}
else if(bijela[i]){
sol.push_back('_');
}
else if(crna[i]){
sol.push_back('X');
}
else{
sol.push_back('?');
}
}
return sol;
}
