#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int qsw[200005];
int qsb[200005];
int evp[200005];
int qs[200005];
bool dp[128][200005];
bool dpb[128][200005];
bool dps[128][200005];
string solve_puzzle(string s, vector<int> c){
int n = s.size();
s.insert(s.begin(), '0');
for(int i = 1; i <= n; i++){
if(s[i] == '_') qsw[i] = qsw[i-1]+1;
else qsw[i] = qsw[i-1];
if(s[i] == 'X') qsb[i] = qsb[i-1]+1;
else qsb[i] = qsb[i-1];
}
string out = s;
int k = c.size();
c.insert(c.begin(), 0);
for(int i = 0; i <= n+1; i++){
dp[0][i] = true;
dpb[k+1][i] = true;
dps[k+1][i] = true;
}
for(int j = 1; j <= k; j++){
for(int i = c[j]; i <= n; i++){
// if end of block is i,
if(s[i] != 'X') dp[j][i] |= dp[j][i-1];
if((i-c[j] == 0 || s[i-c[j]] != 'X') && qsw[i] - qsw[i-c[j]] == 0){
bool clause = i-c[j] == 0 ? j == 1 : dp[j-1][i-c[j]-1];
if(j == 1) clause &= qsb[i-c[j]] == 0;
dp[j][i] |= clause;
}
}
}
for(int j = k; j > 0; j--){
for(int i = n-c[j]+1; i > 0; i--){
if(s[i] != 'X') dps[j][i] |= dps[j][i+1];
if((i+c[j] == n+1 || s[i+c[j]] != 'X') && qsw[i+c[j]-1] - qsw[i-1] == 0){
bool clause = i+c[j] == n+1 ? j == k : dps[j+1][i+c[j]+1];
if(j == k) clause &= qsb[n] - qsb[i+c[j]-1] == 0;
if(j != 1) clause &= dp[j-1][i-2] && s[i-1] != 'X';
else clause &= qsb[i-1] == 0;
dps[j][i] |= clause;
}
}
}
for(int j = 1; j <= k; j++){
for(int i = c[j]; i <= n; i++){
// if end of block is i,
dp[j][i] = false;
if(s[i] != 'X') dp[j][i] |= dp[j][i-1];
if((i-c[j] == 0 || s[i-c[j]] != 'X') && qsw[i] - qsw[i-c[j]] == 0){
bool clause = i-c[j] == 0 ? j == 1 : dp[j-1][i-c[j]-1];
if(j == 1) clause &= qsb[i-c[j]] == 0;
if(j != k) clause &= dps[j+1][i+2] && s[i+1] != 'X';
else clause &= qsb[n] - qsb[i] == 0;
dp[j][i] |= clause;
if(clause){
evp[i-c[j]+1]++;
evp[i+1]--;
}
}
}
}
for(int i = 1; i <= n; i++){
qs[i] = qs[i-1] + evp[i];
if(qs[i] > 0) out[i] = s[i] == '.' ? 'x' : s[i];
else out[i] = '_';
}
for(int i = 1; i <= n; i++){
for(int j = 0; j <= k; j++){
if(dp[j][i-1] && dps[j+1][i+1]){
// i can be _
if(out[i] == 'x') out[i] = '?';
}
}
}
for(int i = 1; i <= n; i++){
if(out[i] == 'x') out[i] = 'X';
}
out.erase(out.begin());
return out;
}
