#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
const char any = '.';
const char white = '_';
const char black = 'X';
const char both = '?';
const int N = 200010;
const int K = 110;
int wqs[N], bqs[N];
bool dp[N][K], pb[N][K], pw[N][K], reach[N][K];
string solve_puzzle(string s, vector<int> c)
{
int n = s.size();
int k = c.size();
s.insert(s.begin(), '\0');
c.insert(c.begin(), 0);
for (int i = 1; i <= n; ++i) {
wqs[i] = wqs[i-1];
if (s[i] == white)
++wqs[i];
}
dp[n+1][k+1] = true;
for (int i = n; i >= 1; --i) {
for (int j = k+1; j >= 1; --j) {
if (j <= k && (s[i] == black || s[i] == any)) {
bool blackstrip = i+c[j]-1 <= n && wqs[i+c[j]-1]-wqs[i-1] == 0;
bool nextwhite = i+c[j] > n || s[i+c[j]] != black;
bool nextdp = dp[min(n+1, i+c[j]+1)][j+1];
if (blackstrip && nextwhite && nextdp) {
pb[i][j] = true;
dp[i][j] = true;
}
}
if ((s[i] == white || s[i] == any) && dp[i+1][j]) {
pw[i][j] = true;
dp[i][j] = true;
}
//printf("dp[%d][%d] = %d (W=%d, B=%d)\n", i, j, dp[i][j]?1:0, pw[i][j]?1:0, pb[i][j]?1:0);
}
}
for (int i = 1; i <= n; ++i)
wqs[i] = 0;
reach[1][1] = true;
for (int i = 1; i <= n+1; ++i) {
for (int j = 1; j <= k+1; ++j) if (reach[i][j] && dp[i][j]) {
if (pb[i][j]) {
bqs[i] += 1;
bqs[i+c[j]] -= 1;
wqs[i+c[j]] = 1;
reach[min(n+1, i+c[j]+1)][j+1] = true;
}
if (pw[i][j]) {
wqs[i] = 1;
reach[i+1][j] = true;
}
}
}
string ans(n, '\0');
for (int i = 1; i <= n; ++i) {
bqs[i] += bqs[i-1];
if (wqs[i] && bqs[i]) ans[i-1] = both;
else if (wqs[i]) ans[i-1] = white;
else ans[i-1] = black;
}
return ans;
}
