#include <bits/stdc++.h>
#include "paint.h"
#define DIM 400010
#define DIMK 110
using namespace std;
int sp[DIM*2],sp2[DIM*2],aib[DIM],dp_left[DIM][DIMK],dp_right[DIM][DIMK];
int f[DIM],f2[DIM];
int get_sum (int x, int y){
if (x > y)
return 0;
int sol = sp[y];
if (x)
sol -= sp[x-1];
return sol;
}
int get_sum2 (int x, int y){
if (x > y)
return 0;
int sol = sp2[y];
if (x)
sol -= sp2[x-1];
return sol;
}
void update (int p, int n, int val){
for (;p<=n;p+=(p&-p))
aib[p] += val;
}
int query (int p){
int sol = 0;
for (;p;p-=(p&-p))
sol += aib[p];
return sol;
}
string solve_puzzle (string S, vector <int> c){
int n = S.length(), i, j;
string s = " ";
for (i=1;i<=n;i++)
s.push_back(S[i-1]);
for (i=1;i<=n;i++){
sp[i] = sp[i-1], sp2[i] = sp2[i-1];
if (s[i] == '_')
sp[i]++;
if (s[i] == 'X')
sp2[i]++;
}
/// dp_left[i][j] = true daca pot sa pun primele j piese pe primele i pozitii
for (j=0;j<c.size();j++){
int lg = c[j];
for (i=lg;i<=n;i++){
if (!j){
if (s[i] == '_')
dp_left[i][j] = dp_left[i-1][j];
else {
if (s[i] == 'X'){
if (get_sum(i-lg+1,i) == 0 && get_sum2(1,i-lg) == 0)
dp_left[i][j] = 1;
} else {
dp_left[i][j] = dp_left[i-1][j];
if (get_sum(i-lg+1,i) == 0 && get_sum2(1,i-lg) == 0)
dp_left[i][j] = 1;
}}
continue;
}
if (s[i] == '_')
dp_left[i][j] = dp_left[i-1][j];
else {
if (s[i] == 'X'){
if (get_sum(i-lg+1,i) == 0 && s[i-lg] != 'X')
dp_left[i][j] = dp_left[i-lg-1][j-1];
} else { /// '.'
dp_left[i][j] = dp_left[i-1][j];
if (get_sum(i-lg+1,i) == 0 && s[i-lg] != 'X')
dp_left[i][j] |= dp_left[i-lg-1][j-1];
}}}}
for (j=c.size()-1;j>=0;j--){
int lg = c[j];
for (i=n-lg+1;i>=1;i--){
if (j == c.size()-1){
if (s[i] == '_')
dp_right[i][j] = dp_right[i+1][j];
else{
if (s[i] == 'X'){
if (get_sum(i,i+lg-1) == 0 && get_sum2(i+lg,n) == 0)
dp_right[i][j] = 1;
} else {
dp_right[i][j] = dp_right[i+1][j];
if (get_sum(i,i+lg-1) == 0 && get_sum2(i+lg,n) == 0)
dp_right[i][j] = 1;
}}
continue;
}
if (s[i] == '_')
dp_right[i][j] = dp_right[i+1][j];
else{
if (s[i] == 'X'){
if (get_sum(i,i+lg-1) == 0 && s[i+lg] != 'X')
dp_right[i][j] = dp_right[i+lg+1][j+1];
} else {
dp_right[i][j] = dp_right[i+1][j];
if (get_sum(i,i+lg-1) == 0 && s[i+lg] != 'X')
dp_right[i][j] |= dp_right[i+lg+1][j+1];
}}}}
/// f[i] = 1 => casuta asta nu poate sa fie mereu alba
for (i=1;i<=n;i++){
if (s[i] == '_')
continue;
/// incerc sa pun X aici si sa vad daca pot sa am vreo solutie
if (s[i-1] == 'X')
continue;
int maxi = 0;
for (j=0;j<c.size() && c.size() > 1;j++){
int lg = c[j];
if (get_sum(i,i+lg-1) || (i-2 < 0 && j) || i + lg - 1 > n)
continue;
if (s[i+lg] == 'X')
continue;
if (!j && get_sum2(1,i-1) == 0 && (c.size()==1 || dp_right[i+lg+1][j+1]))
maxi = max (maxi,lg);
if (j == c.size()-1 && get_sum2(i+lg,n) == 0 && (c.size()==1 || dp_left[i-2][j-1]))
maxi = max (maxi,lg);
if (dp_left[i-2][j-1] && dp_right[i+lg+1][j+1])
maxi = max (maxi,lg);
}
if (c.size() == 1 && get_sum2(1,i-1) == 0 && get_sum2 (i+c[0],n) == 0 && get_sum(i,i+c[0]-1) == 0 && i+c[0]-1 <= n)
maxi = c[0];
/// in intervalul i...i+maxi-1 nu pot avea mereu alb
for (j=i;j<=i+maxi-1;j++)
f[j] = 1;
}
/// f2[i] = 1 -> casuta asta nu poate sa fie neagra mereu
for (i=1;i<=n;i++){
int ok = 0;
for (j=0;j<c.size();j++){
if (!j && dp_right[i+1][j] && get_sum2(1,i) == 0){
ok = 1;
break;
}
if (j == c.size()-1 && dp_left[i-1][j] && get_sum2(i,n) == 0){
ok = 1;
break;
}
if (dp_left[i-1][j] && dp_right[i+1][j+1]){
ok = 1;
break;
}}
f2[i] = ok;
}
for (i=1;i<=n;i++){
if (s[i] == 'X' || s[i] == '_')
continue;
if (f[i] == 0 && f2[i] == 1){
s[i] = '_';
continue;
}
if (f[i] == 1 && f2[i] == 0){
s[i] = 'X';
continue;
}
s[i] = '?';
}
string sol = "";
for (i=1;i<=n;i++)
sol.push_back(s[i]);
return sol;
}
