#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef string str;
const int N = 2e5 + 5;
const int K = 1e2 + 5;
bool dp[N][K];
bool rdp[N][K];
int ps[N];
int B[N], W[N];
str solve_puzzle(str s, vector<int> C){
int k = (int) C.size();
s = "_" + s + "_";
int n = (int) s.size();
ps[0] = 0;
for(int i = 1; i <= n; i++) ps[i] = ps[i - 1] + (s[i - 1] == '_');
memset(dp, 0, sizeof dp);
dp[0][0] = true;
for(int i = 1; i < n; i++){
if(s[i] == 'X') continue;
for(int j = 0; j <= k; j++){
dp[i][j] = dp[i - 1][j];
if(j > 0 && C[j - 1] < i && ps[i] == ps[i - C[j - 1]])
dp[i][j] |= dp[i - C[j - 1] - 1][j - 1];
}
}
memset(rdp, 0, sizeof rdp);
rdp[n - 1][0] = true;
for(int i = n - 2; i >= 0; i--){
if(s[i] == 'X') continue;
for(int j = 0; j <= k; j++){
rdp[i][j] = rdp[i + 1][j];
if(j > 0 && C[k - j] < n - 1 - i && ps[i + 1] == ps[i + 1 + C[k - j]])
rdp[i][j] |= rdp[i + C[k - j] + 1][j - 1];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j <= k; j++)
if(dp[i][j] && rdp[i][k - j])
W[i] = 1;
}
for(int i = 0; i < k; i++){
for(int st = 1; st + C[i] < n; st ++){
if(ps[st] != ps[st + C[i]]) continue;
if(dp[st - 1][i] && rdp[st + C[i]][k - i - 1])
B[st] ++, B[st + C[i]] --;
}
}
for(int i = 1; i < n; i++) B[i] += B[i - 1];
str res = "";
for(int i = 1; i < n - 1; i++){
B[i] = min(B[i], 1);
assert(W[i] + B[i] >= 1);
if(W[i] == 1 && B[i] == 1) res += "?";
else if(W[i] == 1) res += "_";
else res += "X";
}
return res;
}
