#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
#define all(s) s.begin(),s.end()
#define pb push_back
#define ll long long
const int N = 2e5 + 17, K = 100 + 17;
int a[N], b1[N], b2[N];
bool dp1[N][K], dp2[N][K];
string solve_puzzle(string s, vector<int> c) {
int i , j , n = s.size() , k = c.size();
for(int i = 0; i < n; i++)
a[i + 1] = a[i] + (s[i] == '_');
dp1[0][0] = dp2[n][k] = 1;
for(i = 0; i < n; i++){
for(j = 0; j <= k; j++){
if(s[i] != 'X')
dp1[i + 1][j] |= dp1[i][j];
if(j < k && i + c[j] < n && s[i + c[j]]^'X')
if(a[i + c[j]] == a[i])
dp1[i+c[j]+1][j+1] |= dp1[i][j];
}
}
for(int i = n; i > 0; i--) {
for(int j = 0; j <= k; j++) {
if(s[i - 1] != 'X')
dp2[i - 1][j] |= dp2[i][j];
if(j && i - c[j - 1] > 0 && s[i - c[j - 1] - 1] ^ 'X')
if(a[i] == a[i - c[j - 1]])
dp2[i - c[j - 1] - 1][j - 1] |= dp2[i][j];
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j <= k; j++)
b1[i] |= dp1[i + 1][j] && dp2[i][j];
for(int j = 0; j < k; j++) {
if(i + c[j] <= n && dp1[i][j] && dp2[i + c[j]][j + 1] && a[i + c[j]] == a[i]) {
b2[i]++;
b2[i + c[j]]--;
}
}
b2[i + 1] += b2[i];
if(b1[i] && b2[i])
s[i] = '?';
else if(b1[i])
s[i] = '_';
else
s[i] = 'X';
}
return s;
}
