#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
void calc_dp(int n, string s, int k, vector<int> c, vector<vector<int> > &cmin, vector<vector<int> > &cmax, vector<vector<bool> > &w) {
cmin.assign(1 + n, vector<int> (1 + k, -1));
cmax.assign(1 + n, vector<int> (1 + k, -1));
w.assign(1 + n, vector<bool> (1 + k, false));
w[0][0] = true;
for(int i = 1; i <= n; i++) {
if(s[i] == 'X' || s[i] == '.') {
for(int j = 1; j <= k; j++) {
cmin[i][j] = n + 1;
if(w[i - 1][j - 1]) {
cmin[i][j] = 1;
cmax[i][j] = 1;
}
if(cmin[i - 1][j] != -1) {
cmin[i][j] = min(cmin[i][j], cmin[i - 1][j] + 1);
cmax[i][j] = max(cmax[i][j], cmax[i - 1][j] + 1);
}
cmax[i][j] = min(cmax[i][j], c[j]);
if(cmin[i][j] > cmax[i][j]) {
cmin[i][j] = -1;
cmax[i][j] = -1;
}
}
}
if(s[i] == '_' || s[i] == '.') {
if(w[i - 1][0]) {
w[i][0] = true;
}
for(int j = 1; j <= k; j++) {
if(cmax[i - 1][j] == c[j]) {
w[i][j] = true;
}
if(w[i - 1][j]) {
w[i][j] = true;
}
}
}
}
}
vector<vector<int> > left_min;
vector<vector<int> > left_max;
vector<vector<bool> > left_w;
vector<vector<int> > right_min;
vector<vector<int> > right_max;
vector<vector<bool> > right_w;
string solve_puzzle(string s, vector<signed> c) {
int n = (int) s.size();
int k = (int) c.size();
// calculate left dp
string s1 = s;
reverse(s1.begin(), s1.end());
s1.pb('!');
reverse(s1.begin(), s1.end());
vector<int> c1;
c1.pb(0);
for(int i = 0; i < k; i++) {
c1.pb(c[i]);
}
calc_dp(n, s1, k, c1, left_min, left_max, left_w);
// calculate right dp
string s2 = s;
s2.pb('!');
reverse(s2.begin(), s2.end());
vector<int> c2;
for(int i = 0; i < k; i++) {
c2.pb(c[i]);
}
c2.pb(0);
reverse(c2.begin(), c2.end());
calc_dp(n, s2, k, c2, right_min, right_max, right_w);
// calculate answer
string ans(n, '!');
for(int i = 1; i <= n; i++) {
bool b = false;
int j1, j2, cur_left_min, cur_left_max, cur_right_min, cur_right_max;
for(int idx = 1; idx <= k; idx++) {
j1 = idx, j2 = k + 1 - idx;
cur_left_min = left_min[i][j1];
cur_left_max = left_max[i][j1];
cur_right_max = right_min[n + 1 - i][j2];
cur_right_min = right_max[n + 1 - i][j2];
if(cur_left_min == -1 || cur_right_min == -1 || cur_left_max == -1 || cur_right_max == -1) {
continue;
}
cur_right_max = c1[j1] + 1 - cur_right_max;
cur_right_min = c1[j1] + 1 - cur_right_min;
if(max(cur_left_min, cur_right_min) <= min(cur_left_max, cur_right_max)) {
b = true;
break;
}
}
bool w = false;
for(int idx = 0; idx <= k; idx++) {
j1 = idx, j2 = k - idx;
if(left_w[i][j1] && right_w[n + 1 - i][j2]) {
w = true;
break;
}
}
char ch = '!';
if(b && w) {
ch = '?';
}
if(b && !w) {
ch = 'X';
}
if(!b && w) {
ch = '_';
}
ans[i - 1] = ch;
}
return ans;
}
