#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
bool dp[200000][100];
bool dp1[200000][100];
bool black[200000];
bool white[200000];
bool okay1[200000];
bool okay2[200000];
string solve_puzzle(string s,vector<int> c) {
int n=s.size();
int k=c.size();
for(int j=0;j<k;j++) {
int cnt=0;
for(int i=0;i<c[j];i++) {
if (s[i]=='_') {
cnt++;
}
}
deque<int> dq;
bool flag=false;
for(int i=0;i<n;i++) {
if (j==0) {
dq.push_front(i);
}
if (j!=0&&i>c[j-1]&&dp[i-c[j-1]-1][j-1]) {
dq.push_front(i-c[j-1]-1);
}
if (!dq.empty()&&cnt==0&&(j!=0||!flag)) {
dp[i][j]=true;
}
if (s[i]=='X') {
flag=true;
while (!dq.empty()&&dq.back()<=i-(j==0?0:c[j-1])) {
dq.pop_back();
}
}
if (s[i]=='_') {
cnt--;
}
if (i+c[j]<n&&s[i+c[j]]=='_') {
cnt++;
}
}
}
for(int j=k-1;j>=0;j--) {
int cnt=0;
for(int i=n-c[j];i<n;i++) {
if (s[i]=='_') {
cnt++;
}
}
deque<int> dq;
bool flag=false;
for(int i=n-1;i>=0;i--) {
if (j==k-1) {
dq.push_front(i);
}
if (j!=k-1&&i+c[j+1]+1<n&&dp1[i+c[j+1]+1][j+1]) {
dq.push_front(i+c[j+1]+1);
}
if (!dq.empty()&&cnt==0&&(j!=k-1||!flag)) {
dp1[i][j]=true;
}
if (s[i]=='X') {
flag=true;
while (!dq.empty()&&dq.back()>=i+(j==k-1?0:c[j+1])) {
dq.pop_back();
}
}
if (s[i]=='_') {
cnt--;
}
if (i-c[j]>=0&&s[i-c[j]]=='_') {
cnt++;
}
}
}
for(int j=0;j<k;j++) {
int cnt=0;
for(int i=0;i<n;i++) {
//printf("%d %d\n",dp[i][0],dp1[i][0]);
if (i-c[j]>=0&&dp[i-c[j]][j]&&dp1[i-1][j]) {
//printf("- %d\n",i-c[j]);
cnt--;
}
if (i+c[j]-1<n&&dp[i][j]&&dp1[i+c[j]-1][j]) {
//printf("+ %d\n",i);
cnt++;
}
if (cnt!=0) {
black[i]=true;
}
}
}
string ret;
for(int j=0;j<=k;j++) {
memset(okay1,0,sizeof(okay1));
memset(okay2,0,sizeof(okay2));
int cnt=0;
for(int i=0;i<n;i++) {
if (j==0) {
okay1[i]=true;
}
if (i>=c[j-1]&&dp1[i-1][j-1]&&dp[i-c[j-1]][j-1]) {
cnt++;
}
if (s[i]=='X') {
cnt=0;
}
if (cnt>0) {
okay1[i]=true;
}
}
cnt=0;
for(int i=n-1;i>=0;i--) {
if (j==k) {
okay2[i]=true;
}
if (i+c[j]<n&&dp[i+1][j]&&dp1[i+c[j]][j]) {
cnt++;
}
if (s[i]=='X') {
cnt=0;
}
if (cnt>0) {
okay2[i]=true;
}
}
for(int i=0;i<n;i++) {
if (okay1[i]&&okay2[i]) {
white[i]=true;
}
}
}
for(int i=0;i<n;i++) {
if (s[i]=='X') {
white[i]=false;
}
if (s[i]=='_') {
black[i]=false;
}
if (black[i]&&white[i]) {
ret.push_back('?');
}
else if (black[i]) {
ret.push_back('X');
}
else {
ret.push_back('_');
}
}
return ret;
}
