#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200100;
const int maxm = 110;
int n, m;
bool dp[maxn][maxm];
bool ds[maxn][maxm];
string code;
int prefwhite[maxn];
int prefblack[maxn];
int cntwhite(int l, int r) {
return prefwhite[r] - prefwhite[l-1];
}
bool possible_white[maxn];
bool possible_black[maxn];
int marker_black[maxn];
void setwhite(int l, int r) {
possible_white[l] = true;
}
void setblack(int l, int r) {
marker_black[l]++;
marker_black[r+1]--;
}
string solve_puzzle(string s, vector<int> c) {
n = s.length();
m = c.size();
s = "$" + s + "$";
code = s;
vector<int> rc = c;
reverse(rc.begin(), rc.end());
for(int i=1;i<=n;i++) {
prefwhite[i] = prefwhite[i-1];
prefblack[i] = prefblack[i-1];
if(s[i] == '_') prefwhite[i]++;
else if(s[i] == 'X') prefblack[i]++;
}
dp[0][0] = true;
for(int i=1;i<=n;i++) {
for(int j=0;j<=m;j++) {
if(j == 0) {
if(s[i] != 'X') dp[i][j] = dp[i-1][j];
continue;
}
if(s[i] == '_' || s[i] == '.') {
dp[i][j] = dp[i-1][j];
}
if(s[i] == 'X' || s[i] == '.') {
if(i - c[j-1] >= 0) {
if(s[i+1] != 'X' && s[i-c[j-1]] != 'X' && cntwhite(i-c[j-1]+1, i) == 0) {
if(j == 1)
dp[i][j] |= dp[i-c[j-1]][j-1];
else
dp[i][j] |= dp[i-c[j-1]-1][j-1];
}
}
}
//cout<<"("<<i<<", "<<j<<") -> "<<dp[i][j]<<"\n";
}
}
ds[n+1][0] = true;
for(int i=n;i>=1;i--) {
for(int j=0;j<=m;j++) {
if(j == 0) {
if(s[i] != 'X') ds[i][j] = ds[i+1][j];
continue;
}
if(s[i] == '_' || s[i] == '.') {
ds[i][j] = ds[i+1][j];
}
if(s[i] == 'X' || s[i] == '.') {
if(i + rc[j-1] -1 <= n) {
if(s[i-1] != 'X' && s[i+rc[j-1]] != 'X' && cntwhite(i, i+rc[j-1]-1) == 0) {
//cout<<"Ulaza -> "<<i<<"\n";
if(j == 1) {
ds[i][j] |= ds[i+rc[j-1]][j-1];
}
else {
ds[i][j] |= ds[i+rc[j-1]+1][j-1];
}
}
}
}
//cout<<i<<", "<<j<<" -> "<<ds[i][j]<<"\n";
}
}
for(int i=1;i<=n;i++) {
bool save = false;
for(int j=1;j<=m;j++) {
// check if you can start j-th clue at position i
if(dp[i-1][j] && ds[i+1][m-j]) {
save = true;
}
if(i + c[j-1] - 1 <= n) {
if(s[i-1] != 'X' && s[i+c[j-1]] != 'X') {
if(cntwhite(i, i+c[j-1]-1) == 0) {
if(j == 1) {
if(i + c[j-1] - 1 == n && j == m && dp[i-1][0]) {
setblack(i, i+c[j-1]-1);
setwhite(i-1, i-1);
setwhite(i+c[j-1], i+c[j-1]);
}
else if(dp[i-1][0] && ds[i+c[j-1]+1][m-j]) {
setblack(i, i+c[j-1]-1);
setwhite(i-1, i-1);
setwhite(i+c[j-1], i+c[j-1]);
}
}
else if(i >= 2){
if(j == m) {
if(dp[i-2][j-1] && ds[i+c[j-1]][m-j]) {
//cout<<"Setting last at: "<<i<<"\n";
setblack(i, i+c[j-1]-1);
setwhite(i-1, i-1);
setwhite(i+c[j-1], i+c[j-1]);
}
}
else {
if(dp[i-2][j-1] && ds[i+c[j-1]+1][m-j]) {
//cout<<"Setting: "<<j<<" at "<<i<<"\n";
setblack(i, i+c[j-1]-1);
setwhite(i-1, i-1);
setwhite(i+c[j-1], i+c[j-1]);
}
}
}
}
}
}
}
if(dp[i-1][0] && ds[i+1][m]) save = true;
if(save) {
setwhite(i, i);
}
}
int cnt = 0;
for(int i=1;i<=n;i++) {
cnt += marker_black[i];
if(cnt > 0) possible_black[i] = true;
}
string result = "";
for(int i=1;i<=n;i++) {
if(s[i] == '.') {
if(possible_black[i]) {
if(possible_white[i]) result += "?";
else result += "X";
}
else result += "_";
}
else {
result += s[i];
}
}
return result;
}
