#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define N 200005
int n, k, cntw[N], cntb[N], canw[N], canb[N], qwe[N];
vector <int> c;
string s, ans;
int dp[N][105], paint[N];
int solve(int idx, int col){
if (col == -1 && cntb[idx]) return 0;
if (col == -1 && !cntb[idx]) return 1;
if (idx < 2) return 0;
if (dp[idx][col] != -1) return dp[idx][col];
dp[idx][col] = 0;
if (s[idx] == '_' || s[idx] == '.') canw[idx] = dp[idx][col] = solve(idx - 1, col);
if (s[idx] == 'X' || s[idx] == '.')
if (idx - c[col] > 0 && cntw[idx] - cntw[idx - c[col]] == 0 && s[idx - c[col]] != 'X')
if (solve(idx - c[col] - 1, col - 1)){
dp[idx][col] = 1;
paint[idx]++;
paint[idx - c[col]]--;
canw[idx - c[col]] = 1;
}
return dp[idx][col];
}
string solve_puzzle(string ss, vector<int> cc) {
s = "__" + ss;
c = cc;
n = s.size();
k = c.size();
for (int i = 1;i < n;i++){
if (s[i] == '_') cntw[i]++;
cntw[i] += cntw[i - 1];
if (s[i] == 'X') cntb[i]++;
cntb[i] += cntb[i - 1];
}
memset(dp, -1, sizeof dp);
solve(n - 1, k - 1);
for (int i = n - 1;i > 1;i--)
paint[i] += paint[i + 1];
for (int i = 2;i < n;i++){
int d = 0;
if (paint[i]) d += 1;
if (canw[i]) d += 2;
if (d == 1) ans += 'X';
if (d == 2) ans += '_';
if (d == 3) ans += '?';
}
return ans;
}
