#include <bits/stdc++.h>
#include "paint.h"
#define DIMN 200010
using namespace std;
int st[200010][110] , dr[200010][110] , sp0[DIMN] , sp1[DIMN];
char v[DIMN];
int white[DIMN] , black[DIMN];
pair <int,int> event[20000010];
string sol;
string solve_puzzle(string s, vector<int> c) {
int n , k , i , j , ev , cnt , poz;
n = s.size();
k = c.size();
for (i = 1 ; i <= n ; i++)
v[i] = s[i - 1];
for (i = 1 ; i <= n ; i++){
sp0[i] = sp0[i - 1];
sp1[i] = sp1[i - 1];
if (s[i - 1] == '_')
sp0[i]++;
else if (s[i - 1] == 'X')
sp1[i]++;
}
/// MAI SUNT NISTE CONDITII PT ALEA PRESTABILITE !!!!!!!!!
st[0][0] = 1;
/// st[i][j] = pot sa pun primele j seturi pe poz 1 .. i??
for (i = 1 ; i <= n ; i++){
if (sp1[i] == 0)
st[i][0] = 1;
for (j = 1 ; j <= k ; j++){
if (v[i] != 'X')
st[i][j] = st[i - 1][j];
/// altfel, inchei setul i pe pozitia j, DACA POT
if (i - c[j - 1] - 1 == -1 && sp0[i] == 0 && v[i + 1] != 'X' && j == 1){
st[i][j] = 1;
}
if (i - c[j - 1] - 1 >= 0 && v[i - c[j - 1]] != 'X' && sp0[i] - sp0[i - c[j - 1]] == 0 && v[i + 1] != 'X')
st[i][j] = (st[i][j] | st[i - c[j - 1] - 1][j - 1]);
}
}
dr[n + 1][k + 1] = 1;
dr[n + 2][k + 1] = 1;
/// dr[i][j] = pot sa pun seturile j ... k pe poz i ... n ?
for (i = n ; i ; i--){
if (sp1[n] - sp1[i - 1] == 0)
dr[i][k + 1] = 1;
for (j = k ; j ; j--){
if (v[i] != 'X')
dr[i][j] = dr[i + 1][j];
/// altfel, incep setul j pe pozitia i, daca pot
if (i + c[j - 1] <= n+1 && v[i + c[j - 1]] != 'X' && sp0[i + c[j - 1] - 1] - sp0[i - 1] == 0 && v[i - 1] != 'X')
dr[i][j] = (dr[i][j] | dr[i + c[j - 1] + 1][j + 1]);
}
}
ev = 0;
for (i = 1 ; i <= n ; i++){
for (j = 1 ; j <= k ; j++){
/// poate sa se termine pe pozitia i setul j?
if (i - c[j - 1] - 1 >= 0 && v[i - c[j - 1]] != 'X' && sp0[i] - sp0[i - c[j - 1]] == 0 && v[i + 1] != 'X'
&& st[i - c[j - 1] - 1][j - 1] && dr[i + 2][j + 1]){
event[++ev] = make_pair(i - c[j - 1] + 1 , 1);
event[++ev] = make_pair (i + 1 , -1);
}
else if (i - c[j - 1] == 0 && j == 1 && sp0[i] == 0 && v[i + 1] != 'X' && dr[i + 2][j + 1]){
event[++ev] = make_pair(1 , 1);
event[++ev] = make_pair(i + 1 , -1);
}
if ((st[i - 1][j] && dr[i + 1][j + 1]) || (st[i - 1][j - 1] && dr[i + 1][j]))
white[i] = 1;
//if (i == 7 && white[i] == 1)
// printf ("a");
}
}
sort (event + 1 , event + ev + 1);
cnt = 0;
poz = 1;
for (i = 1 ; i <= n ; i++){
while (poz <= ev && event[poz].first == i){
cnt += event[poz].second;
poz++;
}
if (cnt)
black[i] = 1;
}
for (i = 1 ; i <= n ; i++){
if (v[i] != '.')
sol.push_back(v[i]);
else {
if (black[i] && white[i])
sol.push_back('?');
else if (black[i])
sol.push_back('X');
else if (white[i])
sol.push_back('_');
}
}
return sol;
}
