#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define N 200005
int n, k, cnt[N], can[N], dp[N][105], paint[N];
vector <int> c;
string s, ans;
int solve(int idx, int col){
if (!col && !idx) return 1;
if (idx < 0) return 0;
if (dp[idx][col] != -1) return dp[idx][col];
dp[idx][col] = 0;
// cout << idx << ' '<< col << endl;
if (s[idx] != 'X' && solve(idx - 1, col)) can[idx] = dp[idx][col] = 1;
if (col && cnt[idx] - cnt[idx - c[col - 1]] == 0 && s[idx - c[col - 1]] != 'X')
if ((col == 1 && !(idx - c[col - 1])) || solve(idx - c[col - 1] - 1, col - 1)){
dp[idx][col] = 1;
paint[idx]++;
paint[idx - c[col - 1]]--;
can[idx - c[col - 1]] = 1;
}
// cout << idx << ' '<< col << ' '<< dp[idx][col]<< endl;
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] == '_') cnt[i]++;
cnt[i] += cnt[i - 1];
}
memset(dp, -1, sizeof dp);
solve(n - 1, k);
for (int i = n - 1;i > 0;i--) paint[i] += paint[i + 1];
for (int i = 1;i < n;i++){
int d = 0;
if (paint[i]) d += 1;
if (can[i]) d += 2;
if (!d) ans += 'G';
if (d == 1) ans += 'X';
if (d == 2) ans += '_';
if (d == 3) ans += '?';
}
return ans;
}
