#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define N 200005
int n, k, cntw[N], cntb[N], cnt[105], canw[N], canb[N];
vector <int> c;
string s, ans;
int dp[N][105], paint[N][105];
int solve(int idx, int col){
if (col == -1 && !cntb[idx]) return 1;
if (col == -1 && cntb[idx]) return 0;
if (idx < 2) return 0;
if (dp[idx][col] != -1) return dp[idx][col];
dp[idx][col] = 0;
if (s[idx] == '_' || s[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][col]++;
cnt[col]++;
paint[idx - c[col]][col]--;
}
return dp[idx][col];
}
string solve_puzzle(string ss, vector<int> cc) {
s = ss;
c = cc;
s = "__" + s;
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 = 0;i < k;i++){
// cout << cnt[i]<< endl;
int sum = 0;
for (int j = n - 1;j > 1;j--){
// cout << paint[j][i]<< ' ';
sum += paint[j][i];
// cout << sum << ' ';
if (!sum) canw[j]++;
if (sum == cnt[i]) canb[j] = 1;
}
// cout << endl;
}
for (int i = 2;i < n;i++){
if (canw[i] == k) ans += '_';
else if (canb[i] || s[i] == 'X') ans += 'X';
else ans += '?';
}
return ans;
}
