#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
std::string solve_puzzle(std::string s, std::vector<int> c) {
int n = s.size();
int k = c.size();
vi wh(n+1);
for (int i = 1; i <= n; i++) wh[i] = wh[i-1]+(s[i-1]=='_');
vvvi dpl(2, vvi(n+1, vi(k+1)));
vvi startl(n, vi(k+1));
dpl[0][0][0] = 1;
for (int i = 1; i <= n; i++) {
char ch = s[i-1];
if (dpl[0][i-1][0] && ch != 'X') dpl[0][i][0] = 1;
if (ch == '_' || ch == '.') for (int j = 0; j <= k; j++) dpl[0][i][j] |= dpl[0][i-1][j]|dpl[1][i-1][j];
bool prb = 0;
if (i > 1 && s[i-2] == 'X') prb = 1;
if (!prb) {
for (int j = 1; j <= k; j++) {
int l = c[j-1];
if (i+l-1 > n || !dpl[0][i-1][j-1]) continue;
int fw = wh[i+l-1]-wh[i-1];
bool nxb = 0;
if (i-1+l < n && s[i-1+l] == 'X') nxb = 1;
if (fw || nxb) continue;
dpl[1][i-1+l][j] = 1;
startl[i-1][j] = 1;
}
}
}
vvvi dpr(2, vvi(n+1, vi(k+1)));
vvi startr(n, vi(k+1));
dpr[0][n][k] = 1;
for (int i = n-1; i >= 0; i--) {
char ch = s[i];
if (dpr[0][i+1][k] && ch != 'X') dpr[0][i][k] = 1;
if (ch == '_' || ch == '.') for (int j = 0; j <= k; j++) dpr[0][i][j] |= dpr[0][i+1][j]|dpr[1][i+1][j];
bool nxb = 0;
if (i && s[i-1] == 'X') nxb = 1;
if (!nxb) {
for (int j = 0; j < k; j++) {
int l = c[j];
if (i+l > n || !dpr[0][i+l][j+1]) continue;
int fw = wh[i+l]-wh[i];
bool prb = 0;
if (i+l < n && s[i+l] == 'X') prb = 1;
if (fw || prb) continue;
dpr[1][i][j] = 1;
startr[i][j+1] = 1;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 1; j <= k; j++) {
startl[i][j] &= startr[i][j];
}
}
string ans(n, (char)0);
for (int i = 0; i < n-1; i++) {
for (int j = 1; j <= k; j++) {
if (startl[i][j]) ans[i]++;
if (startl[i][j] && !startl[i+1][j]) {
for (int l = 1; l < c[j-1]; l++) {
if (startl[i+l][j]) break;
ans[i+l]++;
}
}
}
}
//for (int i = 0; i < n; i++) {
// for (int j = 0; j <= k; j++) cout << startl[i][j] << " "; cout << " -- ";
// for (int j = 0; j <= k; j++) cout << startr[i][j] << " "; cout << endl;
//}
for (int i = 0; i < n; i++) {
char c = ans[i];
if (s[i] != '.') {
ans[i] = s[i];
continue;
}
if (c == 0) c = '_';
else {
c = 'X';
bool w = 0;
for (int j = 0; j <= k; j++) {
bool okl = dpl[0][i][j]|dpl[1][i][j];
bool okr = dpr[0][i+1][j]|dpr[1][i+1][j];
if (okl && okr && s[i] != 'X') {
w = 1;
break;
}
}
if (w) c = '?';
}
ans[i] = c;
}
return ans;
}
