#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int L[200050][120], R[200050][120], n, k, white[200050], black[200050], qtd[200050];
int global[200050], ini[200050], fim[200050], blocked[200050];
char ans[200050];
vector<int> pos[120], pertence[200050];
int qblack(int l, int r) {
if(l > r) return 0;
return black[r] - (l > 0 ? black[l - 1] : 0);
}
int qwhite(int l, int r){
if(l > r) return 0;
return white[r] - (l > 0 ? white[l - 1] : 0);
}
string solve_puzzle(string s, vector<int> c)
{
n = s.size(), k = c.size();
for(int i = 0; i < n; i++)
{
white[i] = (i > 0 ? white[i - 1] : 0);
black[i] = (i > 0 ? black[i - 1] : 0);
if(s[i] == '_') white[i] ++;
if(s[i] == 'X') black[i] ++;
}
memset(fim, 0x3f3f3f3f, sizeof fim);
memset(ini, -1, sizeof ini);
for(int q = 0; q < k; q++)
{
for(int i = 0; i < n; i++)
{
int ini = i - c[q] + 1;
if(ini < 0) continue;
bool tem = ( !q and (qblack(0, ini - 1) == 0) ), impossivel = false;
if(q == k - 1 and qblack(i + 1, n - 1) > 0) impossivel = true;
for(int j = 0; j < ini - 1; j++)
if(q > 0 and !tem and L[j][q - 1] and qblack(j + 1, ini - 1) == 0 ) tem = true;
if(tem and qwhite(ini, i) == 0 and !impossivel) L[i][q] = true;
//cout<<"LLLL "<<i<<" "<<q<<" "<<L[i][q]<<"\n";
}
}
for(int q = k - 1; q >= 0; q--)
{
for(int i = n - 1; i >= 0; i--)
{
int fim = i + c[q] - 1;
if(fim >= n) continue;
bool tem = ((q == (k - 1)) and (qblack(fim + 1, n - 1) == 0)), impossivel = false;
if(q == 0 and qblack(0, i - 1) > 0) impossivel = true;
for(int j = n - 1; j > fim + 1; j--)
if(q < k - 1 and !tem and R[j][q + 1] and qblack(fim + 1, j - 1) == 0) tem = true;
if(tem and qwhite(i, fim) == 0 and !impossivel) R[i][q] = true;
//cout<<"RRR "<<i<<" "<<q<<" "<<R[i][q]<<"\n";
}
}
for(int q = 0; q < k; q++)
for(int i = 0; i < n; i++)
if(i - c[q] + 1 >= 0 and L[i][q] and R[i - c[q] + 1][q]) pos[q].push_back(i - c[q] + 1);
for(int i = 0; i < n; i++)
{
for(int q = 0; q < k; q++)
{
if(i - c[q] + 1 >= 0 and L[i][q] and R[i - c[q] + 1][q])
{
for(int j = i - c[q] + 1; j <= i; j++)
{
if(s[j] == 'X')
{
ini[j] = max(ini[j], i - c[q] + 1);
fim[j] = min(fim[j], i);
}
}
}
}
}
for(int i = 0; i < n; i++)
{
if(s[i] == 'X' and ini[i] != -1)
{
for(int p = ini[i]; p <= fim[i]; p++) ans[p] = 'X';
}
}
for(int q = 0; q < k; q++)
{
memset(qtd, 0, sizeof qtd);
for(auto i: pos[q])
{
qtd[i] ++;
qtd[i + c[q]] --;
global[i] ++;
global[i + c[q]] --;
}
for(int i = 1; i < n; i++) qtd[i] += qtd[i - 1];
for(int i = 0; i < n; i++)
if(qtd[i] == pos[q].size())ans[i] = 'X';
}
string resp;
for(int i = 1; i < n; i++) global[i] += global[i - 1];
for(int i = 0; i < n; i++)
{
char p = '?';
if(s[i] != '.') p = s[i];
else if(!global[i] and ans[i] != 'X') p = '_';
else if(ans[i] == 'X') p = 'X';
resp.push_back(p);
}
return resp;
}
