#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
//dont forgot to change the sizes of arrays
int pre[200020],suf[200020];
int dp[2][200][200020]; //dp 0 i j means -> 0-i clue in 0-j chars both inclusive, dp 1 i j means -> i-(k-1) clue in j-(n-1) chars both inclusive too
int last[200020];
bool wewe[200020], bebe[200020];
int bobo[200020];
int newdp[2][200][200020];
string solve_puzzle(string s, vector<int> c) {
int n = s.length(), k = c.size();
//suf & pre
for (int i = 0; i < n; i++){
if (i == 0){
pre[i] = (int)(s[i] == '_');
suf[n - 1 - i] = (int)(s[n - 1 - i] == '_');
}
else{
pre[i] = (int)(s[i] == '_') + pre[i - 1];
suf[n - 1 - i] = (int)(s[n - 1 - i] == '_') + suf[n - i];
}
}
for (int i = 0; i < k; i++){ // first
if (i == 0){
for (int j = 0; j + c[i] - 1 < n; j++){
if (pre[j + c[i] - 1] - pre[j] - (s[j] == '_') == 0){ // no underlines in da wei :3
dp[0][i][j] = 1;
}
}
for (int j = 0; j < n; j++){
if(j == 0) last[j] = dp[0][i][j];
else last[j] = last[j - 1] + dp[0][i][j];
}
}
else{
for (int j = c[i - 1] + 1; j + c[i] - 1 < n; j++){
if (last[j - c[i - 1] - 1] > 0){
if (pre[j + c[i] - 1] - pre[j] - (s[j] == '_') == 0){ //no underlinez in da wei :3
dp[0][i][j] = 1;
}
}
}
for (int j = 0; j < n; j++){
if(j == 0) last[j] = dp[0][i][j];
else last[j] = last[j - 1] + dp[0][i][j];
}
}
}
for (int i = k - 1; i >= 0; i--){ //from last
if (i == k - 1){
for (int j = n - 1; j - c[i] + 1 >= 0; j--){
if (suf[j - c[i] + 1] - suf[j] + (s[j] == '_') == 0){ //just like the past, no underlinez
dp[1][i][j] = 1;
}
}
for (int j = n - 1; j >= 0; j--){
if (j == n - 1) last[j] = dp[1][i][j];
else last[j] = last[j + 1] + dp[1][i][j];
}
}
else{
for (int j = n - 1 - c[i + 1] - 1; j - c[i] + 1 >= 0; j--){
if (last[j + c[i + 1] + 1] > 0){
if (suf[j - c[i] + 1] - suf[j] + (s[j] == '_') == 0){ //just like the past, no underlinez
dp[1][i][j] = 1;
}
}
}
for (int j = n - 1; j >= 0; j--){
if (j == n - 1) last[j] = dp[1][i][j];
else last[j] = last[j + 1] + dp[1][i][j];
}
}
}
//preprocess again
for(int i = 0; i < k; i++){
for(int j = 0; j < n; j++){
if (j == 0) newdp[0][i][j] = dp[0][i][j];
else newdp[0][i][j] = dp[0][i][j] + newdp[0][i][j - 1];
}
}
for(int i = k - 1; i >= 0; i--){
for(int j = n - 1; j >= 0; j--){
if (j == n - 1) newdp[1][i][j] = dp[1][i][j];
else newdp[1][i][j] = dp[1][i][j] + newdp[1][i][j + 1];
}
}
for(int j = 0; j < n; j++){
//check if it can be white
if(s[j] == 'X') continue;
if(s[j] == '_') continue;
bool can = 0;
if((j + c[0] < n )){ // buh cluegee hoid tald ni tavich uzeh
if (newdp[1][0][j + c[0]] > 0) can = 1;
}
else if((j - c[k - 1] >= 0)){ //urd tald ni
if (newdp[0][k - 1][j - c[k - 1]] > 0) can = 1;
}
for(int i = 0; i < k - 1; i++){ //0~(j-1), 0~i && (j+1)~(n-1), (i+1)~(k-1)
if(can) break;
if(j - c[i] < 0) continue;
if(j + c[i + 1] >= n) continue;
if (newdp[0][i][j - c[i]] > 0){
if (newdp[1][i + 1][j + c[i + 1]] > 0){
can = 1;
break;
}
}
}
wewe[j] = can;
}
for (int i = 0; i < k; i++){
for (int j = 0; j + c[i] - 1 < n; j++){
if (pre[j + c[i] - 1] - pre[j] - (s[j] == '_') == 0){
if (j + c[i] != n){
if (s[j + c[i]] == 'X') continue;
}
if (j != 0){
if (s[j - 1] == 'X') continue;
}
if (i != 0){
if (j - 1 - c[i - 1] < 0) continue;
if (newdp[0][i - 1][j - 1 - c[i - 1]] == 0) continue;
}
if (i != k - 1){
if (j + c[i] + c[i + 1] >= n) continue;
if (newdp[1][i + 1][j + c[i] + c[i + 1]] == 0) continue;
}
// cout << j << ' ' << c[i] << '\n';
bobo[j] = max(bobo[j], c[i]);
}
}
}
for (int j = 0; j < n; j++){
if (bobo[j] > 0){
for (int l = j; l <= j + bobo[j] - 1; l++){
bebe[l] = 1;
}
}
}
// for (int i = 0; i < k; i++){
// for (int j = 0; j + c[i] - 1 < n; j++){ //can use prefix sum here to speed up
// if(newdp[i][j] == 0) break;
// if (dp[i][j] && (newdp[i][j] > 0)){
// for (int l = j; l <= j + c[i] - 1; l++){
// bebe[l] = 1;
// }
// }
// }
// }
// for (int j = 0; j < n; j++){
// cout << j << ' ';
// }
// cout << '\n';
// for (int j = 0; j < n; j++){
// cout << bebe[j];
// if(j < 9) cout << ' ';
// else cout << " ";
// }
for (int j = 0; j < n; j++){
if(s[j] == 'X') continue;
if(s[j] == '_') continue;
if(wewe[j] && bebe[j]) s[j] = '?';
else if(wewe[j]) s[j] = '_';
else s[j] = 'X';
}
// cout << s;
// debugging
// for (int j = 0; j < n; j++){
// cout << j << ' ';
// }
// cout << '\n';
// for (int j = 0; j < n; j++){
// cout << wewe[j] << ((j<9)?" ":" ");
// }
// cout << "\n#######\n";
// for (int i = 0; i < k; i++){
// for (int j = 0; j < n; j++){
// cout << newdp[0][i][j] << ((j<9)?" ":" ");
// }
// cout << '\n';
// }
return s;
}
// int main(){
// solve_puzzle(".......", {3, 3});
// }
//dont forgot to change the sizes of arrays
